# Infeasible convex optimization

(eliiiiiiiiiiiiiiiii) #1

Do you know that why this problem is infeasible?
I couldn’t find reason.

``````clc
clear all
close all
%%
A = [-0.8 0.3;0.1 1.2]
B = [0.3;0.1]
C =[0.1 -0.2]
mu = 0.8
delta = 0.4
d1 = 2
d2 = 5
Q =[0.3 0;0 0.4]
n = size(A,1);
[n,m] = size(B);
[q,n] = size(C);
%% cvx-optimization
cvx_begin sdp
variable Y(n,n) symmetric;
variable X(n,n) symmetric;

variable AT(n,n) ;
variable BT(n,m) ;
variable CT(q,n) ;
variable DT(q,m) ;

variable gama1 ;

omega1=A'+mu*C'*DT'*B'
omega2=Y*A'+mu*CT'*B'
omega3=A'*X+C'*BT'

Dtel = d2-d1+1

minimize delta^2*gama1
subject to

% H-infinite condition
[-Y -eye(n) zeros(n) zeros(n,1) zeros(n,1) omega2 AT CT' Dtel*Y;
-eye(n) -X zeros(n) zeros(n,1) zeros(n,1) omega1 omega3 C'*DT' Dtel*eye(n);
zeros(1,n) zeros(1,n) zeros(1,n) gama1*eye(1) zeros(1) zeros(1,n) zeros(1,n) zeros(1) zeros(1,n);
zeros(1,n) zeros(1,n) zeros(1,n) zeros(1) -gama1*eye(1) mu*B' mu*B'*X zeros(1) zeros(1,n);
omega2' omega1' Ad zeros(n,1) mu*B -Y -eye(n) zeros(n,1) zeros(n);
AT' omega3' X*Ad zeros(n,1) mu*X*B -eye(n) -X zeros(n,1) zeros(n);
CT DT*C zeros(1,n) zeros(1) eye(1) zeros(1,n) zeros(1,n) -eye(1) zeros(1,n);
Dtel*Y' Dtel*eye(n) zeros(n) zeros(n,1) zeros(n,1) zeros(n) zeros(n) zeros(n,1) -inv(Q)]<=0

cvx_end
W=[10 1.6;1 -6]
S = (eye(n) - X*Y)*inv(W')``````

(Mark L. Stone) #2

CVX provides a warning, which you should have investigated:

``````Warning: This linear matrix inequality appears to be unsymmetric. This is
very likely an error that will produce unexpected results. Please check
the LMI; and, if necessary, re-enter the model.
``````

zeros(1) and eye(1) are not symmetric entries

That may not solve all your difficulties, but you need to at least fix those errors.

(eliiiiiiiiiiiiiiiii) #3

I correct the unsymmetrical terms but it still infeasible too…

``````clc
clear all
close all
%%
A = [-0.8 0.3;0.1 1.2]
B = [0.3;0.1]
C =[0.1 -0.2]
mu = 0.8
delta = 0.4
d1 = 2
d2 = 5
Q =[0.3 0;0 0.4]
n = size(A,1);
[n,m] = size(B);
[q,n] = size(C);
%% cvx-optimization
cvx_begin sdp
variable Y(n,n) symmetric;
variable X(n,n) symmetric;

variable AT(n,n) ;
variable BT(n,m) ;
variable CT(q,n) ;
variable DT(q,m) ;

variable gamasq1 ;

omega1=A'+mu*C'*DT'*B'
omega2=Y*A'+mu*CT'*B'
omega3=A'*X+C'*BT'

Dtel = d2-d1+1

minimize delta^2*gamasq1
subject to

% H-infinite condition
[-Y -eye(n) zeros(n) zeros(n,1) omega2 AT CT' Dtel*Y;
-eye(n) -X zeros(n) zeros(n,1) omega1 omega3 C'*DT' Dtel*eye(n);
zeros(1,n) zeros(1,n) zeros(1,n) -gamasq1*eye(1,1) mu*B' mu*B'*X eye(1) zeros(1,n);
omega2' omega1' Ad mu*B -Y -eye(n) zeros(n,1) zeros(n);
AT' omega3' X*Ad mu*X*B -eye(n) -X zeros(n,1) zeros(n);
CT DT*C zeros(1,n) eye(1) zeros(1,n) zeros(1,n) -eye(1) zeros(1,n);
Dtel*Y' Dtel*eye(n) zeros(n) zeros(n,1) zeros(n) zeros(n) zeros(n,1) -Dtel*inv(Q)]<=0

cvx_end``````

(Mark L. Stone) #4

If the objective is changed to `minimize(lamnda_max(LMI_matrix))` and the LMI constraint on what I will call `LMI_matrix` is removed, it can be seen that if the RHS of the original problem is changed from `0` to `0.106309 *eye(14)` (per sdpt3) or `0.106307*eye(14)` (per sedumi), the problem becomes feasible. I.e.,the `LMImatrix` 's maximum eigenvalue needs to be reduced by `0.106309` (`0.106307`) to become feasible.

It’s your problem, so I’ll let you figure out why. I don;t even know why the problem “should be” feasible, but presumably you do.

(eliiiiiiiiiiiiiiiii) #5

okay…but i don’t understand your mean exactly…could you send the code for me that utilized now.
thank you

(Mark L. Stone) #6
``````cvx_begin sdp
variable Y(n,n) symmetric;
variable X(n,n) symmetric;

variable AT(n,n) ;
variable BT(n,m) ;
variable CT(q,n) ;
variable DT(q,m) ;

variable gamasq1 ;

omega1=A'+mu*C'*DT'*B'
omega2=Y*A'+mu*CT'*B'
omega3=A'*X+C'*BT'

Dtel = d2-d1+1

minimize(lambda_max([-Y -eye(n) zeros(n) zeros(n,1) omega2 AT CT' Dtel*Y;
-eye(n) -X zeros(n) zeros(n,1) omega1 omega3 C'*DT' Dtel*eye(n);
zeros(1,n) zeros(1,n) zeros(1,n) -gamasq1*eye(1,1) mu*B' mu*B'*X eye(1) zeros(1,n);
omega2' omega1' Ad mu*B -Y -eye(n) zeros(n,1) zeros(n);
AT' omega3' X*Ad mu*X*B -eye(n) -X zeros(n,1) zeros(n);
CT DT*C zeros(1,n) eye(1) zeros(1,n) zeros(1,n) -eye(1) zeros(1,n);
Dtel*Y' Dtel*eye(n) zeros(n) zeros(n,1) zeros(n) zeros(n) zeros(n,1) -Dtel*inv(Q)]))

cvx_end

Calling SDPT3 4.0: 105 variables, 17 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

num. of constraints = 17
dim. of sdp    var  = 14,   num. of sdp  blk  =  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|1.2e+02|3.6e+00|2.7e+03| 1.983333e+02  0.000000e+00| 0:0:00| chol  1  1
1|0.909|1.000|1.1e+01|1.9e-02|4.1e+02| 7.463330e+01 -2.411475e+01| 0:0:00| chol  1  1
2|0.956|1.000|4.7e-01|1.9e-03|3.8e+01| 8.281218e+00 -1.867948e+01| 0:0:00| chol  1  1
3|0.815|0.960|8.8e-02|2.6e-04|7.8e+00| 3.496987e+00 -2.672382e+00| 0:0:00| chol  1  1
4|0.727|1.000|2.4e-02|1.8e-02|3.6e+00| 6.943494e-01 -2.326394e+00| 0:0:00| chol  1  1
5|0.955|0.872|1.1e-03|7.0e-03|5.1e-01|-1.838188e-01 -6.392939e-01| 0:0:00| chol  1  1
6|0.726|1.000|2.9e-04|2.1e-04|2.5e-01|-3.837339e-01 -6.227346e-01| 0:0:00| chol  1  1
7|0.942|0.927|1.7e-05|7.4e-05|3.2e-02|-4.843336e-01 -5.151049e-01| 0:0:00| chol  1  1
8|0.866|1.000|2.3e-06|3.4e-06|9.2e-03|-4.990629e-01 -5.081143e-01| 0:0:00| chol  1  1
9|0.890|0.964|2.5e-07|5.7e-07|1.3e-03|-5.053969e-01 -5.066514e-01| 0:0:00| chol  1  1
10|0.845|1.000|3.9e-08|5.0e-08|5.7e-04|-5.058713e-01 -5.064226e-01| 0:0:00|# chol  1  1
11|1.000|1.000|1.2e-09|7.7e-09|3.5e-05|-5.062915e-01 -5.063192e-01| 0:0:00|# chol  1  1
12|0.979|0.986|1.0e-09|3.5e-10|6.8e-07|-5.063153e-01 -5.063095e-01| 0:0:00|# chol  1  1
13|1.000|1.000|1.1e-09|2.1e-10|7.5e-08|-5.063162e-01 -5.063094e-01| 0:0:00|# chol  1  1
14|1.000|1.000|1.1e-09|5.0e-11|2.9e-09|-5.063163e-01 -5.063094e-01| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations   = 14
primal objective value = -5.06316294e-01
dual   objective value = -5.06309376e-01
gap := trace(XZ)       = 2.86e-09
relative gap           = 1.42e-09
actual relative gap    = -3.44e-06
rel. primal infeas (scaled problem)   = 1.13e-09
rel. dual     "        "       "      = 5.01e-11
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual     "        "       "      = 0.00e+00
norm(X), norm(y), norm(Z) = 8.9e-01, 3.1e+03, 3.1e+03
norm(A), norm(b), norm(C) = 2.0e+01, 2.0e+00, 1.9e+01
Total CPU time (secs)  = 0.17
CPU time per iteration = 0.01
termination code       =  0
DIMACS: 1.1e-09  0.0e+00  7.0e-11  0.0e+00  -3.4e-06  1.4e-09
-------------------------------------------------------------------

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.106309
``````

Now if you run your problem, but make the RHS of the LMI `t*eye(14)`, instead of `0`, where `t` is some number >= 0.106309, the problem will be feasible.

For instance,

``````cvx_begin sdp
variable Y(n,n) symmetric;
variable X(n,n) symmetric;

variable AT(n,n) ;
variable BT(n,m) ;
variable CT(q,n) ;
variable DT(q,m) ;

variable gamasq1 ;

omega1=A'+mu*C'*DT'*B'
omega2=Y*A'+mu*CT'*B'
omega3=A'*X+C'*BT'

Dtel = d2-d1+1

minimize delta^2*gamasq1
subject to

% H-infinite condition
[-Y -eye(n) zeros(n) zeros(n,1) omega2 AT CT' Dtel*Y;
-eye(n) -X zeros(n) zeros(n,1) omega1 omega3 C'*DT' Dtel*eye(n);
zeros(1,n) zeros(1,n) zeros(1,n) -gamasq1*eye(1,1) mu*B' mu*B'*X eye(1) zeros(1,n);
omega2' omega1' Ad mu*B -Y -eye(n) zeros(n,1) zeros(n);
AT' omega3' X*Ad mu*X*B -eye(n) -X zeros(n,1) zeros(n);
CT DT*C zeros(1,n) eye(1) zeros(1,n) zeros(1,n) -eye(1) zeros(1,n);
Dtel*Y' Dtel*eye(n) zeros(n) zeros(n,1) zeros(n) zeros(n) zeros(n,1) -Dtel*inv(Q)]<=.106309*eye(14)

cvx_end

Calling SDPT3 4.0: 105 variables, 16 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

num. of constraints = 16
dim. of sdp    var  = 14,   num. of sdp  blk  =  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|2.7e+01|3.5e+00|2.8e+03| 2.599011e+02  0.000000e+00| 0:0:00| chol  1  1
1|0.861|0.942|3.7e+00|2.2e-01|3.3e+02| 9.552136e+01 -3.196340e+00| 0:0:00| chol  1  1
2|0.874|0.816|4.7e-01|4.2e-02|7.1e+01| 3.273188e+01 -3.213664e+00| 0:0:00| chol  1  1
3|0.818|0.807|8.4e-02|8.2e-03|3.1e+01| 1.994043e+01 -2.682973e+00| 0:0:00| chol  1  1
4|0.833|0.752|1.4e-02|3.3e-03|9.8e+00| 5.281529e+00 -1.577143e+00| 0:0:00| chol  1  1
5|0.900|0.725|1.4e-03|1.0e-03|2.1e+00|-6.703837e-01 -1.286179e+00| 0:0:00| chol  1  1
6|0.539|0.480|6.5e-04|5.9e-04|1.4e+00|-2.050551e+00 -1.684234e+00| 0:0:00| chol  1  1
7|0.314|0.314|4.4e-04|4.3e-04|1.5e+00|-3.082940e+00 -2.164462e+00| 0:0:00| chol  1  1
8|0.230|0.334|3.4e-04|3.0e-04|1.6e+00|-4.154286e+00 -2.855188e+00| 0:0:00| chol  1  1
9|0.203|0.381|2.7e-04|1.9e-04|1.4e+00|-5.629699e+00 -3.838021e+00| 0:0:00| chol  1  1
10|0.163|0.322|2.3e-04|1.4e-04|1.4e+00|-7.904277e+00 -5.134345e+00| 0:0:00| chol  1  1
11|0.240|0.279|1.7e-04|1.0e-04|1.8e+00|-1.150792e+01 -7.001989e+00| 0:0:00| chol  1  1
12|0.124|0.283|1.5e-04|7.4e-05|2.0e+00|-1.581281e+01 -9.368133e+00| 0:0:00| chol  1  1
13|0.383|0.330|9.4e-05|5.0e-05|2.3e+00|-2.330976e+01 -1.339650e+01| 0:0:00| chol  1  1
14|0.222|0.347|7.3e-05|3.4e-05|2.8e+00|-3.255485e+01 -1.955213e+01| 0:0:00| chol  1  1
15|0.192|0.325|5.9e-05|2.3e-05|3.1e+00|-4.554010e+01 -2.739114e+01| 0:0:00| chol  1  1
16|0.120|0.285|5.2e-05|1.7e-05|5.0e+00|-5.984181e+01 -3.746028e+01| 0:0:00| chol  1  1
17|0.207|0.367|4.1e-05|1.1e-05|6.3e+00|-8.505235e+01 -5.493833e+01| 0:0:00| chol  1  1
18|0.089|0.175|3.8e-05|9.0e-06|1.0e+01|-1.163163e+02 -6.707741e+01| 0:0:00| chol  1  1
19|0.190|0.370|3.0e-05|5.8e-06|1.7e+01|-1.443733e+02 -9.896742e+01| 0:0:00| chol  1  1
20|0.320|0.332|2.1e-05|3.9e-06|1.8e+01|-2.119288e+02 -1.325165e+02| 0:0:00| chol  1  1
21|0.162|0.376|1.7e-05|2.5e-06|2.2e+01|-2.584448e+02 -1.808308e+02| 0:0:00| chol  1  1
22|0.202|0.356|1.4e-05|1.6e-06|2.2e+01|-3.314437e+02 -2.299772e+02| 0:0:00| chol  1  1
23|0.344|0.161|4.7e-05|1.4e-06|4.2e+01|-3.969104e+02 -2.569729e+02| 0:0:00| chol  1  1
24|0.887|0.578|1.3e-05|6.1e-07|3.9e+01|-4.547742e+02 -3.620151e+02| 0:0:00| chol  1  1
25|0.576|0.681|1.2e-05|2.1e-07|3.6e+01|-4.924313e+02 -4.623949e+02| 0:0:00| chol  1  1
26|0.700|0.704|4.1e-06|6.6e-08|2.3e+01|-5.053863e+02 -5.017125e+02| 0:0:00| chol  1  1
27|0.975|1.000|4.8e-07|1.8e-09|8.6e+00|-5.121984e+02 -5.200563e+02| 0:0:00| chol  1  1
28|0.974|0.969|6.3e-07|1.2e-10|3.0e-01|-5.178249e+02 -5.180695e+02| 0:0:00| chol  1  1
29|0.990|0.979|5.2e-05|4.8e-12|1.1e-02|-5.179892e+02 -5.179980e+02| 0:0:00| chol
linsysolve: Schur complement matrix not positive definite
switch to LU factor. lu  2   1
30|0.958|0.978|5.9e-06|1.9e-13|4.2e-04|-5.179944e+02 -5.179948e+02| 0:0:00|
stop: relative gap < infeasibility
-------------------------------------------------------------------
number of iterations   = 30
primal objective value = -5.17994393e+02
dual   objective value = -5.17994783e+02
gap := trace(XZ)       = 4.18e-04
relative gap           = 4.03e-07
actual relative gap    = 3.76e-07
rel. primal infeas (scaled problem)   = 5.93e-06
rel. dual     "        "       "      = 1.93e-13
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual     "        "       "      = 0.00e+00
norm(X), norm(y), norm(Z) = 7.0e+07, 3.2e+03, 3.2e+03
norm(A), norm(b), norm(C) = 1.1e+01, 1.2e+00, 2.0e+01
Total CPU time (secs)  = 0.36
CPU time per iteration = 0.01
termination code       = -1
DIMACS: 5.9e-06  0.0e+00  2.7e-13  0.0e+00  3.8e-07  4.0e-07
-------------------------------------------------------------------

------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): +517.978
``````

If `t` is increased from `0.106309` by even a small amount,. the optimal objective (`0.16*gamasq1`) will greatly decrease.