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

variable w(1,J) complex
minimize( norm(H*w',inf) )
subject to
a*w' == 1;
abs(a_o*w') < 1;

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:
Platform: Windows/64-X86

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

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
consider using “<=” instead.

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

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

Thanks! I will try it.