qtqp 0.0.7

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 solution side or the certificate side compares y's with nu * tau^2. Since the scalars of #124 it had been evaluated with the unequilibrated y's over the working-frame tau^2, off by 1 / (sigma^2 gamma), which could turn a bounded QP into a false UNBOUNDED certificate. The gate and the reported ktratio now use the working-frame complementarity of the current iterate. On the benchmark it changed four iteration counts, all lower, and no statuses. Two tests were retargeted: an infeasible fixture at objective scale 1e10 is a solution under Clarabel's iterate-relative residuals and now runs at scale 1e4, where it returns its certificate; the forced-linearized-tau stress test accepts an iteration-limit stop on one unbounded seed.
• Warm-start screening (#134). The four candidate embeddings share A x and P x, so screening costs six matrix-vector products instead of fifteen, and an accepted candidate's score is reused as lambda_init. The documentation now describes the screen as what it is: an empirical local-residual score with threshold 100, not a distance certificate and not a no-slowdown guarantee; the theoretical bound needs eta = lambda / sqrt(mu) < 1 and is not used for acceptance.
• Product reuse (#129). The data-column products of the tau equation are computed once per iteration and shared by the predictor, corrector and Gondzio trials; the warm-start metric uses one P x product; three unused operator norms are gone.
• Initialization failures return FAILED (#135). A numeric failure in the initialization factorization, observed as an exactly zero QDLDL pivot on dependent equality rows when the static regularization is lowered, returned as an exception; it now returns FAILED with NaN arrays and zero completed steps. Usage errors raised there, such as a dense backend asked to initialize equality rows with zero regularization, still reach the caller.
• Initialization statistics are reset on every solve(), so an accepted warm start on a reused solver no longer reports the previous cold solve's factor applications (#133).

Performance

• Per-iteration Python overhead (#127): the KKT transpose is cached instead of rebuilt per matvec, GMRES buffers are allocated once, the Ruiz norms avoid sparse temporaries, and the diagonal index scan is vectorized. Bit-identical results; small problems 1.1 to 1.75 times faster (HS118 6.3 to 3.6 ms, QSC205 10.6 to 7.0 ms, AUG3DCQP 39 to 27 ms).
• Dense backends (#128) densify only the A and P blocks they use instead of the full (n + m)^2 KKT matrix: peak setup allocation at m = 5000, n = 20 drops from 205 MB to 6 MB.
• Dense backends raise a clear error when initialization is asked to run with zero regularization on equality rows, instead of propagating NaNs (#130).

Warm starts

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 7 completed steps per step, a warm start from the previous step's solution 4, and a warm start from that solution shifted forward by one stage 3, with the screen accepting 59 of 59 shifted points. On the 224 Maros-Meszaros and feasible NETLIB problems qtqp solves cold, warm-starting copies 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 (perturbations seeded per problem from the SHA-256 digest of its name, so they are reproducible):

δ	copies both solve	warm start accepted	median completed steps cold / warm	median ratio warm/cold	quartiles
0	224	215 / 224	16 / 2	0.12	0.07 / 0.19
1e-3	204	214 / 224	16 / 6	0.36	0.25 / 0.54
1e-2	196	213 / 224	16 / 8	0.52	0.36 / 0.67
1e-1	181	205 / 224	16 / 9	0.64	0.50 / 0.79

On no copy does a warm-started solve fail where the cold start succeeds; the screen vetoes at most ten of the 215 eligible points.

API

• Solution.iterations (new, default 0): completed IPM steps. Stats rows gain iterations; iter keeps its zero-based meaning.
• warm_start and warm_start_threshold documentation rewritten as above; lambda_init, delta_path and delta_path_local are described as guarded diagnostics rather than certified bounds.
• min_static_regularization must be positive for the dense backends on problems with equality rows.
• Reported statuses and solve counts are comparable with 0.0.6; iteration counts are one higher by construction.

All pull requests since 0.0.6

• README: refresh the quick-start output for 0.0.6 by @bodono in #126
• Cut per-iteration Python overhead: cached transpose, GMRES buffers, direct norms by @bodono in #127
• Avoid full KKT densification in dense backend setup by @bodono in #128
• Reuse invariant matrix products across Newton substeps by @bodono in #129
• Explain zero equality regularization errors in dense backends by @bodono in #130
• Report completed IPM steps separately from iteration labels by @bodono in #131
• Use working-frame complementarity for the embedding gate by @bodono in #132
• Reset initialization statistics for reused warm-start solves by @bodono in #133
• Reuse warm-start screening products and clarify heuristic guarantees by @bodono in #134
• Report initialization factorization failures as FAILED by @bodono in #135

Full Changelog: v0.0.6...v0.0.7