CVX shows the program is solved but one of the constraints is violated

1

Hi,

I ran a code using cvx on matrix inequalities and the cvx gives a output as “Solved” but when I check with the expression of constraints after running the code it clearly shows the constraint is violated. Please give me an insight on why this could be happenning.

PFB the code I am running. The violation is happenning in cvx program_3(constraint_2).

clear all;

clc;

close all;

format short;

Sigma1=diag([2.982e6 1.258e6 3.025e6 5.783e6]);

Sigma2=diag([4.212e19 4.116e19 3.859e19 3.553e19]);

[X,e] = polyeig(eye(4),Sigma1,Sigma2);

psi=[3.3211e7 4.0768e7 8.3982e7 3.1922e7];

D=[0.0052];

%D=[52];

E=[192.307];

min_eig = 0.001;

v=[1; 5; 3; 2; 9];

%v=[1; 400; 267; 35; 44];

%v=[32; 67; 54; 987; 20];

%v=[32; 67; 54; 987];

%v=X([1:4],8);

%v=[0.0078; 0.067; 0.0055; 1]

%v=[0.065; 0.0098; 0.077; 0.92]

%v=[1; 5; 3; 2; 9];

%program_1

cvx_begin

variable Gamma(1,5)

maximize(1);

subject to

{(psi')*Gamma*v>=zeros(4,1)

(psi')*Gamma*v<=zeros(4,1)

%Gamma(1,1)==2e9;

Gamma(1,1)==2e7;

%Gamma(1,1)==4425678;

%Gamma(1,1)==592e7;

}

cvx_end

%Program_2

cvx_begin sdp

variable D1(5,5) skew_symmetric

maximize(1);

subject to

{D1*v==zeros(5,1)

%D1*v<=zeros(5,1)

%D1(2,1)==1e5

D1(2,1)==54e4

%D1(3,2)==76e4

%D1(2,1)==22e8

%D1(1,2)==54e4

%D1(2,1)==96e6

%D1(2,1)==1e5

}

cvx_end

Y=(Gamma'*D*Gamma);

%Program_3

cvx_begin sdp

variable D2(5,5)

%Y=(Gamma'*D*Gamma);

%constraint_1

%[[Sigma2 (-(psi')*Gamma) zeros(4,1)]; [(-(Gamma')*psi) D2 Gamma']; [zeros(1,4) Gamma E]] > (min_eig * eye(10))

[[Sigma2 (-(psi')*Gamma) zeros(4,1)]; [(-(Gamma')*psi) D2 Gamma']; [zeros(1,4) Gamma E]] - (min_eig * eye(10)) == semidefinite(10)

%Constraint_2

%(D2-Y-(37.21e18*eye(5)))*v == 0

%(D2-(Gamma'*D*Gamma)-(39.69e18*eye(4)))*v == 0

(D2-Y-(43.56e18*eye(5)))*v == 0

%(D2-Y-(43.56e18*eye(5)))*v <= 0

cvx_end

When I run this code in matlab it says it’s solved. PFB the matlab output.

ans =

  3×1 cell array

    {1×1 cvxcnst}
    {1×1 cvxcnst}
    {1×1 cvxcnst}

Homogeneous problem detected; solution determined analytically.
Status: Solved
Optimal value (cvx_optval): +1
 

ans =

  2×1 cell array

    {1×1 cvxcnst}
    {1×1 cvxcnst}

Homogeneous problem detected; solution determined analytically.
Status: Solved
Optimal value (cvx_optval): +1
 
 
Calling SDPT3 4.0: 55 variables, 10 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 10
 dim. of sdp    var  = 10,   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.4e+02|2.2e+00|1.3e+22| 3.752000e+21  0.000000e+00| 0:0:00| chol  1  1 
 1|0.961|0.987|7.4e+00|3.0e-02|1.3e+21| 1.079199e+21  0.000000e+00| 0:0:00| chol  1  1 
 2|0.000|0.900|7.4e+00|3.0e-03|1.2e+22| 1.237024e+21  0.000000e+00| 0:0:00| chol  1  1 
 3|0.000|0.900|7.4e+00|3.0e-04|1.7e+22| 1.025749e+21  0.000000e+00| 0:0:00| chol  1  1 
 4|0.974|0.974|1.9e-01|7.7e-06|6.9e+20| 2.659358e+20  0.000000e+00| 0:0:00| chol  1  1 
 5|0.989|0.989|2.2e-03|8.6e-08|7.7e+18| 2.981517e+18  0.000000e+00| 0:0:00| chol  1  1 
 6|0.988|0.989|2.5e-05|9.6e-10|8.9e+16| 3.446217e+16  0.000000e+00| 0:0:00| chol  1  1 
 7|0.986|0.988|3.6e-07|1.1e-11|1.3e+15| 4.934552e+14  0.000000e+00| 0:0:00| chol  1  1 
 8|0.973|0.984|9.7e-09|1.7e-13|3.5e+13| 1.376880e+13  0.000000e+00| 0:0:00| chol  1  1 
 9|0.968|0.975|3.1e-10|8.6e-14|1.6e+12| 8.748723e+11  0.000000e+00| 0:0:00| chol  1  1 
10|0.967|0.983|1.0e-11|2.9e-14|5.4e+10| 3.091374e+10  0.000000e+00| 0:0:00| chol  1  1 
11|0.967|1.000|3.4e-13|1.1e-13|2.8e+09| 1.975856e+09  0.000000e+00| 0:0:00| chol  1  1 
12|0.989|1.000|3.8e-15|7.0e-14|3.1e+07| 2.212286e+07  0.000000e+00| 0:0:00| chol  1  1 
13|0.989|1.000|4.2e-17|4.1e-14|3.4e+05| 2.438488e+05  0.000000e+00| 0:0:00| chol  1  1 
14|0.989|1.000|4.6e-19|5.8e-14|3.7e+03| 2.687422e+03  0.000000e+00| 0:0:00| chol  1  1 
15|0.989|1.000|5.1e-21|1.0e-13|4.1e+01| 2.961709e+01  0.000000e+00| 0:0:00| chol  1  1 
16|0.989|1.000|5.6e-23|4.9e-14|4.5e-01| 3.263929e-01  0.000000e+00| 0:0:00| chol  1  1 
17|0.989|1.000|6.2e-25|5.8e-14|5.0e-03| 3.596921e-03  0.000000e+00| 0:0:00| chol  1  1 
18|0.989|1.000|6.8e-27|5.7e-14|5.5e-05| 3.963811e-05  0.000000e+00| 0:0:00| chol  1  1 
19|0.989|1.000|7.5e-29|5.9e-14|6.1e-07| 4.368046e-07  0.000000e+00| 0:0:00| chol  1  1 
20|0.989|1.000|8.3e-31|3.3e-14|1.1e-08| 8.914362e-09  0.000000e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 20
 primal objective value =  8.91436162e-09
 dual   objective value =  0.00000000e+00
 gap := trace(XZ)       = 1.08e-08
 relative gap           = 1.08e-08
 actual relative gap    = 8.91e-09
 rel. primal infeas (scaled problem)   = 8.26e-31
 rel. dual     "        "       "      = 3.33e-14
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 3.7e-12, 1.9e+22, 3.7e+22
 norm(A), norm(b), norm(C) = 1.5e+01, 1.0e+00, 1.3e+20
 Total CPU time (secs)  = 0.32  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 8.3e-31  0.0e+00  9.6e-14  0.0e+00  8.9e-09  1.1e-08
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -8.91436e-09

But When I check the constraint value it’s non-zero.

>> (D2-Y-(43.56e18*eye(5)))*v

ans =

           0
           0
           0
           0
    -8388608

If anyone has any idea as to why this is happenning, please give your feedback

2

The problem has horrendous numerical scaling, with input numbers as high as 4e19… Mosek provides warnings about this, and reports that the solver fails (Actually says:
“Problem status : UNKNOWN
Solution status : UNKNOWN” ).
SDPT3 and SeDuMi report that they succeeded, but either they got confused by the horrendous scaling, or viewed another way, the residuals are relatively small compared to the magnitudes of the input data. Because the problem is a feasibility problem, the solver need only find any primal feasible solution.

You need to rescale, by changing units or something, so that all non-zero input data is within a small number of orders of magnitude of one.

3

I tried to change the values and reduce the scaling but still cvx is unable to solve the constraints.

clear all;
clc;
close all;
format short;
Sigma1=diag([1.08 13.08 54.36]);
Sigma2=diag([2916 106929 820836]);
[X,e] = polyeig(eye(3),Sigma1,Sigma2);
psi=[11 41 51];
D=[0];
min_eig = 0.001;
v=[1; 1; 1; 1];
%v=[0.0092; 0.96; 0.0056; 0.045];
cvx_begin
variable Gamma(1,4)
(psi')*Gamma*v==zeros(3,1)
Gamma(1,1)==22;
cvx_end
cvx_begin
variable D1(4,4) skew_symmetric
D1*v==zeros(4,1)
D1(2,1)==54
cvx_end
Y=(Gamma'*D*Gamma);
cvx_begin sdp
variable D2(4,4)
[[Sigma2 (-(psi')*Gamma)]; [(-(Gamma')*psi) D2]] - (min_eig * eye(7)) == semidefinite(7)
(D2-(25*eye(4)))*v == 0
cvx_end

Still the problem is there. It’s unable to follow the constraints.

>> (psi')*Gamma*v

ans =

   1.0e-12 *

    0.0426
    0.1137
    0.1137

>> D1*v

ans =

   1.0e-14 *

   -0.0423
    0.3095
   -0.2671
         0

>> (D2-(25*eye(4)))*v

ans =

   1.0e-10 *

   -0.5821
         0
    0.5821
         0
4

Those are satisfied to within 1e-13, which is much better (smaller) than solver tolerance. You can’t expect better than this. You shouldn’t “expect” as good as this, although you might get it.