Cvxium#

Cvxium (pronounced “calcium”) builds fast interior-point solvers for convex optimization problems of the form

\[\begin{split}\begin{array}{ll} \mbox{minimize} & f_0(w) \\ \mbox{subject to} & A w = b \\ & f_i(w) \leq 0, \quad i = 1, \ldots, n. \end{array}\end{split}\]

A generic solver factors an \(M \times M\) dense matrix at every Newton step, at a cost of \(O(M^3)\). Most problems that arise in practice have far more structure than that: a diagonal Hessian, a diagonal plus a low-rank update, a band, or an arrow pattern. Cvxium carries that structure through every Newton step, so the same iteration can cost \(O(M)\), which is the difference between a problem with a thousand variables and one with a million.

The library provides:

  • Composable problems: a Problem holds an Objective, a list of inequality ConstraintLayer objects, and optional equality constraints, built fluently with Problem.minimize(...).subject_to(...).

  • Interior-point solvers: the barrier method (BarrierSolver), the primal-dual method (PrimalDualSolver), Newton’s method (NewtonSolver), and a homogeneous self-dual method for conic programs (HsdSolver), each finding its own strictly feasible start (Phase I) when none is given.

  • Structured linear algebra: every component reports its Hessian as a MatrixSystem (diagonal, banded, low-rank updated, block diagonal, arrow), and the solver sums the contributions without losing structure. Equality constraints go through a Schur-complement SaddleSystem, dense, sparse, or banded.

  • Results that know themselves: a SolveResult carries the solution, duality-gap bound, Lagrange multipliers, and per-solver diagnostics, and round-trips through JSON.

  • Pareto frontiers: MultiObjectiveOptimizer traces the tradeoff between competing objectives, finds its knee, and certifies an interpolant with the multipliers it gets for free.

The methods follow [BV04]; the conic solver follows [ART03]. Full citations are on the References page.

Installation#

pip install cvxium

Quickstart#

Find the minimum-norm point satisfying \(A w = b\) and \(w \geq 0.01\). The objective \(\frac{1}{2} \| w \|_2^2\) has a diagonal Hessian and the bounds add another diagonal, so every Newton step costs time linear in the number of variables:

>>> import numpy as np
>>> from cvxium import (
...     BarrierSolver,
...     BoundsConstraintLayer,
...     DiagonalSystem,
...     EqualityConstraintLayer,
...     Problem,
...     QuadraticObjective,
... )
>>> rng = np.random.default_rng(0)
>>> M = 100
>>> A = rng.standard_normal((20, M))
>>> b = A @ (rng.random(M) + 0.1)
>>> objective = QuadraticObjective(
...     c=np.zeros(M), hessian_contribution=DiagonalSystem(np.ones(M))
... )
>>> result = (
...     Problem.minimize(objective)
...     .subject_to(
...         eq=EqualityConstraintLayer(A=A, b=b),
...         ineq=[BoundsConstraintLayer(lb=0.01, dimension=M)],
...     )
...     .solve(solver=BarrierSolver())
... )
>>> print(result.status)
SolveStatus.OPTIMAL
>>> bool(np.allclose(A @ result.solution, b)), bool(np.all(result.solution > 0.01))
(True, True)
>>> print(f"{result.objective_value:.4f}")
4.1942

When no starting point is given, the solver finds a strictly feasible one itself. The Building Fast Solvers with Cvxium works one example, from the mathematics to a fast solve, through writing a new objective and a new constraint layer; cvxium.usage() prints the same guide.

Contents:

Indices and tables#