search

qpsolvers / qpbenchmark

Benchmark for quadratic programming solvers available in Python
Apache License 2.0
110 stars 10 forks source link

Discrepancy in HPIPM evaluation: complementarity slackness vs duality gap #122

Open stephane-caron opened 6 days ago

stephane-caron commented 6 days ago

Issue reported by @giaf in https://github.com/qpsolvers/mpc_qpbenchmark/discussions/7#discussioncomment-10673601:

Strangely HPIPM success rate is lower at low accuracy, and it increases at mid and even more at high accuracy. This behavior doesn't appear for the other solvers. The reason seems to be the low percentage of problems where "solved" return codes are correct. Looking into the issue more carefully, it seems that the issue is related to the duality gap: the interfaces sets the solver 'max_res_comp' (i.e. the complementarity slackness) to a specified value, but then it accepts the solution as correct if the duality gap (instead of the complementarity slackness) is within that specified value. Complementarity slackness and duality gap are equivalent only for a feasible primal and dual point, but numerically this is true only approximately, and the approximation can be especially crude for the low accuracy case, where also primal and dual feasibility tolerances are set to low values.

stephane-caron commented 6 days ago

Thank you @giaf for raising this fine point on the difference between complementarity-slackness and duality-gap termination at low precision. The reason why qpbenchmark went with the duality gap as a termination condition is its availability in most solvers (it appeared a de facto standard).

I don't have other ideas to suggest at present, so I'm following up to your offer of adding an option for duality-gap termination in HPIPM: https://github.com/giaf/hpipm/issues/171 :wink: