Solver not converging on a solution for a convex optimization problem

[fumoboy007]

Hi! I am hoping you can help me understand why the solver is not converging for the attached optimization problem. Apologies in advance… my math is a little rusty, so I wasn’t able to read your paper. But from what I understand, your library is currently the state of the art.

The provided P matrix is positive semidefinite, so as far as I understand, there should be a solution. However, the solver did not converge after 100,000 iterations:

----------------------------------------------------------
                           PIQP                           
                    (c) Roland Schwan                     
   Ecole Polytechnique Federale de Lausanne (EPFL) 2024   
----------------------------------------------------------
dense backend
variables n = 100
equality constraints p = 1
inequality constraints m = 0
variable lower bounds n_lb = 100
variable upper bounds n_ub = 100

iter  prim_obj       dual_obj       duality_gap   prim_inf      dual_inf      rho         delta       mu          p_step   d_step
…
99999   -5.21808e+03   -5.21808e+03   4.59471e-03   6.80861e-14   1.55966e-05   1.000e-10   1.000e-10   1.390e-13   0.9900   0.9900

status:               max iterations reached
number of iterations: 100000
objective:            -5.21808e+03

Why didn’t it converge and are there some settings that I should be tweaking?

[RSchwan]

Hi,
Thanks for the bug report. It looks like your problem is extremely ill-conditions. Although your P is positive-semi-definite, the condition number is huge, i.e., the gap between the lowest and highest eigenvalues is orders of magnitudes. It turns out that internally, the linear solver has problems with this, i.e., due to the numerical issues it doesn't converge. But in your case prim_inf is basically zero, meaning that all constraints are satisfied, and your duality gap is also quite small compared to the objective function. Hence, I would assume that the solution is almost optimal.

I might have some ideas to make it more stable, but this might take some time... For now, I'll leave this issue open for future reference.