google-deepmind/qtqp v0.0.7

qtqp 0.0.7

Repository: google-deepmind/qtqp

Tag: v0.0.7

Published: 2026-09-06T10:11:37Z

Prerelease: no

Release notes: qtqp 0.0.7 corrects how iterations are reported, fixes the embedding gate that decides between solutions and certificates, cuts the per-iteration Python overhead, and makes the warm-start screen and the dense backends cheaper and better documented. The benchmark against Clarabel below is a fresh sweep with both solvers counting completed interior-point steps.

Iteration counting (correction)

qtqp's iteration count was the zero-based index of the last logged row, one below the number of completed steps that other solvers report. Solution.iterations now reports completed IPM steps, excluding initialization and failed attempts, with or without collect_stats (#131); each stats row carries both the zero-based iter label and the running iterations count, and the verbose footer prints the total. The benchmark tables in the 0.0.6 release notes have been corrected in place; the effect was one iteration on every qtqp median and nothing else.

Benchmark against Clarabel 0.11.1 at matched termination criteria and matched linear algebra

Both solvers at the same criteria: all tolerances 1e-8, max_iter = 200, 1830 s wall clock per problem, and both on single-threaded qdldl-family LDLᵀ factorizations (qtqp's QDLDL backend; Clarabel's direct_solve_method = qdldl with one thread instead of its default multithreaded faer), so that times compare algorithms and implementations rather than factorization libraries. Both apply static regularization 1e-8; Clarabel additionally uses its default dynamic pivot perturbation. The sweep is on main at d217b8b, whose solver numerics are those of this release (#135 only changes how an initialization failure is reported). The NETLIB infeasible set now uses the true infeasible greenbea file, on which both solvers were run.

| | 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 / 152 | 93 / 91 | 0 / 1 | | almost solved (reduced tolerances) | 7 / 10 | 1 / 18 | 0 / 1 | 1 / 0 | | infeasibility or unboundedness certificate | 0 / 1\* | 0 / 0 | 0 / 1\* | 28 / 28 | | hit the iteration limit | 7 / 1 | 1 / 1 | 0 / 0 | 1 / 0 | | time limit or solver error | 0 / 0 | 1 / 3 | 0 / 0 | 0 / 0 | | median completed IPM steps (solved) | 12 / 13 | 18 / 18 | 20 / 20 | – / 55† | | median refinement steps per KKT solve | 0.45 / 1.29 | 0.39 / 1.18 | 0.33 / 1.54 | – / 1.27† | | shifted geometric mean time, s (shift 10) | 1.33 / 0.68 | 4.82 / 3.75 | 0.36 / 0.15 | 0.16 / 0.06 | | solved by both / only qtqp / only Clarabel | 126 / 5 / 0 | 151 / 20 / 1 | 91 / 2 / 0 | 0 / 0 / 1 | | median iteration ratio qtqp/Clarabel (both solved) | 0.89 | 1.00 | 1.00 | – | | median time ratio qtqp/Clarabel (both solved) | 3.6 | 1.8 | 2.9 | – |

\* Clarabel's certificates on POWELL20 (Maros-Meszaros) and dfl001 (NETLIB) are on problems that HiGHS solves to optimality. † One problem, not a distribution. Medians exclude the nine equality-only Maros-Meszaros problems that both initializations solve at zero steps.

qtqp solves more problems on every feasible collection. On the problems both solve it needs about 11% fewer steps on Maros-Meszaros and the same number on the LP collections, with about a third of the iterative-refinement work per KKT solve. Clarabel's shortfall is mostly its almost-solved endings (18 on MIPLIB), three 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). Both solvers certify the same 28 infeasible NETLIB problems.

Wall clock with matched linear algebra separates by size. On the largest instances the two solvers are within ten percent (supportcase10 1593 vs 1683 s, ex9 1104 vs 1169 s, opm2-z10-s4 548 vs 556 s, supportcase40 45 vs 50 s), because the factorization dominates and the two qdldl implementations cost the same; on small problems qtqp's per-iteration Python overhead dominates, which is what the geometric means and the per-problem median ratios of 1.8 to 3.6 measure. Those ratios were 2.6 to 5.6 in 0.0.6; the difference is the overhead work below. With each solver's default linear algebra (Accelerate for qtqp on macOS, Pardiso elsewhere; faer with all threads for Clarabel) the large instances are at parity.

Clarabel's dynamic regularization

Clarabel's qdldl backend perturbs pivots during the factorization and qtqp does not. Repeating the Clarabel sweep with the perturbation disabled (through dynamic_regularization_eps, since the enable flag is read only by the faer backend in 0.11.1) leaves all 138 Maros-Meszaros runs identical, aborts 17 linear programs on an exactly zero pivot in the endgame (15 MIPLIB relaxations, 25fv47 and gosh, where the active rows are linearly dependent), turns ten almost-solved endings into solved ones, and changes the iteration count on two of the 363 problems both runs solve; the median refinement counts are unchanged. So the refinement gap in the table is not an artifact of the perturbation. qtqp survives the same dependent rows because its factorized diagonal is max(mu, 1e-8) with mu part of the system it solves, so the cancellation regime is reached only once mu < 1e-8, and its GMRES refinement absorbs the damaged factorizations that then occur.

Static regularization

A sweep of min_static_regularization over 1e-6, 1e-7, 1e-9 and 1e-10 on the same collections keeps the default at 1e-8: larger values cost 60% to 200% more refinement per KKT system and lose endgames (129/161/93 and 130/164/93 solved at 1e-6 and 1e-7), smaller values solve three more LISWET instances but damage the dependent-row LPs (131/165/87 at 1e-9, 133/163/84 at 1e-10, with two lost certificates). The two failure sets are nearly disjoint, and iteration paths barely change; the constant only decides whether the endgame factorization is usable.

Algorithm

• Embedding gate in the working frame (#132). The gate that decides whether an iterate is on the...