1 Prerequisites

1.1 Linear programming overview

Linear programming (LP) is the study of optimization problems in which both the objective function and the constraints are linear. A typical LP seeks to minimize or maximize a linear expression subject to a collection of linear inequality and/or equality constraints. Because the feasible region is a polyhedron (or empty), many theoretical tools—especially duality—can provide certificates of optimality and insights into the structure of solutions.

1.2 Primal and dual problems

Given an LP in a standard form, one can associate a dual LP whose variables correspond to the constraints of the primal. The primal variables represent decision variables in the original model, while dual variables can be interpreted as measures of how much the objective would improve per unit tightening of constraints (subject to scaling). Solving either problem informs the other through their shared optimal value and complementary relationships.

1.3 Feasibility and bounds

Feasibility means at least one assignment satisfies all constraints. In LP, if the primal is feasible and the dual is feasible, both problems have meaningful bounds on the objective value. Even before solving the full optimization, weak duality ensures that any feasible dual solution gives a bound on the best achievable primal value; similarly, any feasible primal solution bounds the dual. Feasibility and these bounds are the baseline assumptions used to reason about optimality.

2 Duality in linear programming

2.1 Weak duality

Weak duality states that for any primal-feasible solution and any dual-feasible solution, the primal objective value cannot cross the dual objective value in the “wrong” direction. Concretely, for minimization-primal/maximization-dual pairs, the dual objective provides an upper bound on the primal objective, or equivalently the primal provides a lower bound on the dual. This guarantee is crucial: it allows certification logic based on showing that primal and dual values coincide.

2.2 Strong duality

Strong duality strengthens weak duality by asserting that if the primal and dual are both feasible and certain regularity conditions hold (commonly satisfied in standard LP settings), then the optimal objective values are equal. As a consequence, if one can exhibit feasible primal and dual solutions with matching objective values, both are optimal.

2.3 Optimality certificates

The most useful practical takeaway of duality is the notion of an optimality certificate. Rather than proving optimality by exploring the entire feasible region, one can provide a feasible primal solution, a feasible dual solution, and show that their objective values match. Complementary slackness supplies the additional structural conditions that ensure the match and explain why it occurs.

3 Complementary slackness conditions

3.1 Primal slack and dual variable pairing

Complementary slackness links primal inequality constraints that are not “tight” to dual variables that must be zero, in a paired manner. Informally, if a primal constraint has slack—meaning it is satisfied strictly—then the corresponding dual variable associated with that constraint cannot contribute to the objective optimally, so it must be zero. This expresses that unused constraints carry no marginal value at the optimum.

3.2 Dual slack and primal variable pairing

The dual form mirrors the same principle. If a dual constraint has slack at the optimum, then the associated primal variable must be zero. In other words, primal variables that would correspond to an inactive restriction in the dual cannot be positive in an optimal primal solution. This pairing creates a two-sided consistency between which constraints bind and which variables are active.

3.3 Zero-product interpretation

Complementary slackness can be summarized as a collection of “zero-product” relations: each inequality constraint slack multiplied by its corresponding dual variable equals zero, and each dual inequality slack multiplied by its associated primal variable equals zero. Because each term is nonnegative under standard sign conventions, the product condition forces at least one factor to be zero.

3.3.1 Complementarity for inequalities

For inequality constraints, slackness is typically defined as the difference between the right-hand side and the left-hand side in a way that is nonnegative over the feasible set. Complementary slackness requires that for each inequality, either the slack is zero (the constraint is tight) or the matching dual variable is zero (the constraint’s shadow value vanishes), or both.

3.3.2 Complementarity for equality constraints

Equality constraints are always tight by definition, so the “slack factor” is identically zero. Consequently, complementary slackness imposes no additional restriction through that product form. Instead, the dual variables for equality constraints reflect their role directly, often without the same zero/nonzero alternation seen for inequalities.

4 Optimality and verification

4.1 Using complementary slackness to certify optimality

A standard verification workflow uses feasibility plus complementary slackness. If one can find a primal-feasible solution and a dual-feasible solution that satisfy the complementary slackness relations, then the primal and dual objective values must coincide, implying both solutions are optimal via strong duality. In practice, this means complementary slackness turns feasibility into a strong optimality check.

4.2 Constructing a primal-dual optimal pair

Complementary slackness also guides construction. One may start with an optimal dual objective value (or a promising primal solution) and then assign dual variables to satisfy feasibility while enforcing complementarity on the active set. Conversely, given an optimal-looking primal solution, one can often infer which dual variables must be zero based on which primal constraints are tight, then solve for a dual that remains feasible and objective-matching.

4.3 Interpreting which constraints are tight

At optimality, complementary slackness makes “tight vs. slack” an answerable question. If a dual variable is positive, the associated primal inequality must have zero slack, indicating the constraint binds and limits the feasible choices. If a dual variable is zero, the constraint may be loose; it is not acting as a limiting factor in the optimum (though it could still be tight incidentally in some degenerate situations).

4.4 Interpreting which variables are positive

The dual slack pairing yields the converse view. A positive primal variable implies that the associated dual constraint is tight. This allows the active structure of the solution to be read off: which decisions are taken in the primal correspond to which restrictions in the dual are binding.

5 Geometric and intuitive interpretations

5.1 Slackness as “distance” to binding constraints

Geometrically, LP feasible regions are polytopes. Constraints that are not binding correspond to facets that are not currently “touched” by the optimal point. The slack associated with an inequality measures, in a linear sense, how far the point is from that facet along the constraint normal. Complementary slackness then states that if the point is not on a facet, the dual weight tied to that facet must vanish at optimality.

5.2 Shadow prices and economic meaning

In applications, dual variables for inequalities are often interpreted as shadow prices: the rate of change of the optimal objective when modifying the constraint bound slightly. Complementary slackness supports this interpretation: if a constraint is not binding (positive slack), its marginal price is zero because relaxing it does not improve feasibility in a way that changes the optimum. If the constraint binds, the marginal price can be positive (or negative, depending on formulation conventions).

5.3 Active set viewpoint

The conditions can also be read as an “active set” consistency rule. The active set of primal constraints (those with zero slack) matches precisely the set of dual variables that may be nonzero, and the active set of dual constraints matches the set of primal variables that may be positive. This dual matching captures how both problems identify the same critical structure of the optimum.

6 Worked examples

6.1 A simple two-variable linear program

Consider the primal minimization problem:

  • minimize \(c^\top x = x_1 + 2x_2\)
  • subject to

\[ \begin{aligned} x_1 + x_2 &\ge 1,\\ x_1 &\ge 0, \quad x_2 \ge 0. \end{aligned} \] A convenient dual form can be written using a dual variable \(y \ge 0\) for the inequality \(x_1 + x_2 \ge 1\). In this formulation, the dual becomes:

  • maximize \(y\)
  • subject to

\[ y \le 1,\quad y \le 2,\quad y \ge 0. \] The dual feasible region is therefore \(0 \le y \le 1\), and the dual optimum is \(y^* = 1\).

6.2 Checking complementary slackness for a given solution

Take a primal point \(x^* = (1,0)\). It is feasible because \(x_1 + x_2 = 1\) and both variables are nonnegative. The primal objective value is \(x_1 + 2x_2 = 1\), matching the dual upper bound implied by \(y \le 1\).

Complementary slackness:

  • The primal inequality \(x_1 + x_2 \ge 1\) has zero slack at \(x^*\) since it holds with equality. The paired dual variable is \(y^* = 1\), which is nonzero, consistent with complementarity.
  • For nonnegativity constraints, complementary slackness in standard primal-dual formulations is handled through the dual constraint structure. Here, \(x_2^* = 0\) corresponds to the fact that the dual constraint associated with \(x_2\) can be slack (it is: \(y^*=1 < 2\)), which matches the rule that a slack dual constraint forces the primal variable to be zero.

Thus the primal-dual pair \((x^*, y^*)\) satisfies the complementary slackness pattern and achieves equal objectives, confirming optimality.

6.3 Diagnosing near-optimality vs optimality

Suppose instead that a candidate primal solution \( \tilde{x} \) is feasible and has objective value close to the dual bound, but complementary slackness fails. In that case, equality of objective values is not guaranteed, and the candidate may be merely near-optimal rather than optimal. Conversely, if a candidate primal and a candidate dual are feasible and their objective values match, complementary slackness will automatically hold under the LP duality framework (in exact arithmetic). Practically, checking complementarity helps distinguish “close but wrong” from “certified optimal.”

7.1 Karush–Kuhn–Tucker (KKT) conditions connection

Complementary slackness is a central component of the KKT conditions for constrained optimization. In the nonlinear or convex setting, KKT introduces Lagrange multipliers for inequality constraints and requires that each multiplier times its constraint slack equals zero, paralleling the LP condition. When the objective and constraint functions are convex and a regularity condition holds, satisfying KKT provides both necessary and sufficient conditions for optimality—making complementary slackness a key bridge from linear to broader convex optimization.

7.2 Complementary slackness in quadratic and convex problems

In quadratic programming and more general convex programs, inequality constraints remain paired with multipliers. The same logic persists: if a constraint is strictly satisfied, the multiplier must be zero at an optimal point; if the multiplier is nonzero, the constraint must be active. The geometric reasoning changes from polyhedral facets to curved constraint boundaries, but the complementary structure remains.

7.3 Relationship to Lagrange multipliers

Lagrange multipliers quantify sensitivity of the objective to constraint perturbations. Complementary slackness dictates how these multipliers behave based on whether constraints affect the optimum. Multipliers for inactive inequalities vanish, while multipliers for active inequalities reflect the degree to which the constraint shapes the feasible set at the solution. This relation explains why multipliers are often interpreted as shadow prices in models that fit LP or convex optimization.

8 Common pitfalls

8.1 Misapplying sign conventions

Complementary slackness depends on the precise definition of slack and the assumed nonnegativity or nonpositivity of dual variables. A common mistake is to mix conventions across formulations (e.g., using “slack” that should be nonnegative while treating it as if it were nonpositive). Correct verification requires consistent transformation into a standard primal-dual pair.

8.2 Confusing primal and dual roles

Another error is pairing the wrong constraint with the wrong multiplier or interpreting a dual variable as if it were a primal decision variable. Complementary slackness is fundamentally a matching rule: primal constraint slacks pair with dual variables, and dual constraint slacks pair with primal variables. Confusion here can lead to incorrect conclusions about which inequalities bind.

8.3 Assuming feasibility automatically implies optimality

Feasibility of a primal or a dual solution alone does not establish optimality. Weak duality only gives bounds, and strong duality requires conditions plus matching objective values (or complementary slackness). A feasible point can be far from optimal, so complementarity and objective matching are essential in certification workflows.