Matpic
mathematics, in pictures
Concept

Complementary slackness

The condition that every constraint a solution uses is tight in its dual, and every dual variable that is positive names a constraint met with equality. It is what turns two matching optima into a proof of each other, and it restricts an optimal solution to a much smaller set of candidates.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

applied · Duality A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.

applied · Assignment 3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.

applied · Duality

Named alongside it

The objects these essays reach for when they reach for this one.

DualityCertificateAlgorithmAssignmentLinear programLinear programmingOptimisationShadow priceConvexityDegeneracyDerivativeFeasible region

All concepts