Certificates and primal recovery¶

What is certified¶

For a maximization problem, res.bound is an upper bound on the optimum of your problem: for every feasible \(x\), \(f(x)\le U(\theta)\), where \(\theta\) is the dual point at the best iterate. This holds for every \(\theta\), not only at convergence, because the dual constraint (a polynomial identity) is satisfied by construction and the positive semidefiniteness of the Gram matrices is restored by a spectral shift whose cost is added to the bound (see Theory in brief). For a minimization problem res.bound is a lower bound.

Two caveats, both important:

The box must contain the feasible set (see Modeling problems).
Floating point. res.bound is exact up to the error of the dense symmetric eigensolver (about \(10^{-12}\) relative in our tests). If you need a bound that is valid in exact arithmetic, use res.rigorous().

The rigorous certificate¶

import itertools
import moment_sos as po

s = po.variables(6)
cut = sum((1 - s[i]*s[j]) / 2 for i, j in itertools.combinations(range(6), 2))
res = po.solve(po.Problem(cut, boolean=True), order=2)

out = res.rigorous()
print(out["ok"], out["bound"], out["time"])

rigorous() replaces the floating-point \(\lambda_{\min}\) by a verified lower bound (a Cholesky factorization of the shifted matrix with a rigorous rounding-error allowance, following Higham) and evaluates the polynomial-identity residual in exact rational arithmetic. The returned dictionary has bound (the verified bound for your problem), U_rig, ok (whether every block was verified) and time. It certifies the normalized floating-point problem that Problem stores: rescaling the box to \([-1,1]^n\) rounds the coefficients, and this rounding is not accounted for. For data that stay exact, such as unit-weight MAX-CUT, the statement is exact. It was run up to blocks of size 821 in our experiments.

Primal recovery and optimality proofs¶

x, value = res.round()

round() recovers a feasible point from the dual iterate (for Boolean problems: random rounding of the recovered moment vectors plus 1-flip local search; for continuous problems, the recovered first moments, checked for feasibility). It returns (None, None) if no feasible point is found. Its value is a lower bound for a max problem, so together with res.bound it brackets the optimum:

\[\text{value}\ \le\ f^\star\ \le\ \text{res.bound}.\]

If the optimum is an integer (e.g. unit-weight MAX-CUT) and floor(res.bound) == value, value is proved optimal. This is how all 60 generated and all 5 real Biq Mac g05_60 instances in our benchmarks were certified.

Note

The bracket can be loose for relaxations that are not tight. On the Biq Mac torus instance t2g10 the relative gap between the best cut and the order-2 bound is 3.0%, so no optimality proof is obtained there.

Bound versus relaxation value¶

res.bound is a bound on the POP optimum \(f^\star\) and is at least the order-\(r\) relaxation value \(\rho_r\) (up to the solver accuracy). If you want to reproduce \(\rho_r\) to high accuracy use solve_alm and compare with the interior-point reference po.solve_dual_ipm(res.relaxation) on problems small enough for it.