mathematics//optimization//convex optimization//quadratic program
A quadratic program is an optimization problem with a quadratic cost and linear constraints; when the quadratic is convex it has a single optimum that solvers find reliably, in fractions of a millisecond for small sizes, and this is why it sits inside linear MPC, the safety filters that correct a learned controller and the trajectory generators of quadrotors.
A quadratic program is an optimization problem with a quadratic cost and linear constraints; when the quadratic is convex it has a single optimum that solvers find reliably, in fractions of a millisecond for small sizes, and this is why it sits inside linear MPC, the safety filters that correct a learned controller and the trajectory generators of quadrotors.
minx 12 x⊤P x+q⊤xsubject toAx≤b,P⪰0\min_{x}\; \tfrac12\,x^{\top}P\,x + q^{\top}x \quad\text{subject to}\quad Ax\le b,\qquad P\succeq0xmin21x⊤Px+q⊤xsubject toAx≤b,P⪰0
PPP holds the quadratic weights and must be positive semidefinite for the problem to be convex; qqq the linear terms; the rows of Ax≤bAx\le bAx≤b the limits. An MPC with a linear model, a quadratic cost on errors and inputs, and limits on actuators and states is exactly this problem, written again at every control period. For a drone's lateral axis (four states, one input) with a horizon of 20 steps it has 20 variables and 40 torque limits, a small QP.
In a control loop a QP solver is a component with a deadline. What matters is its worst-case solve time and what the loop does when it does not finish (apply the next input of the previous plan, or fall back to an LQR); and computing is delay, so a solve that takes 5 ms should start from the state predicted for the moment its input will be applied.
The solvers are specialized. OSQP (an operator-splitting method, light enough for embedded code) and qpOASES (an active-set method built for MPC) are the usual names; both start from the previous plan shifted by one step (warm start), which usually leaves the solution a few iterations away.
Three uses recur in the book. The MPC solves one per period; a control barrier function solves a tiny one per step to change a learned policy's action as little as needed to stay safe; and minimum-snap trajectory generation solves one before take-off for the polynomial path gentlest on the motors.
A QP can have no solution. With a short horizon or a large disturbance no input satisfies every limit, and the solver fails exactly when it is most needed; practice makes state limits soft (violations allowed at a high price) and keeps actuator limits hard, because those are physical. If PPP is not positive semidefinite the problem is non-convex and NP-hard, so the matrix is checked before the solver is trusted.