Convex Optimization Basics

Convex Optimization Basics

Convex Analysis

A good intro to convex analysis focused on optimization is Bertsekas. The main concept behind the definitions here is duality.

Duality

You should be very comfortable with duality. There are many versions of duality.

• LP duality and SDP duality: these are good lecture notes GuptaODonnellLS.
• Conic duality: cvxbook. A different line of presentation, which I haven’t really delved into is given by Ben-Tal and Nemirovski in the first chapter of their monograph.
• Conjugate duality: Bertsekas Chapter 7. This is very important to get comfortable with Mirror Descent and Dual Averaging methods.
• Lagrangian duality: the more general notion. I really like the interpretations in Chapter 5 of cvxbook.

Convex Formulations

There are a large number of types of convex program. I recommend you browse through the cvxbook to get an idea of what’s out there. In this way, next time you encounter an optimization problem, you will have some rough idea of whether it’s been looked at before.

Linear Programming

Linear Programming is one of the basic examples of convex optimization. The structure of linear function allows us to derive stronger statements in this context.

Here are some resources on Linear Programming:

• The notes continue to cover Complementary Slackness, Size of the Linear Program, Ye’s Interior point method.

• [Gupta and ODonnell]: