QCP problem: quadcon numerical issues

[Mads Almassalkhi]

Hi guys,

I have a questions about numerical stability / robustness of GUROBI's QCQP solver and it's dual. 

I have a relatively large non-convex problem with QCQP constraints of the form:

e(t) = [i(t)]^2 

that I relax as

e(t) >= [i(t)]^2.

With QCQP, I rarely find the optimal solution unless I lower the QCP tolerance below 1e-5, which makes it difficult to compute the dual solution:

....

Barrier solved model in 28 iterations and 8.32 seconds

Optimal objective -6.47025614e+04

Warning: failed to compute QCP dual solution due to inaccurate barrier solution.

However, I can also approximate the non-convex constraints with a PWL relaxation:

e(t) = weighted sum of PWL terms = sum_j {aj*iPWj(t)}

and the numerical issues vanish and optimal solution is easily and robustly recovered.

...

Barrier solved model in 19 iterations and 2.03 seconds

Optimal objective -5.98496613e+04

Is GUROBI's QCQP solver numerically hyper-sensitive or is there something else that could be going on? 

Also, assuming numerical issues can be alleviated with scaling or re-modeling, how "fast" should I expect general QCQP performance compared to an equivalent/approximate QP formulation? That is, is QCQP generally much slower than QP?

Thank you so much,

Mads

[Greg Glockner]

Hi Mads. My guess is that the model has numerical issues. Can you read the MPS file in Python and post the output of the Model.printStats() method?

> Also, assuming numerical issues can be alleviated with scaling or re-modeling, how "fast" should I expect general QCQP performance compared to an equivalent/approximate QP formulation? That is, is QCQP generally much slower than QP?

QCP is generally more difficult than QP, but there is no rule that estimates how much difficult.

[Mads Almassalkhi]

Hi Greg,

Below are the stats.

I went ahead and re-formulated my problem to significantly improve numerics. Here are the new stats for the PWL problem (QP):

Statistics for model GUROBI :

  Linear constraint matrix    : 38576 Constrs, 17199 Vars, 68795 NZs

  Matrix coefficient range    : [ 0.000484223, 1 ]

  Objective coefficient range : [ 20.2888, 51.7695 ]

  Variable bound range        : [ 0, 0 ]

  RHS coefficient range       : [ 0.0224523, 393 ]

which solves extremely fast now (used to be ~2s):

...

20  -3.74746682e+04 -3.74746683e+04  1.37e-09 1.09e-13  9.75e-10     0s

Barrier solved model in 20 iterations and 0.37 seconds

Optimal objective -3.74746682e+04

Here are the stats for the equivalent QCQP:

Statistics for model GUROBI :

  Linear constraint matrix    : 20432 Constrs, 8127 Vars, 31373 NZs

  Quadratic constraints       : 189 Constrs, 378 NZs

  Matrix coefficient range    : [ 8e-05, 1 ]

  Objective coefficient range : [ 20.2888, 51.7695 ]

  Variable bound range        : [ 0, 0 ]

  RHS coefficient range       : [ 0.00489437, 393 ]

which does NOT solve (to default optimality tolerances) and does not appear to be numerically onerous:

... 

81  -2.80600960e+04 -3.73870493e+04  2.25e+04 3.78e+03  4.51e-09     9s

Barrier performed 81 iterations in 8.76 seconds

Sub-optimal termination - objective -3.73870268e+04

Warning: failed to compute QCP dual solution due to inaccurate barrier solution

         Try decreasing BarQCPConvTol for more accuracy 

If you have any insights into why GUROBI does not solve this problem, I am all ears. One of my requirements is to be able to extract dual variables (shadow prices/Lagrange Multipliers) from the optimal solution. It seems like QCQP dual is even more sensitive than QCQP.

Thank you,

Mads

[Greg Glockner]

Mads:

We will contact you privately to get a copy of the model.


Thanks, Greg.

[Mads Almassalkhi]

Just to follow up briefly. I ran GUROBI's parameter tuning tool overnight on the MPS files I sent you. However, with all three sets, the solver returned "Sub-optimal solution.":

Tested 2263 parameter sets in 11489.56s

Baseline parameter set: runtime 6.08s

Improved parameter set 1 (runtime 4.00s):

ScaleFlag 0

QCPDual 1

PreDepRow 1

PrePasses 5

Improved parameter set 2 (runtime 4.08s):

ScaleFlag 0

PreDual 0

QCPDual 1

Improved parameter set 3 (runtime 4.31s):

ScaleFlag 0

QCPDual 1

[Mads Almassalkhi]

By any chance, did you get to look at the files I sent you? I am still unable to get OPTIMAL solution with QCP. 

Mads

[Greg Glockner]

Thanks for the reminder - we'll take a look at it.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[nazir...@gmail.com]

Hello. I am getting same issue with my SOCP model with Gurobi. Has there been any development regarding this problem.  

[Daniel Espinoza]

Hi Nazir,

Since 2015, sure, a lot has happened regarding imrpoved robustness... what issue are you facing? Which Gurobi version? Can you post a full log?

Best,

Daniel