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 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.

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.

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 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 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.