Convex Quadratic Programming Solver

A research-oriented Python implementation of a primal-dual interior-point solver for convex quadratic programming, with a Django REST API.

Status

Metric	Value
Version	v0.2.0
Tests	84 passing (0 failing)
Coverage (source = solver)	93%
Lint / Format	ruff clean
Type check	mypy strict (solver, validation)
References	OSQP and Clarabel agreement

Problem

Minimize

$$ \min_{x \in \mathbb{R}^n} ; \frac{1}{2} x^T P x + q^T x \quad \text{s.t.} \quad A x = b, ; G x \le h, $$

where $P \succeq 0$ (symmetric positive semidefinite), $A \in \mathbb{R}^{m \times n}$, $G \in \mathbb{R}^{p \times n}$.

Method

• Primal-dual interior-point with a Mehrotra predictor-corrector step.
• Reduced KKT system solved via dense (NumPy) or sparse (SciPy SuperLU) factorization.
• Fraction-to-boundary step length and adaptive centering parameter.

Features

• Standard convex QP formulation with equality and inequality constraints.
• Primal-dual interior-point (basic) and Mehrotra predictor-corrector.
• KKT residual diagnostics: stationarity, primal feasibility, complementarity, duality gap.
• Dense and sparse KKT paths (scipy.sparse.linalg.splu / SuperLU).
• Input validation: shapes, symmetry, positive semidefiniteness, finiteness.
• Heuristic detection of infeasible and unbounded problems.
• Property-based tests (Hypothesis) and numerical validation corpus (100+ problems).
• Reference comparison against OSQP and Clarabel.
• CLI: cqp-solve problem.json.
• Django REST API with OpenAPI/Swagger.

Installation

python -m venv .venv
.\.venv\Scripts\Activate.ps1
pip install -e ".[dev]"

Quick Start

import numpy as np
from solver import QPProblem, solve

problem = QPProblem(
    P=np.eye(2),
    q=np.array([-2.0, -3.0]),
    A=np.zeros((0, 2)),
    b=np.zeros(0),
    G=np.array([[1.0, 1.0]]),
    h=np.array([2.0]),
)
result = solve(problem)
print(result.status, result.x, result.objective)

CLI

cqp-solve examples\halfplane.json

REST API

cd api
python manage.py migrate
python manage.py runserver

• GET /api/v1/health/ liveness probe
• GET /api/v1/version/ solver version
• GET /api/v1/examples/ example payloads
• POST /api/v1/solve/qp/ solve a convex QP
• GET /api/docs/ Swagger UI
• GET /api/schema/ OpenAPI schema

Testing

pytest
ruff check .
ruff format --check .
mypy .

Benchmarks

python -m benchmarks.run
python -m benchmarks.compare_reference

Results are written to benchmarks/results/.

Project Structure

solver/        optimization core (problem, validation, KKT, IPM, Mehrotra, diagnostics, CLI)
validation/    analytical examples and random QP generators
benchmarks/    size-scaling and reference-comparison harness
examples/      portfolio, resource allocation, SVM dual, MPC
api/           Django REST API (adapter layer)
docs/          mathematical and numerical documentation
tests/         unit, integration, property-based, and API tests

Documentation

• docs/mathematical-formulation.md
• docs/kkt-conditions.md
• docs/interior-point-method.md
• docs/mehrotra-algorithm.md
• docs/numerical-methods.md
• docs/validation.md
• docs/benchmarks.md
• docs/benchmark-report.md
• docs/architecture.md
• docs/audit.md
• docs/limitations.md

Related mathematical implementations

• Robust Statistical Learning studies numerical conditioning, solver stability, regularization, and reference validation.
• Event-Driven Metaheuristic Optimization examines dynamic constrained allocation and warm-start recovery with heuristic optimization methods.

These repositories address complementary mathematical problems; this solver does not depend on either project.

Automated releases

The release workflow validates the version in pyproject.toml, then runs Ruff lint and formatting checks, mypy, the test suite with coverage, a Docker health/version smoke test, reference-solver comparisons, and a Python distribution build. Successful releases attach the wheel and source distribution to the GitHub Release.

To prepare a future release, increment [project].version in pyproject.toml and merge to main, or push a matching vMAJOR.MINOR.PATCH tag. Existing tags are never moved or overwritten; a version that already has a tag must be advanced before it can be released from newer code. The release gate also runs the configured reference comparison against OSQP and Clarabel before packaging. Those checks are reproducible benchmarks, not a proof of correctness for every possible quadratic program.

License

MIT. See LICENSE.

Architecture

graph TD
    CLI[cqp-solve CLI] --> API
    REST[Django REST API] --> API
    API[solver.solve] --> IPM[ipm.py / mehrotra.py]
    IPM --> KKT[kkt.py / linear_solver.py]
    IPM --> RES[residuals.py]
    KKT --> PROB[problem.py / validation.py / exceptions.py]

Loading