Minimization of an infinite norm objective function with linear constraints, where "linsysolve: Schur complement matrix not positive definite switch to LU factor" and "Status: Inaccurate/Solved" showed up

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

> 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

> 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  - 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!

Well, Mosek finds an almost optimal solution. Since the solution is quite feasible and has about 4 figures of accuracy in the objective value.

I do not know how CVX handles this:

Warning: The use of strict inequalities in CVX is strongly discouraged,
because solvers treat them as non-strict inequalities. Please

but I would definitely not use strict inequalities given that message.

1 Like

Also I see

For improved efficiency, Mosek is solving the dual problem.

Maybe if you can force Cvx to feed Mosek the primal you will get better numerical behaviour.
That happens occasionally.

1 Like

Really thanks for your answer! So actually, Mosek is close to the optimal solution, just because itâ€™s not the optimal, then it showed â€śfailedâ€ť?
I will change the strict inequalities to see the influence.
Thanks again!

SDPT3 produces a solution having objective value of essentially zero. If that solution satisfies the constraints, it is optimal, because we know the objective canâ€™t be negative. if so, and you donâ€™t consider it to be a proper solution, then your formulation is inadequate. I am guessing you donâ€™t have such giant or tiny input data values that would invalidate my preceding sentences, because Mosek does not warn about any such input data.

1 Like

I will look into it! I am quite new to cvx and mosek. About â€śforce cvx to feed mosekâ€ť, is there any guildance on how to implement this? Thanks!

I donâ€™t think there is a way to force CVX not to provide the dual to Mosek. Perhaps it can be done indirectly, I have no idea how, with some clever CVX formulation which will induce CvX to not send the dual.

I will defer to @Erling as to how, if at all, Mosek parameters can be set (using cvx_solver_serttings) to get Mosek to solve the dual of what it is provided, and whether that would be any good.

1 Like

Mosek is close to the optimal solution, just because itâ€™s not the optimal, then it showed â€śfailedâ€ť?

My personal opinion is that CVX does not process Mosek solutions having UNKNOWN UNKNOWN as it should. I believe in such case, CVX should return the optimal objective value and optimal values of CVX variables with an appropriate status, maybe less good sounding than â€śInaccruate solvedâ€ť, but not as drastic as â€śFailedâ€ť. Indeed, YALMIP makes the Mosek solution available in such case. But CVXâ€™s response to Mosekâ€™s being unsure of the outcome is NO SOUP FOR YOU!!.

1 Like

I think the solution of SDPT3 satisfied the constaints, because I checked the value of a w^H \quad \text{and} \quad a_o w^H. I think I just donâ€™t know why itâ€™s inaccurate. Sorry for not stating my problem clearly.

Also, the 1 in constraints a_o w^H < 1 actually is a vector, but I wrote it as a scalar 1. Is that ok?

MATLAB, and hence CVX, automatically convert 1 into an appropriate vector (of ones).

CVX and SDPT3 in this instance are not smart enough to realize the objective value canâ€™t possibly be negative. But a human, such as me, can. So if a solution achieving objective value zero is feasible, it must be optimal (although not necessarily unique).

There is something about your problem which is numerically difficult. I defer to @Erling for any deeper assessment of that.

1 Like

Thanks! I think I get your point!

Without seeing the problem I cannot say anything about why the problem causes issues.

That two optimizers have issues indicates that there is something in the problem that makes it hard.

So, in genral, MOSEK and SDPT3 both gave me solutions that close to optimal. And something in my problem makes it numerically difficult.

You can dump the problem to a file using

https://docs.mosek.com/9.2/faq/faq.html

email it to Mosek support for a comment if you like.

Thanks! I will try it.