Checking the duality gap for a stronger optimality guarantee

[stephane-caron]

Checking the duality gap is disabled by default, and ProxQP recommends to enable it for a stronger guarantee that the returned solution is optimal (this is documented in ProxQP with API examples). To illustrate this, I just ran into a small least squares where ProxQP's defaults yield a sub-optimal solution (not unwrapping the calls to the matrix-building API):

Code

import numpy as np
from qpsolvers import solve_ls

R = np.array([[1., 2., 0.], [-8., 3., 2.], [0., 1., 1.]])
s = np.array([3., 2., 3.])
G = np.array([[1., 2., 1.], [2., 0., 1.], [-1., 2., -1.]])
h = np.array([3., 2., -2.]).reshape((3,))

results = {
    "qpalm": solve_ls(R, s, G, h, solver="qpalm"),
    "proxqp_defaults": solve_ls(R, s, G, h, solver="proxqp"),
    "proxqp_check_duality_gap": solve_ls(
        R, s, G, h, solver="proxqp", check_duality_gap=True
    ),
}

for k, x in results.items():
    print(
        f"{k:25}: "
        f"objective={np.linalg.norm(R.dot(x) - s)**2:.1f}, "
        f"constraints_ok={np.all(G.dot(x) <= h)}"
    )

Results

qpalm                    : objective=10.8, constraints_ok=True
proxqp_defaults          : objective=15.4, constraints_ok=True
proxqp_check_duality_gap : objective=10.8, constraints_ok=True