Convex Optimization

The ordinary least-squares problem can be solved using linear algebra methods. It turns out that we can confidently use this approach in an iterative algorithm, to globally minimize ‘‘bowl-shaped’’, or convex, functions, under convex constraints.

We first define precisely what is meant by convex sets and functions, and outline a few simple rules that can help in determining if a set or function is convex. The picture on the left illustrates one of these rules, the monotonicity rule. Then we will define convex optimization problems and single out broad classes of problems that fall in the convex optimization category.

We provide the main ideas behind some convex optimization algorithms, including the so-called interior-point and gradient methods. Our final focus is on disciplined convex programming (DCP), a sub-class of convex optimization that corresponds exactly to the problems amenable to the software package CVX.

Outline

• Convex sets
• Convex functions
• Convex optimization problems
• Algorithms
• Disciplined convex programming and CVX
• Exercises