📊Mathematical Methods for Optimization Unit 5 – Duality and Sensitivity in Optimization

Key Concepts and Definitions

• Optimization problems involve minimizing or maximizing an objective function subject to constraints
• Primal problem represents the original optimization problem with decision variables, objective function, and constraints
• Dual problem is derived from the primal problem and provides bounds on the optimal value of the primal problem
• Lagrangian function combines the objective function and constraints using Lagrange multipliers
• Lagrange multipliers ($\lambda$) represent the sensitivity of the optimal value to changes in the constraints
• Shadow prices are the optimal values of the Lagrange multipliers and indicate the marginal value of relaxing a constraint
• Complementary slackness conditions relate the optimal solutions of the primal and dual problems
  • If a constraint is not binding in the primal solution, its corresponding dual variable is zero
  • If a dual variable is positive, its corresponding primal constraint is binding

Primal and Dual Problems

• Primal problem is the original optimization problem with decision variables ($x$), objective function $f(x)$, and constraints $g_i(x) \leq 0$ and $h_j(x) = 0$
  • Minimize or maximize $f(x)$ subject to $g_i(x) \leq 0$ and $h_j(x) = 0$
• Dual problem is derived from the primal problem by introducing Lagrange multipliers ($\lambda_i$ and $\mu_j$) for each constraint
  • Maximize or minimize the Lagrangian function over the Lagrange multipliers subject to $\lambda_i \geq 0$
• Primal and dual problems are related through the Lagrangian function and provide bounds on each other's optimal values
• Solving the dual problem can be easier than solving the primal problem in some cases (convex optimization)
• Optimal values of the primal and dual problems are equal under certain conditions (strong duality)
  • If strong duality holds, solving the dual problem gives the optimal solution to the primal problem

Lagrangian Duality

• Lagrangian function $L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)$ combines the objective function and constraints
• Lagrangian dual function $g(\lambda, \mu) = \inf_x L(x, \lambda, \mu)$ is the infimum of the Lagrangian function over $x$
  • Dual function provides a lower bound on the optimal value of the primal problem for any $\lambda \geq 0$ and $\mu$
• Lagrangian dual problem maximizes the dual function subject to $\lambda \geq 0$
  • $\max_{\lambda, \mu} g(\lambda, \mu)$ subject to $\lambda \geq 0$
• Solving the Lagrangian dual problem gives a lower bound on the optimal value of the primal problem
• If strong duality holds, the optimal value of the Lagrangian dual problem equals the optimal value of the primal problem

Strong and Weak Duality

• Weak duality states that the optimal value of the dual problem is always a lower bound on the optimal value of the primal problem
  • $d^* \leq p^*$, where $d^*$ and $p^*$ are the optimal values of the dual and primal problems, respectively
• Strong duality holds when the optimal values of the primal and dual problems are equal ($d^* = p^*$)
  • Sufficient conditions for strong duality include convexity of the primal problem and certain constraint qualifications (Slater's condition)
• If strong duality holds, solving the dual problem gives the optimal solution to the primal problem
• Duality gap is the difference between the optimal values of the primal and dual problems ($p^* - d^*$)
  • Duality gap is zero when strong duality holds
  • Non-zero duality gap indicates that the primal problem is not convex or the constraints do not satisfy the required qualifications

Sensitivity Analysis

• Sensitivity analysis studies how changes in the problem parameters (objective function coefficients, constraint bounds) affect the optimal solution and value
• Lagrange multipliers ($\lambda$ and $\mu$) provide information about the sensitivity of the optimal value to changes in the constraints
  • $\lambda_i$ represents the rate of change of the optimal value with respect to the $i$-th inequality constraint
  • $\mu_j$ represents the rate of change of the optimal value with respect to the $j$-th equality constraint
• Shadow prices are the optimal values of the Lagrange multipliers and indicate the marginal value of relaxing a constraint
  • Positive shadow price suggests that relaxing the constraint would improve the optimal value
  • Zero shadow price indicates that the constraint is not binding and small changes do not affect the optimal value
• Sensitivity analysis helps in understanding the robustness of the optimal solution and identifying critical constraints
• Range of validity for the shadow prices determines the extent to which the constraints can be changed without altering the optimal basis (linear programming)

Complementary Slackness

• Complementary slackness conditions relate the optimal solutions of the primal and dual problems
  • If a constraint is not binding in the primal solution, its corresponding dual variable is zero ($\lambda_i g_i(x^*) = 0$)
  • If a dual variable is positive, its corresponding primal constraint is binding ($\lambda_i^* > 0 \implies g_i(x^*) = 0$)
• Complementary slackness conditions are necessary and sufficient for optimality in convex optimization problems with strong duality
• Checking complementary slackness conditions helps verify the optimality of a solution
• Complementary slackness can be used to derive the optimal solution of the primal problem from the dual solution (and vice versa) when strong duality holds
  • Primal constraints corresponding to positive dual variables are binding
  • Dual variables corresponding to non-binding primal constraints are zero

Applications and Examples

• Resource allocation problems (portfolio optimization, production planning)
  • Objective: Maximize profit or minimize cost
  • Constraints: Resource availability, demand satisfaction, budget limitations
• Network flow problems (transportation, maximum flow)
  • Objective: Minimize transportation cost or maximize flow
  • Constraints: Flow conservation, capacity limitations, supply and demand requirements
• Machine learning (support vector machines, dual formulation of training problems)
  • Objective: Maximize margin or minimize training error
  • Constraints: Classification constraints, regularization terms
• Game theory (dual formulation of two-player zero-sum games)
  • Objective: Maximize payoff for one player (minimize for the other)
  • Constraints: Probability distributions, strategy constraints
• Engineering design (truss design, control systems)
  • Objective: Minimize weight or cost, maximize performance
  • Constraints: Stress limitations, stability requirements, control specifications

Common Pitfalls and Tips

• Verify that the primal problem is convex before applying duality results
  • Non-convex problems may have a duality gap or lack strong duality
• Check constraint qualifications (Slater's condition) to ensure strong duality holds
• Normalize equality constraints to have right-hand side zero for consistency in the Lagrangian function
• Use complementary slackness conditions to verify the optimality of a solution
  • Primal constraints corresponding to positive dual variables should be binding
  • Dual variables corresponding to non-binding primal constraints should be zero
• Interpret shadow prices carefully, considering their range of validity and the problem context
• Use sensitivity analysis to identify critical constraints and assess the robustness of the optimal solution
• Be cautious when interpreting unbounded dual variables, as they may indicate infeasibility in the primal problem
• Exploit the structure of the problem (sparsity, separability) to simplify the dual formulation and solution process