5.1 Primal-dual relationship and weak duality theorem

Primal-dual relationships are the backbone of optimization theory. They connect minimization and maximization problems, offering new ways to solve complex issues and gain deeper insights into problem structures.

The weak duality theorem is a key player in this relationship. It sets bounds on optimal solutions, helps develop stopping criteria for algorithms, and forms the basis for more advanced duality concepts in optimization.

Duality in Optimization

Concept and Significance

Top images from around the web for Concept and Significance

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  Dual linear program - Wikipedia View original

  Is this image relevant?

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  Dual linear program - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept and Significance

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  Dual linear program - Wikipedia View original

  Is this image relevant?

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  3.2c. Examples: Solving Linear Programming Graphically | Finite Math View original

  Is this image relevant?

• 

  Dual linear program - Wikipedia View original

  Is this image relevant?

1 of 3

• Duality links primal and dual problems through shared objective function and constraints
• Primal problem minimizes while dual problem maximizes (or vice versa)
• Transforms complex primal problems into potentially simpler dual problems
  • Leads to more efficient solution methods
• Strong duality theorem relates optimal solutions of primal and dual problems
  • States optimal values of both problems are equal under certain conditions
• Provides insights into sensitivity of optimal solutions to parameter changes
  • Facilitates post-optimization analysis and interpretation
• Extends to various optimization problems
  • Linear programming
  • Convex programming
  • Certain classes of nonlinear programming

Applications and Implications

• Enables alternative solution approaches
  • Solving dual problem may be easier than primal in some cases
• Enhances understanding of problem structure
  • Reveals hidden relationships between variables and constraints
• Supports development of efficient algorithms
  • Simplex method for linear programming utilizes duality concepts
• Aids in economic interpretation of optimization problems
  • Shadow prices in resource allocation (marginal value of resources)
• Facilitates sensitivity analysis
  • Assessing impact of parameter changes on optimal solutions
• Provides theoretical foundation for advanced optimization techniques
  • Interior point methods
  • Decomposition algorithms (Dantzig-Wolfe, Benders)

Formulating the Dual Problem

Derivation Process

• Introduce Lagrange multipliers for each primal constraint
• Form Lagrangian function combining objective and constraints
• Obtain dual objective function
  • Minimize Lagrangian with respect to primal variables
  • Maximize with respect to dual variables (Lagrange multipliers)
• Derive dual constraints from Lagrangian optimization conditions
• Define dual feasible region
  • Non-negativity constraints on Lagrange multipliers
  • Additional constraints from Lagrangian optimization

Specific Techniques

• Linear programming dual formulation
  • Transpose constraint matrix
  • Exchange roles of objective coefficients and right-hand side values
  • Example: Primal min $c^Tx$ s.t. $Ax \geq b$ becomes Dual max $b^Ty$ s.t. $A^Ty \leq c$
• Quadratic programming dual formulation
  • Involves matrix operations on quadratic terms
  • Results in a dual problem with similar structure to primal
• Convex programming dual formulation
  • Utilizes Fenchel conjugate functions
  • Generalizes linear and quadratic programming duality

Implications and Applications

• Reveals hidden structure or symmetry in original problem
  • May lead to new solution approaches or insights
• Dual formulation complexity varies by problem type
  • Linear programs often have straightforward duals
  • Nonlinear programs may have more complex dual structures
• Supports development of primal-dual algorithms
  • Simultaneously solve primal and dual problems
  • Example: Primal-dual interior point methods for linear programming
• Facilitates economic interpretation of optimization problems
  • Dual variables often represent shadow prices or marginal values
• Enables construction of bounds on optimal solutions
  • Useful for developing approximation algorithms

Weak Duality Theorem

Theorem Statement and Proof

• Weak duality theorem states
  • For minimization problems, primal objective value $\geq$ dual objective value for any feasible solutions
  • For maximization problems, primal objective value $\leq$ dual objective value for any feasible solutions
• Proof typically involves
  • Manipulating primal and dual objective functions
  • Utilizing constraints and Lagrangian function properties
  • Example: For linear programs, proof uses $c^Tx \geq y^TAx \geq y^Tb$ for feasible $x$ and $y$
• Holds regardless of problem convexity or existence of optimal solutions
  • Applies to wide range of optimization problems

Applications in Optimization

• Establishes bounds on optimal solutions
  • Lower bounds for primal minimization problems
  • Upper bounds for primal maximization problems
• Develops stopping criteria for iterative algorithms
  • Measures optimality gap between primal and dual solutions
  • Example: In branch-and-bound, weak duality provides global lower bound
• Supports algorithm development
  • Simplex method for linear programming utilizes weak duality
  • Subgradient methods for non-differentiable optimization
• Forms basis for more advanced duality results
  • Strong duality theorem
  • Complementary slackness conditions

Practical Implications

• Provides certificate of solution quality
  • Bounds worst-case performance of heuristic algorithms
• Enables early termination of algorithms
  • When primal-dual gap is sufficiently small
• Supports sensitivity analysis
  • Assessing impact of constraint perturbations on optimal value
• Facilitates development of approximation algorithms
  • Using dual-based relaxations to bound optimal solutions
• Aids in economic interpretation
  • Dual variables as price signals in resource allocation problems