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.
