CVX not finding minimum?

1

Hi,
I am currently trying to use CVX to solve an optimization problem. I already know an approximate bound for the solution from an alternative way of approaching the underlying problem, which is significantly below 1. Thus, I had expected obtaining solutions that are smaller or equal to my bound via CVX.

However, it seems like CVX only finds the solution 1, which surprised me (cvx_status is “solved”). Therefore, I manually tried what happens when I slightly change the optimal variables CVX determined, and found that this indeed gives a solution smaller than 1, while still satisfying all constraints.
This left me back puzzled and I do not know what I am doing wrong.

To ease debugging, I managed to break the whole issue down to a minimal (still-not-working-as-expected) example, which I attached below and also use to illustrate what I found.

In case it helps solving my issue, I am using CVX Version 2.2, Build 1148 on MATLAB R2023b on Windows 10.

I appreciate any help/advice to find out what I am doing wrong!

Thank you in advance!

clear
W1 = [[1 0 0 -2]; [0 0 0 0]; [0 0 0 0]; [-2 0 0 1]];
W2 = [[0 0 0 0];[0 0.5 0 0]; [0 0 0.5 0]; [0 0 0 0]];

w1sc = -1;
w2sc = 2.5E-8;

d = size(W1,1)/2;

aM = zeros(d,d);
aM(1,1) = 1;
M = kron(aM,eye(d));

cvx_solver SDPT3

cvx_begin

variable y0 
variable y1
variable z nonnegative

objf = y0+z*w1sc + y1 * w2sc

minimize objf

subject to
    y0 * eye(d^2) + z * W1 +y1*W2 - M >= 0

cvx_end

fprintf(“\n Result optimization: %f \n”, objf)
fprintf(“\n y0 = %f”, y0)
fprintf(“\n y1 = %f”, y1)
fprintf(“\n z = %f”, z)

fprintf(“\n-----------------------------\n”);
fprintf(“Let us slighly change the coefficients: \n”);

y0tilde = y0 - 0.01;
y1tilde = y1;
ztilde = z+0.012;

fprintf(“\n y0 → y0 - 0.01 = %f”, y0tilde)
fprintf(“\n y1 → y1 = %f”, y1tilde)
fprintf(“\n z → z + 0.012 = %f”, ztilde)

altRes = y0tilde + ztilde*w1sc + y1tilde * w2sc;
fprintf(“\n\n Then, the manually found result smaller than CVX result: %d < %d \n”, altRes, objf);

fprintf("\n while still all eigenvalues are positive: ")
eVals = eig(y0tilde * eye(d^2) + ztilde * W1 +y1tilde*W2 - M)

fprintf(“\n So, all constraints are still fulfilled - the manually found values should be still feasible (?)”)

2

You use the SDPT3. Have you tried other optimizers e.g. SeDuMi or Mosek?

I also suggest you post the log output.

3

Hi Thanks a lot for your quick reply!

Yes, I tried it with Mosek and SeDuMi as well - both find the solution 1 as well, although for different variables y0 = 1, y1=0, z=0.

However, the point y0 = 0.99, y1 = 35.0815, z = 0.1 I found manually still is a point that is feasible and gives a solution 0.89 <1. So, independently of the used solver, to me it seems like there are points that are not found (?)

The log output is:

Calling SDPT3 4.0: 6 variables, 3 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 3
dim. of linear var = 6

SDPT3: Infeasible path-following algorithms

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

0|0.000|0.000|1.5e+01|9.8e+00|6.0e+02| 2.000000e+01 0.000000e+00| 0:0:00| chol 1 1
1|0.978|0.951|3.4e-01|5.7e-01|2.9e+01| 8.878940e-01 -8.809103e+00| 0:0:00| chol 1 1
2|0.988|1.000|3.9e-03|1.0e-02|1.1e+00| 4.248787e-01 -3.955305e-01| 0:0:00| chol 1 1
3|0.967|0.992|1.3e-04|1.5e-03|8.9e-02| 4.237552e-02 -1.346735e-02| 0:0:00| chol 1 1
4|0.985|0.987|2.0e-06|1.3e-04|3.1e-03| 6.294563e-04 -7.888880e-05| 0:0:00| chol 1 1
5|0.989|0.989|2.2e-08|1.2e-05|1.7e-04| 6.979734e-06 1.118065e-05| 0:0:00| chol 1 1
6|0.992|0.995|2.2e-08|1.1e-06|1.2e-05| 7.763757e-08 5.486432e-07| 0:0:00| chol 1 1
7|0.989|0.989|2.3e-08|1.3e-08|1.5e-07| 8.515992e-10 -8.645125e-07| 0:0:00| chol 1 1
8|1.000|0.988|2.3e-08|1.8e-10|3.2e-09| 2.890836e-10 -8.771527e-07| 0:0:00| chol 1 1
9|1.000|0.987|2.3e-08|2.7e-12|6.3e-11| 6.963956e-12 -8.707272e-07| 0:0:00| chol 1 1
10|0.000|0.803|2.3e-08|9.7e-13|4.9e-02| 6.642613e-12 -3.328498e+03| 0:0:00| chol 1 1
11|1.000|0.000|2.6e-07|1.8e-12|6.0e+05| 8.153447e-03 -5.955298e+05| 0:0:00|
lack of progress in infeas

number of iterations = 11
primal objective value = 2.89083563e-10
dual objective value = -8.77152659e-07
gap := trace(XZ) = 3.23e-09
relative gap = 3.23e-09
actual relative gap = 8.77e-07
rel. primal infeas (scaled problem) = 2.32e-08
rel. dual " " " = 1.76e-10
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 8.9e+00, 3.5e+01, 2.6e+01
norm(A), norm(b), norm(C) = 4.4e+00, 3.2e+00, 2.4e+00
Total CPU time (secs) = 0.12
CPU time per iteration = 0.01
termination code = 0
DIMACS: 2.5e-08 0.0e+00 2.1e-10 0.0e+00 8.8e-07 3.2e-09

4

SDPT3 reports

My conclusion from the log output is SDPT3 is nowhere near solving your problem.

I suggest you add the constraints

y0 =0.99;
y1=35.06815;
z=0.1;

and see what happens when you optimize.

If the optimizers says infeasible

  • you are most likely wrong
  • or there is a bug in in cvx
  • or you have a nasty problem.
5

Your constraint is being interpreted as element-wise, not as an SDP constraint as you seem to want.

Change
cvx_begin
to
cvx_begin sdp
and the problem is solved as an SDP.

Or you can instead use
y0 * eye(d^2) + z * W1 +y1*W2 - M == semdefinite(d^2)

Both methods are discussed in
https://cvxr.com/cvx/doc/sdp.html

6

Thanks a lot! @Mark_L_Stone !

Very stupid mistake on my side - thanks for spotting!