'Solver not applicable problem' and 'Numerical Problems' errors using SDPT3 solver in Optimization

[Muhammad Yasir]

I am trying to solve and simulate a Stochastic Model Predictive Control (SMPC) based problem for sparse control transmission in a Networked Control System (NCS). For sparsity, we need to introduce a regularization term in the cost function that is based on L-1/L-infinity Mixed Induced Norm.

The optimization problem is shown below:

Where ETA_t is the offset vector and matrix F_t is given below

There are three parts to this problem:

1. Evaluation of covariance matrices through Monte Carlo Simulation
2. Evaluation of offset vector ETA_t and decision matrices THETA_t and LAMBDA_t by solving the optimization problems (17) and (18) with the sparsity-inducing term 
3. Once the offset vector and decision matrices are obtained through the above step, the optimization problems (17) and (18) are solved after the inclusion of the sparsity-inducing term. This should result in the generation of sparser control signals as compared with the signals generated in step 2.

I am using Yalmip SPDT3-4 solver :                     

ops = sdpsettings('solver','sdpt3','verbose',0);                     

sol_1 = optimize(constraints,objective,ops);

When I solve the optimization problem mentioned in step-2, I get the following messages:                     

'Successfully solved'

and sometimes the error message 'Numerical Problems' also pops up.

However, when I solve the complete optimization problem as mentioned in step-3 (with the inclusion of sparsity-inducing term), the following error message is shown:

'Solver not applicable problem'

This issue arises only after the inclusion of the sparsity-inducing terms in the optimization problem.

I have extensively gone through Yalmip help but I am unable to figure out the bug.

[Muhammad Yasir]

The debug messages for the problem mentioned in step-2, when we do not include sparsity-inducing terms in the optimization problem are :

When the problem is successfully solved

when we have 'Numerical problems ' for optimization problem mentioned in step-2:

While the debug messages for the optimization problem mentioned in step-3, when we include sparsity-inducing terms are :

[Johan Löfberg]

norm(sum norms) is not convex by propagation, hence you have to model it manually, i.e. create the outer model skipping the lower epigraph as it is redundant as the inner term is non-negative by design

numerical problems, well it is up to you to see what goes wrong, there is standard answer except crap in crap out, and that you might have a model with a degenerate solution space causing bad solution path

[Muhammad Yasir]

You mean to say that the norm function given in YALMIP/MATLAB is not applicable to the Stochastic MPC-based optimization problem, as the problem turns out to be non-convex.  I need to write my own norm function for this particular case ...?

Then why does the problem gets successfully solved when I solve the optimization problem without using the sparsity-inducing regularization term?

Also, to the best of my knowledge, I have modeled the problem as has been mentioned in the research paper. I am trying to reproduce the results published in the paper ...

Could you please elaborate a bit more on this issue? as I could not understand your point completely. 

It will be really nice of you! 

Thank you for your guidance ...

[Johan Löfberg]

norm(norm(a)+... does not satisfy simple convexity propagation rules, hence you cannot write that (well you can as in some cases yalmip will derive a MILP/MISOCP model, but that would just be unnecessarly complicated to do)

However, it is trivially convex as it is a special case where the argument to the outer norm is non-negative, hence just introduce t and norm(a)+.... <= t to replace the inf-norm

[Muhammad Yasir]

I have solved this optimization problem using the 'QUADPROG' solver and the results seem satisfactory according to the requirement. However, I am confused about when I use the command 'check(constraints)' ,why I am getting secondary residuals as 'NaN'.

Here is the output of the simulation run:

Nonlinear scalar (real, 1 variable)
Current value: 0.094644
Coefficients range: 1 to 1
Nonlinear scalar (real, 2 variables)
Current value: 2.8715
Coefficients range: 1 to 1
Nonlinear scalar (real, 3 variables)
Current value: 8.9755
Coefficients range: 1 to 1
Nonlinear scalar (real, 4 variables)
Current value: 23.551
Coefficients range: 1 to 1
rho_t
+ Solver chosen : BNB
+ Processing objective function
+ Processing constraints
+ Branch and bound started
* Starting YALMIP integer branch & bound.
* Lower solver   : QUADPROG
* Upper solver: rounder
* Max time: 3600
* Max iterations: Inf
 Node       Upper       Gap(%)     Lower     Open   Elapsed time
+ Calling QUADPROG
    1 :          Inf      Inf      3.391E+03   1       0.1    Successfully solved  
+ Calling QUADPROG
    2 :          Inf      Inf      3.391E+03   2       0.1    Successfully solved  
+ Calling QUADPROG
    3 :          Inf      Inf      3.391E+03   3       0.2    Successfully solved  
+ Calling QUADPROG
    4 :          Inf      Inf      3.391E+03   4       0.3    Successfully solved  
+ Calling QUADPROG
    5 :          Inf      Inf      3.391E+03   5       0.3    Successfully solved  
+ Calling QUADPROG
    6 :          Inf      Inf      3.391E+03   6       0.3    Successfully solved  
+ Calling QUADPROG
    7 :          Inf      Inf      3.391E+03   7       0.4    Successfully solved  
+ Calling QUADPROG
    8 :          Inf      Inf      3.391E+03   8       0.4    Successfully solved  
+ Calling QUADPROG
    9 :          Inf      Inf      3.391E+03   9       0.4    Successfully solved  
+ Calling QUADPROG
   10 :          Inf      Inf      3.391E+03  10       0.4    Successfully solved  
+ Calling QUADPROG
   11 :          Inf      Inf      3.391E+03  11       0.5    Successfully solved  
+ Calling QUADPROG
   12 :          Inf      Inf      3.391E+03  12       0.5    Successfully solved  
+ Calling QUADPROG
   13 :          Inf      Inf      3.391E+03  13       0.5    Successfully solved  
+ Calling QUADPROG
   14 :          Inf      Inf      3.391E+03  14       0.5    Successfully solved  
+ Calling QUADPROG
   15 :          Inf      Inf      3.391E+03  15       0.5    Successfully solved  
+ Calling QUADPROG
   16 :          Inf      Inf      3.391E+03  16       0.6    Successfully solved  
+ Calling QUADPROG
   17 :          Inf      Inf      3.391E+03  17       0.6    Successfully solved  
+ Calling QUADPROG
   18 :          Inf      Inf      3.391E+03  18       0.6    Successfully solved  
+ Calling QUADPROG
   19 :          Inf      Inf      3.391E+03  19       0.7    Successfully solved  
+ Calling QUADPROG
   20 :          Inf      Inf      3.391E+03  20       0.7    Successfully solved  
+ Calling QUADPROG
   21 :          Inf      Inf      3.391E+03  21       0.8    Successfully solved  
+ Calling QUADPROG
   22 :          Inf      Inf      3.391E+03  22       0.8    Successfully solved  
+ Calling QUADPROG
   23 :          Inf      Inf      3.391E+03  23       0.8    Successfully solved  
+ Calling QUADPROG
   24 :          Inf      Inf      3.391E+03  24       0.8    Successfully solved  
+ Calling QUADPROG
   25 :          Inf      Inf      3.391E+03  25       0.9    Successfully solved  
+ Calling QUADPROG
   26 :          Inf      Inf      3.391E+03  26       0.9    Successfully solved  
+ Calling QUADPROG
   27 :          Inf      Inf      3.391E+03  27       0.9    Successfully solved  
+ Calling QUADPROG
   28 :          Inf      Inf      3.391E+03  28       0.9    Successfully solved  
+ Calling QUADPROG
   29 :          Inf      Inf      3.391E+03  29       0.9    Successfully solved  
+ Calling QUADPROG
   30 :          Inf      Inf      3.391E+03  30       1.0    Successfully solved  
+ Calling QUADPROG
   31 :          Inf      Inf      3.391E+03  31       1.0    Successfully solved  
+ Calling QUADPROG
   32 :          Inf      Inf      3.391E+03  32       1.0    Successfully solved  
+ Calling QUADPROG
   33 :          Inf      Inf      3.391E+03  33       1.0    Successfully solved  
+ Calling QUADPROG
   34 :          Inf      Inf      3.391E+03  34       1.0    Successfully solved  
+ Calling QUADPROG
   35 :          Inf      Inf      3.391E+03  35       1.1    Successfully solved  
+ Calling QUADPROG
   36 :          Inf      Inf      3.391E+03  36       1.1    Successfully solved  
+ Calling QUADPROG
   37 :          Inf      Inf      3.391E+03  37       1.1    Successfully solved  
+ Calling QUADPROG
   38 :          Inf      Inf      3.391E+03  38       1.1    Successfully solved  
+ Calling QUADPROG
   39 :          Inf      Inf      3.391E+03  39       1.1    Successfully solved  
+ Calling QUADPROG
   40 :          Inf      Inf      3.391E+03  40       1.2    Successfully solved  
+ Calling QUADPROG
   41 :    3.440E+03     0.72      3.391E+03  12       1.2    -> Found improved solution!
+ Calling QUADPROG
   42 :    3.440E+03     0.72      3.391E+03  13       1.3    Successfully solved  
+ Calling QUADPROG
   43 :    3.440E+03     0.72      3.391E+03  14       1.3    Successfully solved  
+ Calling QUADPROG
   44 :    3.440E+03     0.72      3.391E+03  15       1.3    Successfully solved  
+ Calling QUADPROG
   45 :    3.440E+03     0.72      3.391E+03  16       1.4    Successfully solved  
+ Calling QUADPROG
   46 :    3.440E+03     0.72      3.391E+03  17       1.4    Successfully solved  
+ Calling QUADPROG
   47 :    3.440E+03     0.72      3.391E+03  18       1.4    Successfully solved  
+ Calling QUADPROG
   48 :    3.440E+03     0.72      3.391E+03  19       1.5    Successfully solved  
+ Calling QUADPROG
   49 :    3.440E+03     0.72      3.391E+03  20       1.5    Successfully solved  
+ Calling QUADPROG
   50 :    3.440E+03     0.72      3.391E+03  21       1.5    Successfully solved  
+ Calling QUADPROG
   51 :    3.440E+03     0.72      3.391E+03  20       1.6    Successfully solved  
+ Calling QUADPROG
   52 :    3.440E+03     0.72      3.391E+03  21       1.6    Successfully solved  
+ Calling QUADPROG
   53 :    3.440E+03     0.72      3.391E+03  22       1.6    Successfully solved  
+ Calling QUADPROG
   54 :    3.440E+03     0.72      3.391E+03  23       1.7    Successfully solved  
+ Calling QUADPROG
   55 :    3.440E+03     0.72      3.391E+03  24       1.8    Successfully solved  
+ Calling QUADPROG
   56 :    3.440E+03     0.72      3.391E+03  25       1.9    Successfully solved  
+ Calling QUADPROG
   57 :    3.440E+03     0.72      3.391E+03  26       1.9    Successfully solved  
+ Calling QUADPROG
   58 :    3.440E+03     0.72      3.391E+03  27       1.9    Successfully solved  
+ Calling QUADPROG
   59 :    3.440E+03     0.72      3.391E+03  28       2.0    Successfully solved  
+ Calling QUADPROG
   60 :    3.440E+03     0.72      3.391E+03  29       2.0    Successfully solved  
+ Calling QUADPROG
   61 :    3.440E+03     0.72      3.391E+03  30       2.0    Successfully solved  
+ Calling QUADPROG
   62 :    3.391E+03     0.00      3.391E+03   0       2.1    -> Found improved solution!
+  62 Finishing.  Cost: 3390.9332
Successfully solved
 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|   ID|               Constraint|                Primal residual|   Dual residual|
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|   #1|   Elementwise inequality|                15|                  NaN|
|   #2|   Elementwise inequality|           11.3238|             NaN|
|   #3|   Elementwise inequality|       -5.5511e-17|           NaN|
|   #4|   Elementwise inequality|           12.8307|             NaN|
|   #5|   Elementwise inequality|                15|                  NaN|
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| A primal-dual optimal solution would show non-negative residuals. |
| In practice, many solvers converge to slightly infeasible                     |
| solutions, which may cause some residuals to be negative.               |
| It is up to the user to judge the importance and impact of                  |
| slightly negative residuals (i.e. infeasibilities)                                        |
| https://yalmip.github.io/command/check/                                             |
| https://yalmip.github.io/faq/solutionviolated/                                       |
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
Are these results numerically valid and acceptable? However, simulation plots seem to show the desired plots ...

[Johan Löfberg]

Duals are not computed when solving problems with BNB

[Muhammad Yasir]

So you mean to say these results are numerically acceptable and there are no issues with this simulation ...

[Johan Löfberg]

if you trust the solver, it says it has solved the problem to 0% gap, and the constraint violations are essentially machine epsilon, i.e. a very simple problem to solve