Handout 13 · Interactive chapter

Linear Programming Duality

The chapter’s main idea is that an optimality proof can be packaged as a certificate: choose nonnegative weights for the primal constraints, add them together, and obtain an upper bound on every feasible objective value.

Upper-bound certificates The dual LP Simplex certificates General rule
Primal solution Dual certificate same value at optimality max cᵀx min bᵀy feasible x gives a lower bound feasible y gives an upper bound
Chapter setup

Upper bounds by adding constraints

The opening example asks for an upper bound on the objective value of every feasible solution to the primal LP.

maximize   x1 + x2 + 2x3
subject to   x1 + 2x2 + 3x3 ≤ 12
              2x1 + x2 + 4x3 ≤ 10
              −x3 ≤ −1
              x1, x2, x3 ≥ 0.

A nonnegative combination of the three constraints gives a valid upper bound whenever its left-hand-side coefficients dominate the objective coefficients.

y1(x1+2x2+3x3) + y2(2x1+x2+4x3) + y3(−x3)
= (y1+2y2)x1 + (2y1+y2)x2 + (3y1+4y2−y3)x3.
Key test

When is the certificate valid?

The weights y1, y2, y3 must satisfy two requirements.

Nonnegative weights. Multiplying a ≤ constraint by a negative number reverses the inequality, so the proof would break.
Coefficient domination. The combined coefficients must be at least 1, 1, and 2, respectively.
A valid y produces the bound
x1 + x2 + 2x3 ≤ 12y1 + 10y2 − y3
for every feasible x.

Interactive Build an upper-bound certificate

Move the y-weights to combine constraints. Move x to test a primal solution. The certificate is useful only when y is dual feasible and x is primal feasible.

Constraint weights

checking
Upper bound value—
—
Guided sequence

Click “Next bound” to replay the certificate improvements from the chapter.

Primal test point

checking
Primal objective value—
—
Weak duality comparison will appear here.

Dual feasible region, projected to y₁–y₂

y₃ handled separately

For fixed y₁ and y₂, increasing y₃ lowers the bound, but y₃ cannot exceed 3y₁ + 4y₂ − 2. The optimal certificate is (1/3, 1/3, 1/3).

—
The dual

The best certificate is itself an LP

To find the best upper bound obtainable by this method, minimize the bound value subject to the certificate-validity constraints.

minimize   12y1 + 10y2 − y3
subject to   y1 + 2y2 ≥ 1
              2y1 + y2 ≥ 1
              3y1 + 4y2 − y3 ≥ 2
              y1, y2, y3 ≥ 0.
Weak duality. For every primal-feasible x and every dual-feasible y, the primal objective is at most the dual objective.
Chapter conclusion

Why the inequality is convincing

The dual constraints are exactly the restrictions needed to make the weighted sum of primal constraints dominate the primal objective. Once those conditions hold, the upper bound requires no trust in the simplex pivots that found the solution.

x1 + x2 + 2x3 ≤ 12y1 + 10y2 − y3.

At y = (1/3, 1/3, 1/3), the bound is 7. At x = (1, 4, 1), the primal objective is also 7. Equal lower and upper bounds certify optimality.

From the simplex dictionary

A certificate hiding in the final dictionary

The chapter revisits the LP from the simplex handout.

maximize   2x1 + x2 + x3
subject to   x1 ≤ 4
              x2 ≤ 4
              x1 + x2 ≤ 6
              −x1 + 2x3 ≤ 4
              x1, x2, x3 ≥ 0.

The final dictionary has objective row

maximize   14 − (3/2)x4 − x6 − (1/2)x7.

The negative coefficients of the slack variables x4, x6, x7 produce the certificate weights y = (3/2, 0, 1, 1/2).

Certificate proof

The bound from those weights

(3/2)(x1) + 1(x1 + x2) + (1/2)(−x1 + 2x3)
= 2x1 + x2 + x3.

The weighted right-hand sides give 6 + 6 + 2 = 14. Since the simplex solution also has objective value 14, optimality follows.

This is the same pattern as max flow/min cut: a feasible solution and a matching certificate prove optimality together.

Interactive Check the simplex certificate

Use the sliders to test primal points and dual certificates for the simplex-handout LP. At the optimal pair, every complementary-slackness product is zero and the primal and dual values match.

Primal variables

checking
Primal value—
—

Dual weights

checking
Dual bound—
—

Primal–dual gap

Primal value—
Dual value—
—

Complementary slackness check

At optimality, every product yi·slacki and xj·surplusj is zero.

General rule

Max-≤ primal and min-≥ dual

Primal: maximize cTx subject to Ax ≤ b, x ≥ 0.
Dual: minimize bTy subject to ATy ≥ c, y ≥ 0.
Strong duality. When optimal primal and dual solutions exist, their objective values are equal.
How to read it

Rows become variables; columns become constraints

Each primal constraint receives a dual variable. Each primal variable becomes a dual constraint. The coefficient matrix is transposed.

This is exactly what the certificate argument does: the dual variables are the multipliers used to add the primal constraints.

Interactive Make the dual by transposing the data

Edit the coefficients of a three-constraint, three-variable maximization LP of the form Ax ≤ b, x ≥ 0. The dual updates immediately.

Editable primal data

Generated primal and dual

Primal

Dual

Changing a column of A changes one dual constraint. Changing a row of A changes the coefficients of one dual variable across all dual constraints.

The referenced source image pics/copilot/duality4.png was not included with the TeX upload, so the page uses native SVG diagrams instead.

Free Web Hosting