google-deepmind/qtqp v0.0.6

v0.0.6

Repository: google-deepmind/qtqp

Tag: v0.0.6

Published: 2026-09-04T16:58:31Z

Prerelease: no

Release notes: qtqp 0.0.6 is the largest release since the solver was published. It adopts Clarabel's termination criteria so that results are directly comparable with Clarabel, replaces the initialization with Clarabel's, rescales the problem so the factorized KKT block stays unit-scaled, adds certified warm starts, Gondzio centrality correctors, an adaptive endgame step schedule and GMRES-based iterative refinement, and removes the unproven heuristics that had accumulated around the linear algebra. At matched tolerances it now solves more problems than Clarabel 0.11.1 on Maros-Meszaros, MIPLIB and NETLIB with fewer iterations and about a third of the refinement work per iteration.

Benchmark against Clarabel 0.11.1 at matched termination criteria

Both solvers at their defaults, which are now the same criteria: all tolerances 1e-8, max_iter = 200, 1830 s wall clock per problem, qtqp on the QDLDL backend. MIPLIB is the 173 MIPLIB 2017 root relaxations with MPS files under 20 MB. "Refinement steps" are extra factorization solves per KKT system beyond the first, averaged over a run; medians are over solved problems; the iteration ratio is the median over problems both solvers solve.

| | Maros-Meszaros (138) | MIPLIB (173) | NETLIB feasible (93) | NETLIB infeasible (29) | |---|---|---|---|---| | | qtqp / Clarabel | qtqp / Clarabel | qtqp / Clarabel | qtqp / Clarabel | | solved to 1e-8 | 131 / 126 | 171 / 151 | 93 / 91 | 1 / 2 | | almost solved (reduced tolerances) | 7 / 10 | 1 / 20 | 0 / 1 | 1 / 0 | | infeasibility or unboundedness certificate | 0 / 1\* | 0 / 0 | 0 / 1\* | 27 / 27 | | hit the iteration limit | 7 / 1 | 1 / 1 | 0 / 0 | 1 / 0 | | time limit or solver error | 0 / 0 | 1 / 2 | 0 / 0 | 0 / 0 | | median iterations (solved) | 10 / 12 | 17 / 19 | 19 / 20 | 50† / 48† | | median refinement steps per KKT solve | 0.44 / 1.31 | 0.39 / 1.21 | 0.33 / 1.54 | 3.92† / 1.68† | | shifted geometric mean time, s (shift 10) | 1.51 / 0.34 | 5.38 / 1.85 | 0.44 / 0.15 | 0.22 / 0.09 | | solved by both / only qtqp / only Clarabel | 126 / 5 / 0 | 150 / 21 / 1 | 91 / 2 / 0 | 1 / 0 / 1 | | median iteration ratio qtqp/Clarabel (both solved) | 0.80 | 0.91 | 0.93 | 1.19† |

\* Clarabel's certificates on POWELL20 (Maros-Meszaros) and dfl001 (NETLIB) are on problems that HiGHS solves to optimality. † One or two problems, not a distribution.

qtqp solves more problems on every feasible collection and, on the problems both solve, needs 7-20% fewer iterations and about a third of the iterative-refinement work per KKT solve. Clarabel's shortfall is mostly its almost-solved endings (20 on MIPLIB), two solver errors, and the two certificates on feasible problems; qtqp returns no certificate on any feasible collection. qtqp's own failures are the six LISWET instances and BOYD2 (refinement at its budget on near-singular endgame systems), cbs-cta (a step-size stall), cplex2 (an endgame divergence after reaching 1e-10 residuals; the problem has an optimal solution despite being in the infeasible collection) and ns1116954 (wall clock). Wall-clock times compare a Python implementation with a compiled one: per iteration qtqp is 3-6x slower than Clarabel on these collections. Both solvers certify the same 27 infeasible NETLIB problems.

Warm starts

Two experiments measure the new certified warm start. On a closed-loop model-predictive control sequence (8 states, 3 inputs, horizon 40, box constraints, 60 steps, each step a QP with 440 variables, 320 equality and 880 inequality rows) a cold start needs a median of 6 iterations per step, a warm start from the previous step's solution 3, and a warm start from that solution shifted forward by one stage 2, with the certificate accepting 59 of 59 shifted points. On the 224 Maros-Meszaros and feasible NETLIB problems qtqp solves cold, warm-starting a copy whose b and c entries are each perturbed by a relative amount up to δ from the unperturbed solution gives, over the copies both starts solve:

| δ | copies both solve | warm start accepted | median iterations cold / warm | median iteration ratio warm/cold | quartiles | |---|---|---|---|---|---| | 0 | 224 | 215 / 224 | 15 / 1 | 0.05 | 0.00 / 0.11 | | 1e-3 | 205 | 214 / 224 | 15 / 5 | 0.32 | 0.17 / 0.50 | | 1e-2 | 197 | 214 / 224 | 15 / 7 | 0.50 | 0.29 / 0.62 | | 1e-1 | 183 | 207 / 224 | 15 / 9 | 0.62 | 0.48 / 0.78 |

Copies the perturbation made infeasible or unbounded are excluded; on every one of them cold and warm starts return the same certificate. Nine of the non-accepted points at each level are the equality-only problems, on which the initialization solves the problem outright and the warm start is ignored. On no copy does a warm-started solve fail where the cold start succeeds.

Termination criteria and statuses (breaking)

• qtqp now uses Clarabel's termination criteria term for term (#122, #118, #110): relative primal and dual residuals normalized by max(1, ||b||_inf + ||x|| + ||s||) and max(1, ||c||_inf + ||x|| + ||y||), the duality gap tested absolutely or relative to max(1, min(|p|, |d|)), solutions accepted only when κ/τ ≤ 1, and certificates considered only when κ/τ > certificate_ktratio (default 1e9). Because qtqp eliminates κ through τκ = μ, the ratio is evaluated as μ/τ².
• The tolerance parameters are renamed to Clarabel's: tol_feas, tol_gap_abs, tol_gap_rel, tol_infeas_abs, tol_infeas_rel, all defaulting to 1e-8. The old atol, rtol, atol_infeas, rtol_infeas are gone.
• New statuses: SolutionStatus.ALMOST_SOLVED (#97, #98), returned with the best iterate meeting the same criteria at reduced tolerances (1e-4 feasibility, 5e-5 gap) when the iteration budget or the linear algebra stops progress, and SolutionStatus.HIT_MAX_ITER (#67). SolutionStatus.FAILED is now returned for numerical failures instead of an exception (#93).
• Infeasibility and unboundedness certificates are judged on the unit-slope ray with data-scaled residuals (#110, #118).

Algorithm

• Initialization (#99, #112, #123): the initial point is Clarabel's, the solution of [P, A'; A, -H][x; y] = [-c; b] with H the identity on inequality rows and zero on equality rows (separate primal and dual solves for LPs), shifted interior. Equality rows are satisfied exactly by the initial point, so problems with only equality constraints are solved at iteration 0 (#120, #123)....