3.3 Duality theory

Duality theory is a powerful tool in combinatorial optimization. It connects primal and dual problems, providing alternative perspectives and efficient solution methods. The weak and strong duality theorems offer bounds and optimality conditions, while linear programming duality forms the foundation for many applications.

Duality extends to network flows, integer programming, and advanced concepts like Farkas' lemma and KKT conditions. It enables sensitivity analysis, economic interpretations, and algorithmic techniques such as primal-dual methods and column generation. Understanding duality is crucial for solving complex optimization problems efficiently.

Concept of duality

• Fundamental principle in optimization theory establishes relationships between primal and dual problems
• Provides powerful tools for analyzing and solving complex optimization problems in combinatorial optimization
• Allows for alternative perspectives on optimization problems leading to more efficient solution methods

Primal vs dual problems

Top images from around the web for Primal vs dual problems

• 

  linear programming - Simplex method : Duality by Bazaraa - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  linear programming - Simplex method : Duality by Bazaraa - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 1

Top images from around the web for Primal vs dual problems

• 

  linear programming - Simplex method : Duality by Bazaraa - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  linear programming - Simplex method : Duality by Bazaraa - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 1

• Primal problem represents the original optimization problem formulated to minimize or maximize an objective function
• Dual problem derives from the primal problem offers a complementary perspective on the optimization task
• Primal and dual problems have inverse objective functions (minimization becomes maximization and vice versa)
• Variables in the dual problem correspond to constraints in the primal problem
• Constraints in the dual problem correspond to variables in the primal problem

Weak duality theorem

• States that the objective value of any feasible solution to the dual problem bounds the objective value of the primal problem
• For minimization problems, dual objective value provides a lower bound for the primal objective value
• For maximization problems, dual objective value provides an upper bound for the primal objective value
• Holds true regardless of whether the optimal solution has been found
• Useful for developing approximation algorithms and bounding optimal solutions

Strong duality theorem

• Asserts that under certain conditions, the optimal objective values of the primal and dual problems are equal
• Applies to linear programming problems and certain classes of convex optimization problems
• Provides a powerful tool for verifying optimality of solutions
• Enables solving one problem (primal or dual) to obtain the solution to the other
• Breaks down for integer programming problems, leading to the concept of duality gap

Linear programming duality

Standard form LP

• Represents a linear programming problem in a standardized format
• Consists of a linear objective function to be maximized or minimized
• Subject to a set of linear equality constraints
• All variables are required to be non-negative
• Can be written as: $\text{maximize } c^Tx \text{ subject to } Ax \leq b, x \geq 0$
• Facilitates the application of standard solution methods (simplex algorithm)

Dual form LP

• Derived from the standard form LP by transforming the primal problem
• Objective function coefficients become right-hand side values in constraints
• Right-hand side values in constraints become objective function coefficients
• Constraint matrix is transposed
• Inequality directions are reversed
• Can be written as: $\text{minimize } b^Ty \text{ subject to } A^Ty \geq c, y \geq 0$
• Often provides computational advantages over solving the primal problem directly

Complementary slackness conditions

• Define relationships between optimal solutions of primal and dual problems
• State that for each constraint, either the slack variable is zero or the corresponding dual variable is zero
• Provide a way to verify optimality of primal and dual solutions simultaneously
• Can be expressed as: $x_i(A^Ty - c)_i = 0$ for primal variables and $y_j(b - Ax)_j = 0$ for dual variables
• Useful in developing primal-dual algorithms and sensitivity analysis

Duality in network flows

Max flow-min cut theorem

• Fundamental result in network flow theory establishes duality between maximum flow and minimum cut problems
• States that the maximum flow value equals the capacity of the minimum cut in a network
• Provides a certificate of optimality for both problems simultaneously
• Applies to directed and undirected networks with capacitated edges
• Forms the basis for many efficient algorithms in network optimization (Ford-Fulkerson algorithm)

Minimum cost flow duality

• Relates the minimum cost flow problem to its dual formulation
• Dual problem involves finding node potentials that maximize a certain objective function
• Optimal node potentials provide insights into the structure of the optimal flow
• Complementary slackness conditions relate flow values to reduced costs
• Enables development of efficient algorithms for solving minimum cost flow problems (network simplex method)

Applications of duality

Sensitivity analysis

• Utilizes duality to analyze how changes in problem parameters affect optimal solutions
• Examines effects of changes in objective function coefficients and constraint right-hand sides
• Provides insights into the stability and robustness of optimal solutions
• Allows for efficient re-optimization when problem parameters change slightly
• Crucial for decision-making in dynamic environments (supply chain management)

Economic interpretation

• Dual variables (shadow prices) represent marginal values of resources in the primal problem
• Provides insights into the economic value of constraints and resources
• Helps in resource allocation decisions and pricing strategies
• Enables analysis of opportunity costs and trade-offs in resource utilization
• Applicable in various fields (production planning, portfolio optimization)

Game theory connections

• Duality in linear programming relates to the minimax theorem in two-person zero-sum games
• Optimal strategies in game theory correspond to optimal solutions of primal and dual LPs
• Enables solving certain classes of games using linear programming techniques
• Provides insights into equilibrium concepts and strategic decision-making
• Applications in economics, political science, and operations research

Duality in integer programming

Lagrangian relaxation

• Technique for approximating integer programming problems using duality
• Relaxes complex constraints by incorporating them into the objective function with Lagrange multipliers
• Creates a relaxed problem that is easier to solve than the original integer program
• Provides bounds on the optimal solution value of the original problem
• Often used in combination with branch-and-bound algorithms to solve large-scale integer programs

Cutting plane methods

• Iterative approach for solving integer programming problems using duality
• Adds constraints (cuts) to the LP relaxation to tighten the feasible region
• Utilizes the dual problem to generate valid inequalities that separate fractional solutions
• Gomory cuts and Chvátal-Gomory cuts are common types of cutting planes
• Combines with branch-and-bound to form branch-and-cut algorithms for solving difficult integer programs

Algorithmic implications

Primal-dual algorithms

• Simultaneously work on primal and dual problems to find optimal solutions
• Maintain feasibility in one problem while improving optimality in the other
• Often provide approximation guarantees for NP-hard problems
• Examples include algorithms for minimum spanning trees and bipartite matching
• Useful in online and distributed optimization settings

Column generation techniques

• Utilizes duality to efficiently solve large-scale linear programs
• Starts with a restricted set of variables (columns) and iteratively adds promising ones
• Uses the dual problem to identify variables with negative reduced costs
• Applicable to problems with exponentially many variables (cutting stock problem)
• Often combined with branch-and-bound to solve integer programs (branch-and-price)

Advanced duality concepts

Farkas' lemma

• Fundamental result in linear algebra and optimization theory
• States that for a system of linear inequalities, either there exists a solution or there exists a certificate of infeasibility
• Provides a theoretical foundation for duality in linear programming
• Used to prove the strong duality theorem and develop optimality conditions
• Applications in feasibility analysis and constraint qualification in nonlinear optimization

Duality gap

• Difference between the optimal values of the primal and dual problems
• Always non-negative due to weak duality
• Zero for linear programs with strong duality
• Can be positive for non-convex problems (integer programming)
• Measures the quality of relaxations and approximations in optimization algorithms

Karush-Kuhn-Tucker conditions

• Necessary conditions for optimality in nonlinear programming problems
• Generalize the concept of Lagrange multipliers to inequality constraints
• Include primal feasibility, dual feasibility, complementary slackness, and stationarity conditions
• Sufficient for optimality in convex optimization problems
• Form the basis for many nonlinear optimization algorithms (sequential quadratic programming)