Convex Optimization

Minimizing a convex function over a convex feasible region — a problem where any local optimum found is also the global one.

Convex optimization studies minimizing a convex function over a convex set: min f(x) subject to x ∈ C. f is a convex function (its graph looks like a bowl, and the line segment between any two points on it lies above the curve), and C is a convex set (the line segment between any two points in the set stays inside the set). Its most important property is that any local optimum is automatically the global optimum; categories such as linear programming, quadratic programming, second-order cone programming, and semidefinite programming all have polynomial-time algorithms (such as interior-point methods), so they solve quickly and reliably. Real-time robot control leans on this heavily: convex MPC, the quadratic programs inside whole-body control, and contact-force allocation are all deliberately formulated as convex problems specifically so they can be solved reliably within a millisecond-scale budget. Non-convex problems, such as general trajectory optimization, are commonly approximated by breaking them into a sequence of convex subproblems, an approach called sequential quadratic programming.

ExampleMIT Cheetah 3 (2018) simplified the quadruped into a single rigid body and formulated planning of ground-reaction forces over a horizon of up to 0.5 s as a convex quadratic program, solving it in under 1 ms and re-solving repeatedly at 20–30 Hz, producing gaits including trotting, galloping, and pronking.

Also called

Convex Programming

Related

Quadratic Programming · Convex MPC · Model Predictive Control · Trajectory Optimization · Sequential Quadratic Programming · OSQP

Sources

Wikipedia: Convex optimization
Boyd & Vandenberghe: Convex Optimization（官方免费电子版页面） (Chinese)
Dynamic Locomotion in the MIT Cheetah 3 Through Convex Model-Predictive Control (IROS 2018)