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 ½ xᵀPx + qᵀx over rows l <= a·x <= u, each row hard
(projected onto its interval) or soft (an exact l1 penalty weight × 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 + σI + Aᵀ diag(ρ) 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 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
½ xᵀPx + qᵀxover rowsl <= a·x <= u, each row hard (projected onto its interval) or soft (an exact l1 penaltyweight ×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 + σI + Aᵀ diag(ρ) 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.