10. Convex Optimization#

This chapter provides general introduction to convex optimization problems. Convex optimization focuses on a special class of mathematical optimization problems where:

  • The real valued function being optimized (maximized or minimized) is convex.

  • The feasible set of values for the function is a closed convex set.


Fig. 10.1 For a convex function, the line segment between any two points on the graph of the function does not lie below the graph between the two points. Its epigraph is a convex set. A local minimum of a convex function is also a global minimum.#

Convex optimization problems are usually further classified into

  • Least squares

  • Linear programming

  • Quadratic minimization with linear constraints

  • Quadratic minimization with convex quadratic constraints

  • Conic optimization

  • Geometric programming

  • Second order cone programming

  • Semidefinite programming

There are specialized algorithms available for each of these classes.

Some of the applications of convex optimization include:

  • Portfolio optimization

  • Worst case risk analysis

  • Compressive sensing

  • Statistical regression

  • Model fitting

  • Combinatorial Optimization