Convex problems are a special class of optimization problems that are almost always “easy” to solve (polynomial-time).
A problem is convex if it has a convex domain and convex objective
Convex problems has the following nice properties:
- can make guarantees about solution (always the best)
- doesn’t depend on initialization (strong convexity) (we can start at whatever random guess)
- often quite efficient
Convex Quadratic Objectives & Linear Systems
It is an often problem in Computer Graphics, for example, in quadric error simplification.
It can be expressed via positive-semidefinite (PSD) matrix A:
By differentiating the above function, we get
The 2nd-order condition is satisfied by definition, so we just need to solve a system of linear equation!
Unfortunately, most problems are not that clean (and often have constraints), so we need to solve them by descent methods.