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]
Ad =[0.1 -0.1;0 0.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(n) zeros(n) -Q zeros(n,1) zeros(n,1) -Ad' Ad'*X zeros(n,1) zeros(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. 

Your LMI has two non-symmetries.

zeros(1) and eye(1) are not symmetric entries
-Ad’ and Ad 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]
Ad =[0.1 -0.1;0 0.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(n) zeros(n) -Q zeros(n,1) Ad' Ad'*X zeros(n,1) zeros(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(n) zeros(n) -Q zeros(n,1) Ad' Ad'*X zeros(n,1) zeros(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(n) zeros(n) -Q zeros(n,1) Ad' Ad'*X zeros(n,1) zeros(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.