Strict complementary slackness is an important concept in linear programming and optimization theory, providing deeper insight into the relationship between primal and dual solutions. Unlike the standard complementary slackness condition, which allows non-strict inequalities, strict complementary slackness requires that for each pair of primal and dual variables, exactly one in the pair is strictly positive while the other is zero. This property is particularly valuable in sensitivity analysis, duality theory, and understanding the uniqueness of optimal solutions. Proving strict complementary slackness involves a combination of linear algebra, convex analysis, and duality principles, making it a foundational result in both theoretical and applied optimization.
Background on Linear Programming and Duality
Linear programming (LP) involves the optimization of a linear objective function subject to linear equality and inequality constraints. Formally, a standard primal problem can be expressed as
Maximize \( c^T x \) subject to \( Ax \leq b \) and \( x \geq 0 \), where \( x \in \mathbb{R}^n \), \( A \in \mathbb{R}^{m \times n} \), \( b \in \mathbb{R}^m \), and \( c \in \mathbb{R}^n \).
The corresponding dual problem is defined as
Minimize \( b^T y \) subject to \( A^T y \geq c \) and \( y \geq 0 \), where \( y \in \mathbb{R}^m \).
The duality principle states that if both the primal and dual problems have feasible solutions, then the optimal values of their objective functions are equal. Complementary slackness provides conditions that relate the primal and dual optimal solutions and serves as a crucial tool in proving optimality.
Complementary Slackness Conditions
In the context of linear programming, the complementary slackness conditions state that for each pair of primal variable \( x_i \) and corresponding dual constraint slack \( s_i \), the following holds at optimality
- \( x_i (A^T y – c)_i = 0 \) for all \( i \), where \( (A^T y – c)_i \) is the slack in the dual constraint.
- \( y_j (b – Ax)_j = 0 \) for all \( j \), where \( (b – Ax)_j \) is the slack in the primal constraint.
These conditions imply that either a primal variable is zero or the corresponding dual constraint is tight, and vice versa. Strict complementary slackness strengthens this relationship by ensuring that exactly one element in each pair is strictly positive, preventing simultaneous zeros.
Statement of Strict Complementary Slackness
Formally, strict complementary slackness asserts that for each pair \( (x_i, s_i) \) and \( (y_j, t_j) \), where \( s_i = (A^T y – c)_i \) and \( t_j = (b – Ax)_j \), one and only one of the pair is strictly positive
- \( x_i >0 \) implies \( s_i = 0 \)
- \( s_i >0 \) implies \( x_i = 0 \)
- \( y_j >0 \) implies \( t_j = 0 \)
- \( t_j >0 \) implies \( y_j = 0 \)
Strict complementary slackness is particularly relevant when the linear program has a unique optimal solution or when exploring sensitivity and stability properties of LP solutions. It also facilitates the construction of strictly feasible dual and primal solutions for theoretical analysis.
Proof of Existence of Strict Complementary Slackness
The proof typically relies on the convexity of feasible regions and properties of linear programming. One standard approach is based on perturbation arguments and the use of Farkas’ lemma. The main steps are outlined below
Step 1 Feasible and Optimal Solutions
Assume that the primal problem has an optimal solution \( x^ \) and the dual problem has an optimal solution \( y^ \). Let \( S \) denote the set of indices corresponding to non-zero primal variables, and let \( T \) denote the set of indices corresponding to non-zero dual variables. The complementary slackness conditions are satisfied for these solutions, but strict positivity is not guaranteed.
Step 2 Perturbation of Objective Function
Introduce a small perturbation to the objective vector \( c \) such that \( c_\epsilon = c + \epsilon d \), where \( d \) is a randomly chosen vector and \( \epsilon >0 \) is sufficiently small. This ensures that the new LP problem remains feasible and has a unique optimal solution due to the generic perturbation, which breaks ties between degenerate solutions.
Step 3 Uniqueness and Non-degeneracy
Under the perturbed problem, the primal and dual solutions become non-degenerate, meaning that the basic feasible solution has exactly \( n \) active constraints and no zero components except those dictated by feasibility. This guarantees that each primal variable corresponding to a tight dual constraint is strictly positive, and vice versa.
Step 4 Limiting Argument
As \( \epsilon \to 0 \), the perturbed solution converges to a solution of the original problem. By continuity and convexity of the feasible region, one can select a limit point where strict complementary slackness holds. This step ensures the existence of a solution satisfying the strict form of the complementary slackness condition.
Applications of Strict Complementary Slackness
Strict complementary slackness has important implications in optimization theory and practical applications. These include
- Sensitivity AnalysisHelps determine how changes in constraints or objective coefficients affect the optimal solution.
- Uniqueness of Optimal SolutionsProvides conditions under which the primal and dual solutions are uniquely determined.
- Interior Point MethodsUsed in algorithm design to ensure convergence to strictly feasible points in primal-dual algorithms.
- Economic InterpretationIn linear programming models of economics, strict complementary slackness corresponds to binding constraints and active prices.
Examples in Practice
Consider a linear program representing a production planning problem where a factory produces multiple products with limited resources. Strict complementary slackness can identify which products are actively utilizing resources and which constraints are tight, offering insights into resource allocation and efficiency. Similarly, in transportation or network flow problems, it can indicate which routes or flows are critical and which are surplus, guiding decision-making for optimization and cost reduction.
Strict complementary slackness is a fundamental concept in linear programming that strengthens the relationship between primal and dual optimal solutions. Its proof relies on convexity, perturbation arguments, and continuity principles to establish the existence of strictly complementary solutions. Beyond theoretical significance, strict complementary slackness has practical applications in sensitivity analysis, uniqueness verification, and algorithm design, making it an essential tool for both researchers and practitioners in operations research, economics, and applied mathematics. Understanding and applying this concept provides a deeper comprehension of linear programming structure and the behavior of optimal solutions under varying conditions.