YALMIP infers quadratic problem as conic

[zeeshan khan]

I use the latest version of YALMIP and MOSEK. I have a simple quadratic objective with linear equality constraints. YALMIP gives me the following output

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 9099
Cones : 1
Scalar variables : 10467
Matrix variables : 0
Integer variables : 15

Optimizer started.
Mixed integer optimizer started.
Threads used: 4
Presolve started.
Presolve terminated. Time = 13.83
Presolved problem: 10466 variables, 9063 constraints, 18279897 non-zeros
Presolved problem: 0 general integer, 15 binary, 10451 continuous
Clique table size: 5
BRANCHES RELAXS ACT_NDS DEPTH BEST_INT_OBJ BEST_RELAX_OBJ REL_GAP(%) TIME
0 1 0 0 NA 8.1966472636e-08 NA 94.7
0 1 0 0 1.3656467828e-01 8.1966472636e-08 100.00 334.8
0 1 0 0 8.0854508065e-02 8.1966472636e-08 100.00 827.5
Cut generation started.
0 2 0 0 8.0854508065e-02 1.3094923508e-06 100.00 1168.1
Cut generation terminated. Time = 179.67
10 13 5 3 8.0854508065e-02 1.3094923508e-06 100.00 1875.1

It takes too long. The same code, I ran in my friend's Mac laptop with somewhat older versions of YALMIP, MOSEK and Matlab. For the same problem (and code), he gets the following output

Problem
Name :
Objective sense : min
Type : QO (quadratic optimization problem)
Constraints : 4631
Cones : 0
Scalar variables : 5991
Matrix variables : 0
Integer variables : 15

Optimizer started.
Quadratic to conic reformulation started.
Quadratic to conic reformulation terminated. Time: 0.04
Mixed integer optimizer started.
Threads used: 4
Presolve started.
Presolve terminated. Time = 0.09
Presolved problem: 10466 variables, 9044 constraints, 75112 non-zeros
Presolved problem: 0 general integer, 15 binary, 10451 continuous
Clique table size: 5
BRANCHES RELAXS ACT_NDS DEPTH BEST_INT_OBJ BEST_RELAX_OBJ REL_GAP(%) TIME
0 1 0 0 NA 7.5010889879e-09 NA 0.9
0 1 0 0 8.7368995172e+00 7.5010889879e-09 100.00 1.9
0 1 0 0 1.0345133742e+00 7.5010889879e-09 100.00 4.3
Cut generation started.
0 2 0 0 1.0345133742e+00 7.5010889879e-09 100.00 5.7
Cut generation terminated. Time = 0.74
7 10 6 2 1.0155068171e+00 3.6612530424e-06 100.00 7.9
16 20 3 2 3.8085611918e-01 8.5668705719e-03 97.75 10.2
An optimal solution satisfying the relative gap tolerance of 1.00e-02(%) has been located.
The relative gap is 0.00e+00(%).
An optimal solution satisfying the absolute gap tolerance of 0.00e+00 has been located.
The absolute gap is 0.00e+00.

Objective of best integer solution : 3.808561191811e-01
Best objective bound : 3.808561191811e-01
Construct solution objective : Not employed
Construct solution # roundings : 0
User objective cut value : 0
Number of cuts generated : 0
Number of branches : 23
Number of relaxations solved : 27
Number of interior point iterations: 175
Number of simplex iterations : 0
Time spend presolving the root : 0.09
Time spend in the heuristic : 0.00
Time spend in the sub optimizers : 0.00
Time spend optimizing the root : 0.36
Mixed integer optimizer terminated. Time: 12.00

Optimizer terminated. Time: 12.60

Integer solution solution summary
Problem status : PRIMAL_FEASIBLE
Solution status : INTEGER_OPTIMAL
Primal. obj: 3.8085611920e-01 nrm: 2e+02 Viol. con: 1e-11 var: 0e+00 itg: 0e+00
Optimizer summary
Optimizer - time: 12.60
Interior-point - iterations : 0 time: 0.00
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: 27 time: 12.00

0.3809

His YALMIP infers it as quadratic problem and takes 12 seconds. Mine infers the same problem as Conic and takes 40 minutes.

Is this a version issue. Please guide me to the appropriate version

Thanks

[Johan Löfberg]

You would have to supply a reproducible example

I did some changes in the mosek interface in the last interface, so it is not unlikely that I messed something up

[Johan Löfberg]

Confirmed. Just revert back and use june version or earlier. I will fix this

[Johan Löfberg]

Hmm, due to a bug in the june version, which counter-acts another bug which is in all other versions, the june version is the only version that actually works as expected. Sometimes two wrongs makes right...In other words, Mosek MIQPs has almost always been solved as MISOCPs in YALMIP

Hence, june 12th version is the one you want until I've fixed this...

[Johan Löfberg]

Fixed in develop.

[zeeshan khan]

The following toy example from quadratic programming Documentation

x = [1 2 3 4 5 6]';
t = (0:0.02:2*pi)';
A = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)];
e = (-4+8*rand(length(t),1));
e(100:115) = 30;
y = A*x+e;
plot(t,y);

xhat = sdpvar(6,1);
residuals = y-A*xhat;
bound = sdpvar(length(residuals),1);
Constraints = [-bound <= residuals <= bound];

optimize([],residuals'*residuals);
x_L2 = value(xhat);

infers the quadratic problem as conic. The output is as follows

Problem
  Name                   :                
  Objective sense        : min            
  Type                   : CONIC (conic optimization problem)

  Constraints            : 7              
  Cones                  : 1              
  Scalar variables       : 8              
  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.00           
Lin. dep.  - number                 : 0              
Presolve terminated. Time: 0.03   

Problem
  Name                   :                
  Objective sense        : min            
  Type                   : CONIC (conic optimization problem)

  Constraints            : 7              
  Cones                  : 1              
  Scalar variables       : 8              
  Matrix variables       : 0              
  Integer variables      : 0              

Optimizer  - threads                : 4              
Optimizer  - solved problem         : the primal     
Optimizer  - Constraints            : 1
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 3                 conic                  : 3              
Optimizer  - Semi-definite variables: 0                 scalarized             : 0              
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                 after factor           : 1              
Factor     - dense dim.             : 0                 flops                  : 1.30e+01       
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME 
0   8.1e+00  1.8e+03  1.8e+03  0.00e+00   -4.642689611e+05  0.000000000e+00   1.0e+00  0.06 
1   2.5e-01  5.6e+01  1.2e+01  -9.67e-01  -3.172855604e+05  -4.309318157e+03  3.1e-02  0.17 
2   5.1e-02  1.2e+01  1.9e+00  -4.76e-01  -1.873123017e+05  -7.734495616e+03  6.4e-03  0.17 
3   1.2e-02  2.8e+00  4.0e-01  -2.10e-01  -1.142541247e+05  -7.975961663e+03  1.5e-03  0.19 
4   3.8e-03  8.6e-01  1.6e-01  1.87e-01   -6.362158487e+04  -1.325303579e+04  4.8e-04  0.19 
5   1.4e-03  3.1e-01  4.1e-02  -2.22e-01  -5.817301764e+04  -3.880270535e+03  1.7e-04  0.20 
6   2.4e-04  5.3e-02  4.2e-02  6.75e-01   -2.121694891e+04  -1.379814762e+04  2.9e-05  0.20 
7   2.8e-05  6.3e-03  7.9e-03  5.12e-01   -1.395015666e+04  -1.263851936e+04  3.5e-06  0.20 
8   1.5e-06  3.4e-04  1.6e-03  7.72e-01   -1.239402499e+04  -1.231194336e+04  1.9e-07  0.22 
9   5.8e-08  1.3e-05  3.4e-04  1.02e+00   -1.231156217e+04  -1.230856177e+04  7.2e-09  0.22 
10  4.0e-09  8.9e-07  8.9e-05  1.01e+00   -1.230818685e+04  -1.230798231e+04  4.9e-10  0.22 
11  1.1e-10  2.4e-08  1.5e-05  9.99e-01   -1.230793202e+04  -1.230792650e+04  1.3e-11  0.23 
12  2.9e-12  1.8e-09  1.2e-06  1.00e+00   -1.230792480e+04  -1.230792476e+04  1.0e-13  0.23 
Optimizer terminated. Time: 0.33   

Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -1.2307924805e+04   nrm: 8e+03    Viol.  con: 1e-09    var: 0e+00    cones: 4e-10 
  Dual.    obj: -1.2307924765e+04   nrm: 5e+04    Viol.  con: 0e+00    var: 2e-05    cones: 0e+00 
Optimizer summary
  Optimizer                 -                        time: 0.33   
    Interior-point          - iterations : 12        time: 0.25   

      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   

Yalmip infers it as a conic problem while it is a quadratic

[Sarmad Munir]

Hi Johan,

Did you manage to fix the bug? I am still facing similar issues i.e. mosek solves the linear objective optimization problem (c'x) swiftly whereas it is taking significantly more time to solve quadratic objective optimization problem (x'Qx).

[Johan Löfberg]

The bug was fixed and is in the develop branch

[Erling D. Andersen]

FYI: Internally Mosek translate QP and QPQCs to a conic problem before optimizing. 

Also note if you have a dense Q or Q=0 you will most likely make a huge difference in solution time.