9.1 Lagrangian duality

Lagrangian duality is a powerful tool in optimization, connecting primal and dual problems. It introduces the Lagrangian function, which combines the objective and constraints, and explores the relationship between primal and dual solutions.

This concept is crucial for understanding duality theory, as it provides insights into problem structure and solution methods. Lagrangian duality forms the foundation for various optimization techniques and has wide-ranging applications in machine learning, economics, and resource allocation.

Lagrangian Formulation

Lagrangian Function and Problem Formulation

Top images from around the web for Lagrangian Function and Problem Formulation

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Lagrangian Function and Problem Formulation

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

1 of 3

• Lagrangian function combines objective function and constraints into a single expression
• Primal problem represents original optimization problem with constraints
• Dual problem derives from Lagrangian function, maximizes lower bound on primal objective
• Lagrange multipliers act as weights for constraints in Lagrangian function
• Lagrangian relaxation technique relaxes complicating constraints by adding them to objective function

Mathematical Representation of Lagrangian Concepts

• Lagrangian function for constrained optimization problem expressed as $L(x, λ) = f(x) + λᵀg(x)$
• Primal problem formulated as $\min_{x} f(x) \text{ subject to } g(x) \leq 0$
• Dual problem defined as $\max_{λ≥0} \min_{x} L(x, λ)$
• Lagrange multipliers (λ) associated with each constraint, indicate sensitivity of optimal value to constraint changes
• Dual function derived from Lagrangian $d(λ) = \inf_{x} L(x, λ)$

Duality Properties

Fundamental Duality Concepts

• Weak duality theorem states optimal value of dual problem provides lower bound for primal problem
• Strong duality occurs when optimal values of primal and dual problems are equal
• Duality gap measures difference between primal and dual optimal values
• Saddle point represents solution where Lagrangian function minimized with respect to primal variables and maximized with respect to dual variables
• Complementary slackness condition relates optimal primal and dual solutions

Duality Theorems and Conditions

• Weak duality holds for any convex optimization problem
• Slater's condition provides sufficient condition for strong duality in convex problems
• KKT conditions necessary for optimality in nonlinear programming problems with differentiable functions
• Farkas' lemma fundamental result in linear programming duality theory
• Fenchel duality generalizes Lagrangian duality to non-convex problems

Applications

Convex Optimization Applications

• Support Vector Machines (SVMs) in machine learning utilize duality for efficient training
• Network flow problems solved using dual formulations (max-flow min-cut theorem)
• Portfolio optimization employs duality to balance risk and return
• Constrained least squares problems solved efficiently using dual methods
• Economic equilibrium models analyzed using duality concepts

Practical Uses of Lagrangian Duality

• Resource allocation problems optimized using Lagrangian relaxation techniques
• Decomposition methods for large-scale optimization problems leverage duality
• Robust optimization formulations incorporate duality to handle uncertainty
• Penalty and barrier methods in nonlinear programming derived from Lagrangian concepts
• Dual ascent algorithms used for distributed optimization in multi-agent systems