SDP LMI results do not satisfy all constraints

I would like to solve the following LMIs with CVX SDP:

P == X_0*Q

[P X_1* Q ; transpose(X_1*Q) P] > 0

where P is to be positive definite and Q is a non-square matrix, both of which are decision variables.
X_{1,T} is a 1 x T matrix containing the states of a system sampled T times consecutively:

X_{1,T} = [ x(1) x(2), … x(T)] %Not including initial conditions x(0)

I have implemented this into MATLAB:
image
n= number of states, where T = number of samples taken

However, when verifying the above constraints with the produced P and Q from the solver, none of the constraints are satisfied, except that P is positive definite (implicitly given).

The log produced is as follows:
Calling SDPT3 4.0: 96 variables, 42 equality constraints

num. of constraints = 42
dim. of sdp var = 8, num. of sdp blk = 1
dim. of free var = 60 *** convert ublk to lblk
number of nearly dependent constraints = 34
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 1.


SDPT3: Infeasible path-following algorithms


version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|4.5e+04|9.2e+14|1.2e+18| 0.000000e+00 0.000000e+00| 0:0:00| chol 5 10
1|0.000|0.068|4.5e+04|8.6e+14|2.3e+17| 0.000000e+00 4.679271e-06| 0:0:00| chol
linsysolve: Schur complement matrix not positive definite
switch to LU factor. lu 11 ^10
2|0.017|0.001|8.4e+07|8.6e+14|5.3e+16| 0.000000e+00 4.566872e-06| 0:0:00| lu 11 ^11
3|0.038|0.033|8.1e+07|8.3e+14|1.8e+16| 0.000000e+00 4.924854e-06| 0:0:00| lu 22 ^16
4|0.005|0.005|8.1e+07|8.2e+14|1.1e+16| 0.000000e+00 4.490137e-06| 0:0:00| lu 20 ^28
5|0.024|0.041|7.9e+07|7.9e+14|8.8e+15| 0.000000e+00 4.573615e-06| 0:0:00| lu 30 ^11
6|0.287|0.249|5.6e+07|5.9e+14|6.3e+15| 0.000000e+00 5.806613e-06| 0:0:00| lu 30 ^15
7|0.020|0.039|5.5e+07|5.7e+14|5.9e+15| 0.000000e+00 8.674502e-06| 0:0:00| lu 30 ^15
8|0.006|0.024|5.5e+07|5.6e+14|5.8e+15| 0.000000e+00 9.459091e-06| 0:0:00| lu 30 30
9|0.013|0.042|5.4e+07|5.3e+14|5.6e+15| 0.000000e+00 8.064293e-06| 0:0:00| lu 19 ^ 7
10|0.070|0.152|5.0e+07|4.5e+14|4.8e+15| 0.000000e+00 1.181983e-05| 0:0:00| lu 30 ^14
11|0.023|0.034|4.9e+07|4.4e+14|4.6e+15| 0.000000e+00 1.340708e-05| 0:0:00| lu 30 ^ 2
12|0.000|0.001|4.9e+07|4.4e+14|4.6e+15| 0.000000e+00 1.406109e-05| 0:0:00| lu 30 ^ 9
13|0.168|0.010|4.1e+07|4.3e+14|4.2e+15| 0.000000e+00 1.407104e-05| 0:0:00| lu 30 ^ 7
14|0.023|0.032|4.0e+07|4.2e+14|3.9e+15| 0.000000e+00 1.392335e-05| 0:0:00| lu 30 30
15|0.035|0.063|3.8e+07|3.9e+14|3.6e+15| 0.000000e+00 1.298630e-05| 0:0:00| lu 30 ^ 9
16|0.132|0.019|3.3e+07|3.8e+14|3.4e+15| 0.000000e+00 1.292926e-05| 0:0:00| lu 30 ^ 6
17|0.136|0.067|2.9e+07|3.6e+14|2.9e+15| 0.000000e+00 1.470041e-05| 0:0:01| lu 30 ^ 4
18|0.539|0.087|1.3e+07|3.3e+14|2.2e+15| 0.000000e+00 1.534966e-05| 0:0:01| lu 11 ^17
19|0.041|0.044|1.3e+07|3.1e+14|1.8e+15| 0.000000e+00 1.642148e-05| 0:0:01| lu 11 ^10
20|0.004|0.020|1.3e+07|3.1e+14|1.7e+15| 0.000000e+00 2.174916e-05| 0:0:01| lu 30 30
21|0.025|0.076|1.2e+07|2.8e+14|1.6e+15| 0.000000e+00 2.708212e-05| 0:0:01|
stop: steps too short consecutively

number of iterations = 21
primal objective value = 0.00000000e+00
dual objective value = 2.70821227e-05
gap := trace(XZ) = 1.63e+15
relative gap = 1.63e+15
actual relative gap = -2.71e-05
rel. primal infeas (scaled problem) = 1.23e+07
rel. dual " " " = 2.83e+14
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 3.8e+04, 2.1e+11, 2.0e+14
norm(A), norm(b), norm© = 2.0e+13, 1.0e+00, 1.0e+00
Total CPU time (secs) = 0.63
CPU time per iteration = 0.03
termination code = -5
DIMACS: 1.2e+07 0.0e+00 2.8e+14 0.0e+00 -2.7e-05 1.6e+15


Status: Failed
Optimal value (cvx_optval): NaN

Here is the code to reproduce the result:

A=[1.38 -0.2077 6.715 -5.676; -0.5814 -4.29 0 0.675; 1.067 4.273 -6.654 5.893;0.048 4.273 1.343 -2.104];
B=[0 0; 5.679 0; 1.136 -3.146; 1.136 0];
C=[1 0 1 -1;0 1 0 0];
D=0;

T=15;
n = 4; 
%Randomly generated inputs
u=[0.590904730405336	0.0503399867389541	0.834189061056900	0.863710865055866	0.669042590081555	0.217993798750154	0.122189150923420	0.599585548122814	0.0563430185433568	0.0196210667655841	0.832221475282818	0.520129415310742	0.0976979181614431	0.108016694136759	0.143156022083576; 0.459380047966325	0.228687584020221	0.0156446926965270	0.0780690530324343	0.500211324281102	0.571615725404089	0.671166232988653	0.0559761573877905	0.152500637002470	0.435175545696952	0.617390171454084	0.863868222933611	0.908052203186769	0.516996758096945	0.559370572403004];
x(:,1)=[1;1;1;1];  %Arbitrary initial conditions

for i=1:T
    x(:,i+1)=A*x(:,i)+B*u(:,i);
end
X_1=x(:,2:(T-1+2));

I am wondering if I have implemented this incorrectly into CVX or perhaps I need to reformulate the problem better. Any help/insight would be appreciated! Thanks!

x has some huge values which appear to be beyond SDPT3’s ability to handle. So the solver failed. All variable values after the solver fails are meaningless.

You need to improve the formulation to not have huge values of x.

In the future, instead of posting an image of your code, please copy and pasted the code into your post, using Preformatted text icon.

1 Like

Thank you very much! And duly noted on the preformatting for future posts!