google-deepmind/qtqp

google-deepmind/qtqp

Language: Python

License: Apache-2.0

Stars: 33

Forks: 4

Open issues: 2

Created: 2025-10-23T13:05:15Z

Pushed: 2026-05-31T14:32:08Z

Default branch: main

Fork: no

Archived: no

README:

QTQP


The cutie QP solver is a primal-dual interior point method for solving convex quadratic programs (QPs), implemented in pure python. It solves the primal QP:

min. (1/2) x.T @ p @ x + c.T @ x
s.t. a @ x + s = b
s[:z] == 0
s[z:] >= 0

With dual:

max. -(1/2) x.T @ p @ x - b.T @ y
s.t. p @ x + a.T @ y = -c
y[z:] >= 0

with data a, b, c, p, z and variables x, y, s. It returns a primal-dual solution when one exists, or a certificate of primal or dual infeasibility otherwise.

Installation

QTQP is available via pip:

python -m pip install qtqp

On supported platforms this also installs the recommended sparse CPU backend automatically:

• Linux / Windows x86_64: py-mkl-pardiso
• macOS arm64: macldlt

To install from source, first clone the repository:

git clone https://github.com/google-deepmind/qtqp.git
cd qtqp

Then, assuming conda is installed, create a new conda environment:

conda create -n tmp python=3.12
conda activate tmp

Finally, install the package:

python -m pip install .

To run the tests, inside the qtqp directory:

python -m pytest .

Tests for optional linear solvers are skipped when the corresponding dependencies are not installed.

Quick start

Here is an example usage (taken from here):

import qtqp
import scipy
import numpy as np

# Set up the problem data
p = scipy.sparse.csc_matrix([[3.0, -1.0], [-1.0, 2.0]])
a = scipy.sparse.csc_matrix([[-1.0, 1.0], [1.0, 0.0], [0.0, 1.0]])
b = np.array([-1, 0.3, -0.5])
c = np.array([-1.0, -1.0])

# Initialize solver
solver = qtqp.QTQP(p=p, a=a, b=b, c=c, z=1)
# Solve!
sol = solver.solve()
print(f'{sol.x=}')
print(f'{sol.y=}')
print(f'{sol.s=}')

You should see output similar to

| QTQP v0.0.3: m=3, n=2, z=1, nnz(A)=4, nnz(P)=4, linear_solver=SCIPY
|------|------------|------------|----------|----------|----------|----------|----------|----------|----------|
| iter | pcost | dcost | pres | dres | gap | infeas | mu | q, p, c | time |
|------|------------|------------|----------|----------|----------|----------|----------|----------|----------|
| 0 | 1.205e+00 | 1.298e+00 | 2.18e-01 | 6.17e-01 | 9.36e-02 | 1.67e+00 | 1.09e+00 | 1, 1, 1 | 1.61e-02 |
| 1 | 1.161e+00 | 1.211e+00 | 3.16e-02 | 5.23e-02 | 5.01e-02 | 1.35e+00 | 1.04e-01 | 1, 1, 1 | 1.66e-02 |
| 2 | 1.234e+00 | 1.235e+00 | 3.77e-04 | 8.61e-04 | 6.64e-04 | 1.30e+00 | 7.67e-03 | 1, 1, 1 | 1.70e-02 |
| 3 | 1.235e+00 | 1.235e+00 | 3.78e-06 | 8.62e-06 | 6.65e-06 | 1.30e+00 | 1.25e-04 | 1, 1, 1 | 1.74e-02 |
| 4 | 1.235e+00 | 1.235e+00 | 3.78e-08 | 8.62e-08 | 6.65e-08 | 1.30e+00 | 1.25e-06 | 1, 1, 1 | 1.78e-02 |
|------|------------|------------|----------|----------|----------|----------|----------|----------|----------|
| Solved
sol.x=array([ 0.29999999, -0.69999997])
sol.y=array([2.69999964e+00, 2.09999968e+00, 3.86572055e-07])
sol.s=array([0.00000000e+00, 7.13141634e-09, 1.99999944e-01])

API reference

Once installed QTQP is imported using

import qtqp

This exposes the main solver class qtqp.QTQP with constructor:

QTQP(
*,
a: scipy.sparse.csc_matrix,
b: np.ndarray,
c: np.ndarray,
z: int,
p: scipy.sparse.csc_matrix | None = None,
)

Arguments:

• a: (m×n) Constraint matrix.
• b: (m) RHS vector.
• c: (n) Cost vector.
• z: Number of equality constraints (size of the zero cone). Must satisfy

`0 ≤ z qtqp.Solution

Key parameters:

- `atol`, `rtol`: Absolute/relative stopping tolerances for optimality.
- `atol_infeas`, `rtol_infeas`: Thresholds for (primal/dual) infeasibility
detection.
- `max_iter`: Iteration cap.
- `step_size_scale` (0,1): Scale for line search step size to stay strictly
interior.
- `min_static_regularization`: Diagonal regularization on KKT for robustness.
- `max_iterative_refinement_steps`, `linear_solver_atol/rtol`: Control
iterative refinement of the linear solve. The default is 20 refinement
steps, counting the initial solve.
- `linear_solver`: (`qtqp.LinearSolver`) Choose the KKT solver backend (see
below).
- `verbose`: Print per-iteration table with key metrics.
- `equilibration_strategy`: Choose how problem data is scaled before the IPM
iterations. Defaults to `qtqp.EquilibrationStrategy.RUIZ`.
- `collect_stats`: If True, populate `Solution.stats` with per-iteration
diagnostics (sy, s/y statistics, complementarity, etc.). Defaults to False
for faster throughput.
- `init_strategy`: Choose the initial interior-point iterate. Defaults to
`qtqp.InitStrategy.TRIVIAL`.
- `init_mu_scale`: Positive scale used only by `qtqp.InitStrategy.ORTHANT` to
set the initial barrier parameter.
- `refinement_strategy`: Choose the iterative-refinement method used for KKT
solves. Defaults to `qtqp.RefinementStrategy.RICHARDSON`.
- `gmres_restart`: Restart length for `qtqp.RefinementStrategy.GMRES`.
Ignored by Richardson refinement.
- `central_path_exponent`: Positive exponent for the generalized central-path
residual equation. The default `1.0` is the standard central path.
- `fused_corrector_division`: If True, computes the Mehrotra corrector slack
update with one fused division. The default False preserves legacy
arithmetic.

#### Equilibration strategies

Choose one with the `equilibration_strategy` argument:

- `qtqp.EquilibrationStrategy.RUIZ`: Default. Ruiz equilibration on `A` and
`P`; `b` and `c` are scaled passively by the accumulated row/column
scalings.
- `qtqp.EquilibrationStrategy.AUGMENTED`: Ruiz equilibration on the symmetric
augmented matrix containing `P`, `A`, `b`, and `c`. This lets `b` and `c`
participate directly in the scaling and can improve reliability on
ill-scaled instances.
- `qtqp.EquilibrationStrategy.NONE`: Disable equilibration.

#### Initialization strategies

Choose one with the `init_strategy` argument:

- `qtqp.InitStrategy.TRIVIAL`: Default. Starts from `x = 0`, `tau = 1`, and
unit inequality components for `y` and `s`.
- `qtqp.InitStrategy.ORTHANT`: Closed-form non-negative orthant centering. It
uses `init_mu_scale *…