Quadratic Programming

An optimization problem with a quadratic objective and linear equality or inequality constraints, extremely common in control.

Quadratic programming is a class of mathematical optimization problems: min ½xᵀQx + cᵀx, subject to Ax ≤ b. Here x is the variable being solved for (e.g., joint accelerations, torques, or contact forces), Q and c describe the objective (often ‘squared deviation from a desired value’), and A, b encode linear constraints (torque limits, a linearized friction cone, etc.). When Q is positive semi-definite the problem is convex, has a global optimum, and can be solved quickly with interior-point or active-set methods; OSQP and qpOASES are commonly used open-source solvers in robotics. When Q doesn't meet that condition, the problem is generally NP-hard. QP shows up constantly in robot control because ‘minimize squared tracking error subject to physical limits’ is naturally this shape: whole-body control solves a QP every cycle to allocate torques and contact forces, and convex MPC is also often written as a QP.

ExampleIn MIT Mini Cheetah's controller, an MPC solves a QP at 30 Hz to plan ground reaction forces at each foot, and a 500 Hz whole-body impulse controller solves a small additional QP to refine those forces before converting them into joint torques.

Also called

QP, Convex QP

Related

Convex Optimization · Whole-Body Control · Model Predictive Control · Hierarchical Quadratic Programming · OSQP · Friction Cone

Sources

Wikipedia: Quadratic programming
OSQP Documentation
Highly Dynamic Quadruped Locomotion via Whole-Body Impulse Control and Model Predictive Control (arXiv:1909.06586)