Recently, I was using CVX to solve a minimization problem based on beamforming, which can be formulated as,
\underset{w \in \mathbb{C}^{1\times N}}{\text{minimize}} \| H w^H \|_{\infty}
\text{subject to} \quad a w^H = 1
where matrix H \in \mathbb{C}^{M \times N} and vector a \in \mathbb{C}^{1\times N} were given.
It can be solved by CVX just fine, but as this is a beamforming problem, the output showed that constraint a w^H = 1 was not enough to make sure the main beam to steer at the angle where I interested. (a is the manifold of the angle we interest in.) Therefore, I add constraints $|a_o w^H| \lt 1$, where a_o \in \mathbb{C}^{32850\times N} is the manifold except the angle of main beam. Therefore, I hoped it can maximize the main beam of the angle we interested in.
Then, the problem was formulated as
cvx_begin
variable w(1,J) complex
minimize( norm(H*w',inf) )
subject to
a*w' == 1;
abs(a_o*w') < 1;
cvx_end
Then, the command showed,
Warning: The use of strict inequalities in CVX is strongly discouraged,
because solvers treat them as non-strict inequalities. Please
consider using "<=" instead.
> In < (line 21)
In Infinite_Solver_2 (line 10)
In Infinite_Norm (line 126)
Calling SDPT3 4.0: 131530 variables, 32947 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 32947
dim. of socp var = 98646, num. of socp blk = 32882
dim. of linear var = 32882
dim. of free var = 2 *** convert ublk to lblk
*******************************************************************
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|3.3e+04|2.6e+02|2.2e+09| 5.689787e+04 0.000000e+00| 0:0:02| spchol 1 1
1|0.945|0.483|1.8e+03|1.3e+02|1.7e+08| 2.660858e+05 -2.605909e+02| 0:0:04| spchol 1 1
2|0.930|0.572|1.3e+02|5.7e+01|1.2e+08| 1.447948e+06 -4.016923e+03| 0:0:08| spchol 1 1
3|0.953|0.612|6.0e+00|2.2e+01|6.0e+07| 1.853264e+06 -1.138702e+04| 0:0:12| spchol 1 1
4|1.000|0.705|8.1e-05|6.6e+00|2.5e+07| 2.433990e+06 -1.407040e+04| 0:0:15| spchol 1 1
5|1.000|0.540|3.4e-05|3.0e+00|1.4e+07| 2.604175e+06 -1.028176e+04| 0:0:21| spchol 1 1
6|1.000|0.850|6.6e-05|4.7e-01|3.8e+06| 2.204486e+06 -4.239839e+03| 0:0:24| spchol 1 1
7|0.998|0.995|3.4e-05|1.0e-02|4.3e+05| 4.151029e+05 -1.332577e+02| 0:0:28| spchol 1 1
8|0.986|0.988|2.2e-06|4.0e-03|6.4e+03| 6.121300e+03 -1.610922e+00| 0:0:32| spchol 1 1
9|0.983|0.983|5.7e-07|2.0e-03|1.3e+02| 1.101245e+02 -2.596288e-02| 0:0:35| spchol 1 1
10|0.968|0.836|1.3e-07|8.2e-04|9.2e+00| 6.069560e+00 -5.836902e-03| 0:0:40| spchol 1 1
11|0.910|0.689|1.9e-06|3.7e-04|2.6e+00| 1.762024e+00 -4.447488e-03| 0:0:45| spchol 3 3
12|0.952|1.000|1.9e-06|5.3e-05|8.7e-01| 7.742080e-01 -3.301505e-03| 0:0:49| spchol 3 3
13|0.570|0.459|2.4e-06|3.6e-05|5.2e-01| 4.718680e-01 -2.360860e-03| 0:0:54| spchol 3 3
14|0.188|0.300|2.3e-06|2.7e-05|4.4e-01| 4.110820e-01 -1.865405e-03| 0:0:58| spchol 3 3
15|0.343|0.393|2.1e-06|1.7e-05|3.4e-01| 3.178887e-01 -1.501984e-03| 0:1:02| spchol 3 3
16|0.600|0.377|1.7e-06|1.1e-05|2.2e-01| 2.102167e-01 -1.232737e-03| 0:1:06| spchol 3 3
17|0.784|0.458|7.7e-07|6.3e-06|1.2e-01| 1.114326e-01 -9.422457e-04| 0:1:09| spchol 3 3
18|0.489|0.400|5.9e-07|3.9e-06|8.3e-02| 7.733478e-02 -8.241664e-04| 0:1:13| spchol 4 4
19|0.925|0.547|3.0e-07|1.9e-06|3.2e-02| 2.878538e-02 -6.395769e-04| 0:1:16| spchol 5 5
20|0.560|0.355|5.7e-07|1.3e-06|2.0e-02| 1.748384e-02 -4.864576e-04| 0:1:20| spchol 6 7
21|0.784|0.605|3.6e-06|6.0e-07|8.8e-03| 7.933218e-03 -1.752094e-04| 0:1:24| spchol 7 7
22|0.346|0.143|4.9e-06|6.5e-07|6.9e-03| 6.032792e-03 -1.152224e-04| 0:1:27| spchol 7 6
23|0.114|0.403|4.8e-06|5.9e-07|6.4e-03| 5.626792e-03 -1.291323e-04| 0:1:32| spchol 7 7
24|0.269|0.470|4.2e-06|6.2e-07|5.7e-03| 4.846108e-03 -8.255444e-05| 0:1:36| spchol 7 7
25|0.281|0.050|3.6e-06|9.4e-07|5.2e-03| 4.110613e-03 -8.135088e-05| 0:1:40| spchol 7 7
26|0.731|0.782|3.4e-06|3.4e-07|2.0e-03| 1.636828e-03 -2.559093e-05| 0:1:44| spchol 7 8
27|0.786|0.353|4.6e-06|3.1e-07|1.3e-03| 9.178478e-04 -1.971537e-05| 0:1:47| spchol 9 10
28|1.000|0.660|3.8e-06|1.3e-07|3.9e-04| 2.455572e-04 -8.219419e-06| 0:1:51| spchol 16 16
29|0.730|0.551|7.9e-06|7.4e-08|2.3e-04| 1.554825e-04 -3.636544e-06| 0:1:55| spchol 20 19
30|0.534|0.386|4.3e-06|5.7e-08|1.7e-04| 1.117745e-04 -2.470812e-06| 0:1:59| spchol
linsysolve: Schur complement matrix not positive definite
switch to LU factor. splu 17 3
31|0.801|0.312|7.6e-06|4.6e-08|1.1e-04| 6.182776e-05 -1.795283e-06| 0:2:06| splu 30 9
32|0.554|0.352|9.4e-06|3.5e-08|7.9e-05| 4.260602e-05 -1.326513e-06| 0:2:12| splu 27 24
33|0.677|0.482|1.4e-05|2.1e-08|5.0e-05| 3.131637e-05 -8.471440e-07| 0:2:18| splu 11 30
34|0.449|0.280|7.4e-06|1.8e-08|3.8e-05| 2.154239e-05 -7.022830e-07| 0:2:24| splu 15 30
35|0.487|0.246|1.2e-05|1.6e-08|3.3e-05| 2.061399e-05 -6.631912e-07| 0:2:33| splu 19 30
36|0.358|0.581|5.7e-06|8.1e-09|2.3e-05| 1.329805e-05 -5.951497e-07| 0:2:40| splu 30 30
37|0.115|0.049|6.4e-06|9.2e-09|2.3e-05| 1.250049e-05 -5.942612e-07| 0:2:46| splu 11 30
38|0.044|0.046|6.0e-06|1.0e-08|2.4e-05| 1.297763e-05 -5.915119e-07| 0:2:53|
stop: steps too short consecutively
-------------------------------------------------------------------
number of iterations = 38
primal objective value = 1.32980509e-05
dual objective value = -5.95149726e-07
gap := trace(XZ) = 2.34e-05
relative gap = 2.34e-05
actual relative gap = 1.39e-05
rel. primal infeas (scaled problem) = 5.67e-06
rel. dual " " " = 8.09e-09
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 6.6e+02, 7.9e+01, 1.5e+02
norm(A), norm(b), norm(C) = 1.5e+03, 2.0e+00, 1.8e+02
Total CPU time (secs) = 172.73
CPU time per iteration = 4.55
termination code = -5
DIMACS: 5.7e-06 0.0e+00 7.4e-07 0.0e+00 1.4e-05 2.3e-05
-------------------------------------------------------------------
------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): +5.9515e-07
Then, I ran it in MOSEK, it showed,
Warning: The use of strict inequalities in CVX is strongly discouraged,
because solvers treat them as non-strict inequalities. Please
consider using "<=" instead.
> In < (line 21)
In Infinite_Solver_2 (line 10)
In Infinite_Norm (line 126)
Calling Mosek 9.1.9: 131530 variables, 32947 equality constraints
For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 32947
Cones : 32882
Scalar variables : 131530
Matrix variables : 0
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 - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.70
Lin. dep. - number : 0
Presolve terminated. Time: 2.13
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 32947
Cones : 32882
Scalar variables : 131530
Matrix variables : 0
Integer variables : 0
Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 65
Optimizer - Cones : 32883
Optimizer - Scalar variables : 98649 conic : 98649
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 1.25 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 2145 after factor : 2145
Factor - dense dim. : 0 flops : 4.07e+08
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.1e+01 1.0e+00 3.3e+04 0.00e+00 3.285000000e+04 0.000000000e+00 1.0e+00 5.13
1 1.6e+01 5.2e-01 1.2e+04 1.00e+00 1.723709565e+04 -4.440009180e-01 5.2e-01 5.75
2 7.5e+00 2.4e-01 4.2e+03 9.96e-01 8.389197223e+03 -7.022630467e-01 2.4e-01 6.06
3 1.3e-01 4.2e-03 3.9e+00 1.02e+00 1.423145224e+02 -7.137013049e-01 4.2e-03 6.72
4 1.7e-03 5.4e-05 5.6e-03 1.05e+00 1.772212574e+00 -8.989956363e-03 5.4e-05 7.20
5 1.7e-04 5.6e-06 4.1e-04 1.00e+00 1.806981006e-01 -2.815494863e-03 5.6e-06 7.70
6 1.2e-04 3.9e-06 2.4e-04 1.00e+00 1.278523160e-01 -1.808522912e-03 3.9e-06 7.92
7 9.0e-05 2.9e-06 1.6e-04 1.00e+00 9.494815381e-02 -1.195271006e-03 2.9e-06 8.14
8 5.2e-05 1.7e-06 6.8e-05 1.00e+00 5.430695531e-02 -8.559746259e-04 1.7e-06 8.42
9 3.1e-05 1.0e-06 3.2e-05 1.00e+00 3.279121452e-02 -5.961972716e-04 1.0e-06 8.80
10 6.2e-06 2.0e-07 2.9e-06 1.00e+00 6.427971926e-03 -1.247958891e-04 2.0e-07 9.27
11 5.4e-06 1.7e-07 2.4e-06 1.00e+00 5.672252509e-03 -9.985815747e-05 1.7e-07 9.55
12 5.4e-06 1.7e-07 2.3e-06 1.00e+00 5.591817026e-03 -1.048784919e-04 1.7e-07 9.81
13 3.2e-06 1.0e-07 1.1e-06 1.00e+00 3.331636758e-03 -7.099144209e-05 1.0e-07 10.06
14 8.2e-07 2.5e-08 1.3e-07 1.00e+00 8.046761594e-04 -1.310744713e-05 2.5e-08 10.52
15 8.2e-07 2.5e-08 1.3e-07 1.00e+00 8.046761594e-04 -1.310744713e-05 2.5e-08 11.55
16 8.2e-07 2.5e-08 1.3e-07 1.00e+00 8.046761594e-04 -1.310744713e-05 2.5e-08 12.80
17 7.8e-07 2.0e-08 9.5e-08 1.00e+00 6.636762207e-04 -1.079377247e-05 2.0e-08 13.52
18 7.5e-07 2.0e-08 8.9e-08 1.00e+00 6.345934410e-04 -1.031559354e-05 2.0e-08 14.16
19 7.5e-07 2.0e-08 8.9e-08 9.98e-01 6.344852980e-04 -1.031381164e-05 2.0e-08 15.34
20 7.4e-07 1.9e-08 8.6e-08 1.00e+00 6.205801933e-04 -1.008383986e-05 1.9e-08 17.53
21 7.4e-07 1.9e-08 8.6e-08 9.98e-01 6.172431042e-04 -1.002924128e-05 1.9e-08 18.19
22 7.4e-07 1.9e-08 8.6e-08 1.00e+00 6.172431042e-04 -1.002924128e-05 1.9e-08 18.95
23 7.4e-07 1.9e-08 8.6e-08 9.99e-01 6.172431042e-04 -1.002924128e-05 1.9e-08 19.67
Optimizer terminated. Time: 20.67
Interior-point solution summary
Problem status : UNKNOWN
Solution status : UNKNOWN
Primal. obj: 6.1724310407e-04 nrm: 9e+01 Viol. con: 7e-07 var: 0e+00 cones: 0e+00
Dual. obj: -1.0029241282e-05 nrm: 1e+00 Viol. con: 0e+00 var: 5e-13 cones: 0e+00
Optimizer summary
Optimizer - time: 20.67
Interior-point - iterations : 24 time: 20.53
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
Finally, although they both gave a solution of w that actually satisfied my demand (\|H w^H\|_{\infty} was minimized and the main beam was steered to the angle I interested in), SDPT3 provided an inaccurate output and MOSEK failed.
Does this mean my problem is poorly scaled or ill-conditioned? If it is, is it because my constraints are too harsh(especially the \|a_o w^H\| \lt 1)? Is it possible to optimize my problem to make it be solved accurately?
Thanks for any help!