Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 8

Duality in Optimization

• The Lagrangian is formed by incorporating constraints into the objective function using Lagrange multipliers.
• The dual function is obtained by minimizing the Lagrangian over the variables.
• The dual function provides a lower bound on the optimal value of the original problem.
• The dual function can be interpreted as the conjugate of the objective function plus a linear function.
• Strong duality holds when the optimal value of the primal problem is equal to the optimal value of the dual problem.
• Constraint qualifications are additional conditions that must be satisfied for strong duality to hold.
• The Slater's condition is a well-known constraint qualification that guarantees strong duality for convex problems.

Duality Gap

• Duality gap refers to the difference between the optimal value of the primal problem and the optimal value of the dual problem.
• In general, non-convex problems can have a duality gap, while convex problems have zero duality gap.
• The geometric interpretation of the duality gap using the level curves of the Lagrangian function explains why convex problems have zero duality gap and why non-convex problems can have a duality gap.

Duality in Linear Programming

• The dual function of a linear program (LP) is formed by taking the transpose of the objective function and adding the transpose of the product of the Lagrange multipliers and the inequality constraints.
• Strong duality holds for linear programs, meaning that the optimal values of the primal and dual problems are equal, except in extremely pathological cases.

KKT Conditions

• The KKT conditions are necessary and sufficient conditions for optimality in constrained optimization problems.
• The KKT conditions extend the Lagrange conditions to handle inequality constraints.
• The KKT conditions state that:
  • The primal and dual variables must be feasible.
  • The dual variables must be non-negative.
  • Complementary slackness must hold.
  • The gradient of the Lagrangian with respect to the primal variables must vanish.

Lagrange Multipliers

• Lagrange multipliers are useful for understanding the behavior of optimization problems.
• They can be used to predict how the objective function will change if additional resources are allocated.
• Lagrange multipliers can also be used to identify which constraints are most tightly binding.
• In mechanical systems, Lagrange multipliers can be interpreted as forces.
• In electrical circuits, Lagrange multipliers can be interpreted as locational marginal prices.
• In resource allocation, Lagrange multipliers can be interpreted as prices or shadow prices.

CVX Pi

• CVX Pi is a software that solves convex optimization problems by transforming the original problem into a series of equivalent problems that a solver can handle.
• The transformations used by CVX Pi are called reductions, and each reduction has a corresponding retrieval method that allows the original problem to be reconstructed from the solution of the transformed problem.