Weak Duality

This chapter shows how the notion of weak duality allows to develop, in a systematic way, approximations of non-convex problems based on convex optimization.

Starting with any given minimization problem, which we call ‘‘primal’’ for reference, we can form a ‘‘dual’’ problem. The dual problem is a concave maximization problem which provides a lower bound on the value of the original problem. This weak duality result allows to form bounds on non-convex problems using convex optimization.

When the original problem is convex, and with some mild extra conditions, the value of the ‘‘dual’’ problem is the same as that of the ‘‘primal’’, and we say that strong duality holds. Strong duality is covered here.

Outline

• Dual problem
• Geometric interpretation
• Duality as a game: the minimax inequality