A convex quadratic program with banded curvature and sparse rows, solved
by OSQP (Stellato, Banjac, Goulart, Bemporad and Boyd 2020, "OSQP: an
operator splitting solver for quadratic programs", Math Program Comput
12:637): minimise 1/2 x^T P x + q^T x over rows l <= a.x <= u, each row hard
(projected onto its interval) or soft (an exact l1 penalty weight times its
distance from the interval, whose proximal step is a soft threshold toward
it), the form of the convex subproblem of TrajOpt's sequential convex
optimisation (Schulman et al. 2014, IJRR 33:1251).
As the paper prescribes:
the data are equilibrated first (section 5.1): modified Ruiz scaling of
the KKT matrix's columns, the variables by D, the rows by E and the
cost by c, so rows of millimetres and of degrees meet the same step;
each row has its own step size (section 5.2): an equality row a
thousand times the step, a row bounded on neither side the least;
the step size adapts (section 5.2) to balance the primal and the dual
residuals, the step's system factored again when it changes fivefold;
the iteration stops on the primal and dual residuals of the unscaled
problem (section 3.4), or on a certificate of primal infeasibility
(section 3.4), ITERATIONS only a guard;
a solved problem is polished (section 4): the KKT system of the rows the
solution holds on their bounds is solved, regularised and refined, so
those rows are met to numerical precision, and the polished solution is
kept when its residuals are no larger.
The curvature and the rows only couple variables within band of each
other, so every linear system is the banded reduced form P + sigma I + A^T diag(rho) A (the paper's indirect form), factored by a banded Cholesky
factorisation (HumanQuadraticBand). A warm start carries the iterates of
a solve of the same rows with other bounds. A one-shot solve prepares
its own data; a caller that keeps a preparation (an interior session, a
fixed model) shares it only after exact P, q, ordered nonzero A and
scaling comparisons (HumanQuadraticPreparation). prepare additionally snapshots
a fixed convexification for bound-only retries and bounded exact factor
and scratch reuse; each solve computes its own iterates and resets rho.
Costs use w=band+1, S supplied curvature entries, Z stored row entries
and m rows, including diagonal systems and supplied curvature padding.
A convex quadratic program with banded curvature and sparse rows, solved by OSQP (Stellato, Banjac, Goulart, Bemporad and Boyd 2020, "OSQP: an operator splitting solver for quadratic programs", Math Program Comput 12:637): minimise
1/2 x^T P x + q^T xover rowsl <= a.x <= u, each row hard (projected onto its interval) or soft (an exact l1 penaltyweighttimes its distance from the interval, whose proximal step is a soft threshold toward it), the form of the convex subproblem of TrajOpt's sequential convex optimisation (Schulman et al. 2014, IJRR 33:1251).As the paper prescribes:
D, the rows byEand the cost byc, so rows of millimetres and of degrees meet the same step;ITERATIONSonly a guard;The curvature and the rows only couple variables within
bandof each other, so every linear system is the banded reduced formP + sigma I + A^T diag(rho) A(the paper's indirect form), factored by a banded Cholesky factorisation (HumanQuadraticBand). A warm start carries the iterates of a solve of the same rows with other bounds. A one-shotsolveprepares its own data; a caller that keeps a preparation (an interior session, a fixed model) shares it only after exact P, q, ordered nonzero A and scaling comparisons (HumanQuadraticPreparation). prepare additionally snapshots a fixed convexification for bound-only retries and bounded exact factor and scratch reuse; each solve computes its own iterates and resets rho. Costs use w=band+1, S supplied curvature entries, Z stored row entries and m rows, including diagonal systems and supplied curvature padding.