Duality gap as a benchmark metric

[stephane-caron]

OSQP does not constrain the duality gap which can make it artificially faster, but in reality it's returning incorrect solutions, e.g. if the problem is strictly convex and thus a zero duality gap is part of optimality conditions.

@bodono discusses this in a paper:

Original context: bodono/scs-python#63 (comment)

[stephane-caron]

A consequence of this fact is that the solutions returned by some solvers can be severely sub-optimal. The benchmark shouldn't trust them to be optimal, and perform its own independent check.

Idea 1: the benchmark checks the duality gap directly

• Pro: we check all optimality conditions (c.f. e.g. this primer)
• Con: would require a significant qpsolvers upgrade (keep track of dual multipliers in all inequality/equality conversions)

[stephane-caron]

→ Going for it in #35

[stephane-caron]

Idea 2: check the cost error

Take the primal solution returned by a solver, compute the corresponding cost, compare it to the known optimum.

• Pro: optimal costs are already available for the Maros-Meszaros test set
• Pro: for future test sets, we could pre-compute "groundtruth" costs with a solver that provides strong guarantees like SCS (or aggregate solutions from multiple solvers)

[stephane-caron]

→ Preferring idea 1 to this alternative, see #35

[stephane-caron]

There is some follow-up to this discussion in the ProxQP documentation:

ProxQP provides the check_duality_gap option to include this duality gap in the stopping criterion. Note that it is disabled by default, as other solvers don't check in general this criterion. Enable this option if you want a stronger guarantee that your solution is optimal. ProxQP will then check the same termination condition as SCS (for more details see, e.g., SCS's optimality conditions checks as well as section 7.2 in the corresponding paper). The absolute and relative thresholds $\epsilon^{\text{gap}}_{\text{abs}}, \epsilon^{\text{gap}}_{\text{rel}}$ for the duality gap can differ from those $\epsilon_{\text{abs}}, \epsilon_{\text{rel}}$ for residuals because, contrary to residuals which result from an infinite norm, the duality gap scales with the square root of the problem dimension (thus it is numerically harder to achieve a given duality gap for larger problems). A recommended choice is $\epsilon^{\text{gap}}_{\text{abs}} = \epsilon_{\text{abs}} \sqrt{\max(n, n_{\text{eq}}, n_{\text{ineq}})}$. Note finally that meeting all residual and duality-gap criteria can be difficult for ill-conditioned problems.