Solved after the first iteration while Failed in the second iteration

1

Hi everyone. I have an iterative program that consists of a objective function and several constraints. In the iterative program, there are some initial points that have to be updated in each iteration. In each of the iterations several matrix variables should be derived and some of them should be used in next iteration as initial points. When I run the program for the first iteration, it status is solved as follows.

Calling Mosek 9.1.9: 2604 variables, 445 equality constraints

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 445
Cones : 225
Scalar variables : 1004
Matrix variables : 40
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.02
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 445
Cones : 225
Scalar variables : 1004
Matrix variables : 40
Integer variables : 0

Optimizer - threads : 6
Optimizer - solved problem : the primal
Optimizer - Constraints : 201
Optimizer - Cones : 113
Optimizer - Scalar variables : 432 conic : 339
Optimizer - Semi-definite variables: 40 scalarized : 3440
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 1.10e+04 after factor : 1.28e+04
Factor - dense dim. : 0 flops : 7.75e+06
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 9.8e+03 6.1e+02 3.4e+04 0.00e+00 3.356232330e+04 -7.552652810e+01 1.0e+00 0.05
1 5.8e+03 3.6e+02 2.6e+04 -9.97e-01 3.327410315e+04 -3.098845721e+02 5.9e-01 0.11
2 3.5e+03 2.2e+02 2.0e+04 -9.92e-01 3.439435193e+04 9.398977957e+02 3.6e-01 0.13
3 1.8e+03 1.1e+02 1.4e+04 -9.83e-01 3.904753972e+04 5.896479556e+03 1.8e-01 0.13
4 1.3e+03 8.1e+01 1.2e+04 -9.66e-01 2.950892979e+04 -3.365745875e+03 1.3e-01 0.14
5 5.7e+02 3.6e+01 7.6e+03 -9.42e-01 3.054210792e+04 -1.104312568e+03 5.7e-02 0.14
6 3.6e+02 2.2e+01 5.8e+03 -8.63e-01 3.002955202e+04 -3.077783477e+02 3.6e-02 0.16
7 1.9e+02 1.2e+01 3.8e+03 -7.74e-01 2.775782824e+04 2.540967377e+02 1.9e-02 0.16
8 6.8e+01 4.3e+00 1.6e+03 -5.80e-01 1.668655269e+04 -2.411973339e+03 6.9e-03 0.17
9 1.1e+01 7.1e-01 1.7e+02 7.82e-02 3.013151292e+03 -1.717762265e+03 1.1e-03 0.17
10 6.5e+00 4.1e-01 7.4e+01 9.50e-01 1.924293536e+03 -8.149163520e+02 6.5e-04 0.19
11 3.0e+00 1.8e-01 2.4e+01 9.22e-01 1.174480775e+03 -1.562443866e+02 3.0e-04 0.19
12 4.6e-01 2.8e-02 1.4e+00 9.46e-01 3.763250667e+02 1.649902056e+02 4.6e-05 0.20
13 3.3e-01 2.0e-02 1.1e+00 4.73e-01 4.117701548e+02 2.140896431e+02 3.3e-05 0.20
14 6.9e-02 4.3e-03 1.3e-01 7.59e-01 3.345187395e+02 2.859156484e+02 7.0e-06 0.22
15 2.3e-02 1.4e-03 3.7e-02 4.67e-01 3.465117307e+02 3.231796339e+02 2.4e-06 0.22
16 6.9e-03 4.3e-04 9.1e-03 4.27e-01 3.648100881e+02 3.544351708e+02 7.0e-07 0.23
17 5.6e-03 3.5e-04 7.4e-03 2.33e-01 3.736799510e+02 3.641912305e+02 5.7e-07 0.25
18 3.0e-03 1.9e-04 2.5e-03 9.25e-01 4.099308384e+02 4.051774618e+02 3.0e-07 0.25
19 2.7e-03 1.7e-04 2.1e-03 8.20e-01 4.237216317e+02 4.194191562e+02 2.8e-07 0.27
20 1.3e-03 8.2e-05 7.6e-04 9.33e-01 4.381946785e+02 4.360238480e+02 1.5e-07 0.27
21 1.3e-03 8.2e-05 7.6e-04 9.11e-01 4.381946785e+02 4.360238480e+02 1.5e-07 0.28
22 1.3e-03 8.2e-05 7.6e-04 9.12e-01 4.381946785e+02 4.360238480e+02 1.5e-07 0.30
23 2.0e-04 1.3e-05 4.6e-05 9.20e-01 4.441516095e+02 4.438064371e+02 2.4e-08 0.30
24 5.3e-05 3.3e-06 6.3e-06 9.87e-01 4.450636927e+02 4.449736655e+02 6.1e-09 0.31
25 1.2e-05 7.8e-07 7.6e-07 9.97e-01 4.454920322e+02 4.454707767e+02 1.4e-09 0.31
26 5.5e-06 3.4e-07 2.3e-07 1.00e+00 4.457012213e+02 4.456918746e+02 6.4e-10 0.33
27 1.2e-06 7.5e-08 2.4e-08 1.00e+00 4.459704177e+02 4.459683626e+02 1.5e-10 0.33
28 5.0e-07 3.1e-08 6.4e-09 1.00e+00 4.461609462e+02 4.461601036e+02 6.4e-11 0.34
29 1.8e-07 3.6e-08 5.8e-10 1.00e+00 4.464157575e+02 4.464155914e+02 1.7e-11 0.34
30 1.8e-07 1.4e-07 1.3e-10 1.00e+00 4.466148728e+02 4.466148128e+02 1.2e-11 0.36
31 1.8e-07 4.2e-07 1.2e-11 1.00e+00 4.468771314e+02 4.468771228e+02 6.5e-12 0.36
32 1.8e-07 6.7e-07 2.7e-12 1.00e+00 4.470980049e+02 4.470980027e+02 4.5e-12 0.38
Optimizer terminated. Time: 0.39

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 4.4709800492e+02 nrm: 1e+04 Viol. con: 4e-03 var: 0e+00 barvar: 0e+00 cones: 0e+00
Dual. obj: 4.4709800266e+02 nrm: 1e+10 Viol. con: 0e+00 var: 6e-06 barvar: 9e-13 cones: 4e-23
Optimizer summary
Optimizer - time: 0.39
Interior-point - iterations : 32 time: 0.38
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Solved
Optimal value (cvx_optval): +496.964

Some cvx variables obtained at the first iteration are used as initial value for the second iteration. While the status of the second iteration is Failed as follows.

Calling Mosek 9.1.9: 2604 variables, 445 equality constraints

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 445
Cones : 225
Scalar variables : 1004
Matrix variables : 40
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 20
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.03
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 445
Cones : 225
Scalar variables : 1004
Matrix variables : 40
Integer variables : 0

Optimizer - threads : 6
Optimizer - solved problem : the primal
Optimizer - Constraints : 201
Optimizer - Cones : 113
Optimizer - Scalar variables : 432 conic : 339
Optimizer - Semi-definite variables: 40 scalarized : 3440
Factor - setup time : 0.01 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 1.10e+04 after factor : 1.28e+04
Factor - dense dim. : 0 flops : 7.75e+06
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 9.8e+03 3.0e+07 2.1e+09 0.00e+00 2.121017357e+09 -7.552652810e+01 1.0e+00 0.06
1 5.8e+03 1.7e+07 1.6e+09 -1.00e+00 2.121007994e+09 -9.395241560e+03 5.9e-01 0.17
2 3.6e+03 1.1e+07 1.3e+09 -1.00e+00 2.120995195e+09 -2.214735021e+04 3.7e-01 0.17
3 5.2e+02 1.6e+06 4.9e+08 -1.00e+00 2.120801451e+09 -2.151724081e+05 5.4e-02 0.19
4 1.1e+02 3.3e+05 2.2e+08 -1.00e+00 2.119976824e+09 -1.035673424e+06 1.1e-02 0.19
5 2.3e+01 6.9e+04 1.0e+08 -1.00e+00 2.116164792e+09 -4.827129064e+06 2.4e-03 0.20
6 5.1e+00 1.5e+04 4.8e+07 -1.00e+00 2.099120973e+09 -2.177745353e+07 5.2e-04 0.20
7 2.2e+00 6.7e+03 3.2e+07 -1.00e+00 2.071237397e+09 -4.949791682e+07 2.3e-04 0.22
8 1.3e+00 3.9e+03 2.4e+07 -1.00e+00 2.042966711e+09 -7.726850555e+07 1.7e-04 0.22
9 4.8e-01 1.5e+03 1.5e+07 -9.98e-01 1.977297790e+09 -1.367318383e+08 6.2e-05 0.23
10 8.1e-02 2.4e+02 6.1e+06 -9.89e-01 1.714914702e+09 -3.307922127e+08 1.1e-05 0.23
11 1.7e-02 5.1e+01 2.5e+06 -9.19e-01 1.374701589e+09 -3.914947205e+08 2.3e-06 0.25
12 1.0e-02 3.0e+01 1.6e+06 -5.54e-01 1.237524946e+09 -2.277290076e+08 1.4e-06 0.27
13 9.1e-03 2.7e+01 1.4e+06 4.32e-02 1.222356898e+09 -1.117817025e+08 1.3e-06 0.27
14 8.0e-03 2.4e+01 1.4e+06 -1.47e-01 9.709656981e+08 -4.875560062e+08 1.2e-06 0.28
15 3.2e-03 9.5e+00 5.4e+05 -2.90e-01 6.053942657e+08 -2.934299934e+08 4.6e-07 0.28
16 1.4e-03 4.1e+00 1.8e+05 3.92e-01 3.156428342e+08 -1.506911270e+08 2.1e-07 0.30
17 6.0e-04 1.8e+00 5.6e+04 6.52e-01 1.552073542e+08 -6.718096235e+07 9.2e-08 0.30
18 2.8e-04 8.4e-01 1.9e+04 8.26e-01 7.910801764e+07 -2.980227286e+07 4.2e-08 0.31
19 7.0e-05 2.1e-01 2.6e+03 9.18e-01 1.988323911e+07 -7.643183072e+06 1.0e-08 0.31
20 1.9e-05 5.6e-02 3.6e+02 1.00e+00 4.829637030e+06 -2.472946405e+06 2.5e-09 0.33
21 1.0e-05 3.1e-02 1.3e+02 1.16e+00 2.089467233e+06 -1.526495100e+06 1.4e-09 0.33
22 8.2e-06 2.5e-02 8.2e+01 1.53e+00 1.422171607e+06 -1.054264060e+06 1.1e-09 0.34
23 7.5e-06 2.2e-02 7.0e+01 1.49e+00 1.200966910e+06 -9.790681213e+05 1.1e-09 0.34
24 5.3e-06 1.6e-02 3.2e+01 1.84e+00 6.332118206e+05 -5.054880925e+05 8.4e-10 0.36
25 5.3e-06 1.6e-02 3.2e+01 2.24e+00 6.332118206e+05 -5.054880925e+05 8.4e-10 0.38
26 5.3e-06 1.6e-02 3.2e+01 2.22e+00 6.332118206e+05 -5.054880925e+05 8.4e-10 0.39
Optimizer terminated. Time: 0.47

Interior-point solution summary
Problem status : ILL_POSED
Solution status : PRIMAL_ILLPOSED_CER
Dual. obj: -5.1142476907e-01 nrm: 1e+07 Viol. con: 0e+00 var: 1e-06 barvar: 3e+01 cones: 0e+00
Optimizer summary
Optimizer - time: 0.47
Interior-point - iterations : 27 time: 0.41
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Failed
Optimal value (cvx_optval): NaN

So I checked the feasibility of each constraints after the first iteration and I found that all the constraints are satisfied except a semidefinite constraints. The semidefinite constraint requires a matrix (Mat_semidef) that consists of cvx variables cjk and djk to be semidefinite (The values of cjk and djk are used in the next iteration). While one of the eigenvalues of the matrix is smaller than 0.

Mat_semidef(1,1,:)=reshape(cjk,1,JK);
Mat_semidef(1,2,:)=reshape(djk,1,JK);
Mat_semidef(2,1,:)=reshape(djk,1,J*K) ;
Mat_semidef(2,2,:)= reshape(F’.*ones(J,K).repmat(sum(var_g2wv,1),[J,1])+[sum(var_g2ww,1)-var_g2ww1;sum(var_g2ww_1,1)-var_g2ww1_1]+noise_uk,1,JK);

eig(Mat_semidef(:,:,2))
ans =
-0.0000
0.0787

Here, the first eigenvalue is

-4.19699360204199e-10

which is a very small value.

So I wonder if the semidefinite constraints is the reason why I obtain Failed status. I modified the tolerance by setting cvx_precision high or medium or low and it doesn’t works well.

Thank you.

2

maybe you use SCA algorithm to solve the non-convex question, I have met such problem.maybe you shuould changed the initial value into an appropriate scale or use other solver such as fmincon,which is is the toolbox of MATLAB

4

Thank you for your kindly reply.

You are right, I used the SCA algorithm to convexify the non-convex objective function. I checked the initial value again and I found that I missed checking the semidefinite constraint. The initial Mat_semidef_t has negative eigen value, e.g., -2.57505692337446e-10.

So I think the initial value of Mat_semidef_t is not feasible although CVX outputs a solved optimal value. I will try to generate a feasible initial value and see if it works.

Thank you again!

5

If your name and abilities do not happen to be Stephen Boyd, (crude, unsafeguarded) Sequential Convex Optimization (SCA) often doesn’t work well, and you’d be better served by using a high quality local or global optimizer, for instance under YALMIP.

However, if you need an n by n matrix, X, to not have even slightly negative eigenvalues, you can change the semidefinite constraint to
X - smallpositivenumber*eye(n) == semidefinite(n)
or if using sdp mode,
X - smallpositivenumber*eye(n) >= 0
where smallpositivenumber is a small, but not too small, positive number, such as 1e-6, 1e-7, or maybe 1e-8.

6

Thank you for your kindly reply and suggestions.

I think adding a small positive number is an appropriate solution to the semidefinite constraint. Thank you so much!