Faster convex quadratic programming

Solve a dense convex quadratic program with inequality and equality constraints faster than CVXPY with the OSQP solver, reaching the same optimal value. Quadratic programs are the inner loop of model predictive control, portfolio optimization and sequential quadratic programming.

Task

Input: $P=M^\top M$ with $M\in\mathbb{R}^{n\times n}$, $q\in\mathbb{R}^n$, $G\in\mathbb{R}^{m\times n}$ and $A\in\mathbb{R}^{p\times n}$, all with independent standard normal entries, $m=p=\lfloor n/2\rfloor$, and $h=Gx_f+\lvert\xi\rvert$, $b=Ax_f$ for random standard normal $x_f$ and $\xi$, so that the problem is strictly feasible; in the benchmark $n=278$. Output: a solution $x$ of

$$\min_x\ \tfrac12x^\top Px+q^\top x\quad\text{subject to}\quad Gx\le h,\quad Ax=b.$$

An output is accepted when $Gx-h\le10^{-6}$ componentwise, $Ax$ matches $b$ under NumPy's allclose with absolute tolerance $10^{-6}$, and its objective is at most $p^\star+10^{-4}(1+\lvert p^\star\rvert)$, where $p^\star$ is the reference optimum. The reference solver is CVXPY with OSQP at absolute and relative tolerances $10^{-8}$.

Score: the reference's run time divided by the candidate's, averaged over the test instances; it is 1 if any output fails the check, and speed-ups below 1 count as 1. Higher is better.

Background

OSQP (Stellato et al., 2020) is an operator-splitting (ADMM) solver for convex quadratic programs; the reference also pays CVXPY's modelling overhead. Dense interior-point methods, active-set methods and warm-started splitting methods are all candidates for problems of this size, and the acceptance test only checks feasibility and the optimal value.

Data and evaluation

• Instances: 100 test and 100 development instances from the task's generator at $n=278$, in the AlgoTune dataset; the reference needs about 99 ms per instance on the authors' machine.
• Evaluation code: the AlgoTune harness (./algotune.sh evaluate in the repository), which runs the task's checker on every output.
• Hardware: speed-ups depend on the machine, so reference and candidate are timed in the same environment. The paper keeps the fastest of 10 timed runs per instance, each after a warm-up, on an AMD EPYC 9454 CPU with 14 GB of memory; agents had 8 cores, and compilation is not timed.

What is known

• Best on the AlgoTune leaderboard as of 2026-10-20: 1.89×, by the AlgoTuner agent driven by GPT-5, ahead of Claude Sonnet 4.5 (1.79×) and Claude Opus 4.1 (1.74×).
• Press et al. (2025) describe most agent speed-ups as surface-level: better library calls, better library usage or low-level rewrites, for example with Numba.

What would count as progress

• A solver beating 1.89× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
• A comparison of interior-point, active-set and splitting methods written directly against NumPy or LAPACK on these instances.

References

1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. arXiv:2507.15887
2. B. Stellato, G. Banjac, P. Goulart, A. Bemporad, S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathematical Programming Computation 12, 637–672 (2020). doi:10.1007/s12532-020-00179-2

Source

Imported from AlgoTune task qp, curated by Ori Press and the AlgoTune contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.