Duality Examples

Optimization · Axiom Academy

EXAMPLE Duality in Convex Optimization Worked Examples: LP Duality, QP Duality, and Norm Minimization This module walks through three complete duality examples step-by-step: Example 1: Linear Programming Duality Example 2: Quadratic Program Duality Example 3: Norm Minimization and Its Dual For each example, we'll form the Lagrangian, derive the dual function, write the dual problem, and verify strong duality. Introduce Lagrange multipliers _1, _2 0 for the inequality constraints: The dual function is g( ) = _ x_1, x_2 L(x, ) . Minimize over x_1 and x_2 : For the infimum to be finite, we need: When this holds, g( ) = -3 _1 - 2 _2 . The dual problem is to maximize g( ) subject to the constraints: From the equality constraints: Consider the quadratic program: where P = 2 & 0 \\ 0 & 2 , q = -4 \\ -6 , A = 1 & 1 , b = 3 . Introduce Lagrange multiplier (unconstrained) for the equality constraint: Take the gradient with respect to x and set to zero: Solving: x^*( ) = P^ -1 (q - A^T ) = 2 -4 - \\ -6 - After substitution and simplification: This is an unconstrained concave quadratic maximization problem. Consider the norm minimization problem: This problem minimizes the Euclidean norm subject to linear equality constraints. Introduce Lagrange multiplier vector ^m : Minimize over x : _x L = x + A^T = 0 , so x^*( ) = -A^T . This is an unconstrained concave quadratic maximization.

This is the written version of the interactive lesson above. See the full Optimization course.