Back to the on-screen lesson ·
The dual problem, weak duality as a certificate that needs no convexity, and when the gap closes.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to form the Lagrangian dual of a constrained problem, prove weak duality and say which two sign facts it rests on, and compute and interpret a duality gap. You will also be able to say why a dual bound is a certificate rather than an observation — it bounds the optimum without anybody knowing the optimum — when strong duality closes the gap, and why weak duality remains available on the integer problems of unit 4 where nothing else is.
Multipliers as prices, from lessons 11 and 12, and complementary slackness. Duality is what happens when those prices are promoted from a by-product of the answer to a problem in their own right — and the result is the only device in this course that can prove a method is allowed to stop.
Primal: the problem as posed. Dual: the problem built from its multipliers, one dual variable per primal constraint.
Dual objective: the right-hand sides valued at those multipliers — it prices the resources rather than the plan.
Weak duality: every feasible dual value is a bound on every feasible primal value. It holds always, and costs nothing to use.
Strong duality: the two optima coincide. It holds for linear programs and for convex problems under a qualification, and not in general.
Duality gap: the distance between a feasible primal value and a feasible dual value — what is still unknown about the optimum.
Certificate: a bound that can be checked without redoing the search.
Shadow price: a dual variable read as the worth of one more unit of its constraint.
Start from the Lagrangian of $\min f(x)$ subject to $g_i(x) \le 0$:
$$L(x, \mu) = f(x) + \sum_i \mu_i g_i(x).$$
The dual function is what is left after minimising out $x$:
$$q(\mu) = \inf_x L(x, \mu),$$
and the dual problem is $\max_{\mu \ge 0} q(\mu)$.
Weak duality. For every feasible $x$ and every $\mu \ge 0$, $q(\mu) \le f(x)$.
This holds always — no convexity, no constraint qualification, nothing. Every dual value is below every feasible primal value, so the two problems squeeze the optimum between them. The difference $f(x) - q(\mu)$ is the duality gap.
Strong duality. For a convex problem with a strictly feasible point (Slater's condition), the best dual value equals the best primal value: the gap closes.
Why this is the most useful theorem here. A feasible plan says the optimum is at most this. A dual point says the optimum is at least that. Together they bracket an unknown number, and they do it without anybody knowing it. That is a certificate: the plan in hand is within the gap of optimal, provably, and a method can stop on it. Every early stop with a guarantee in the rest of the course — the bound in branch and bound, the stopping rule of an interior point method — is this.
What the dual is about. In the transport problem, the primal chooses a plan and the dual chooses prices for the resources. The primal asks what should we do; the dual asks what is it worth. When the two values meet, the plan is worth exactly what its resources are.
Another way: picture
A number line with the unknown optimum somewhere on it. Every feasible plan puts a marker above it; every dual point puts a marker below. The markers close in from both sides, and when two meet the optimum is caught exactly.
Another way: steps
To use duality in practice:
Let $x$ be primal feasible and $\mu \ge 0$.
For each $i$: $g_i(x) \le 0$ by feasibility and $\mu_i \ge 0$ by the sign condition, so $\mu_i g_i(x) \le 0$. Summing,
$$L(x, \mu) = f(x) + \sum_i \mu_i g_i(x) \le f(x).$$
And $q(\mu)$ is an infimum over all $z$, so $q(\mu) \le L(x, \mu)$. Chaining, $q(\mu) \le f(x)$.
Notice how little was used: no convexity, no differentiability, no qualification — only the two sign facts. That is why weak duality is available on problems where nothing else is, including the integer programs of unit 4, where it is the entire basis of branch and bound.
Assuming the gap closes. It closes for convex problems with a strictly feasible point. On an integer program it generally does not, and the remaining gap is the thing a search has to work down.
Reading the dual bound as the answer. It is a bound. Reporting $q(\mu)$ as the optimum is claiming the gap is zero without checking.
Forgetting $\mu \ge 0$. A dual point with a negative multiplier is not dual feasible and its value bounds nothing.
Solving the dual because it looks smaller. Sometimes an excellent idea — the dual of a problem with many constraints and few variables is a problem with few constraints and many variables. Sometimes the dual function is harder to evaluate than the primal is to solve. It is a judgement, not a rule.
It is often introduced as a trick for solving the same problem another way, and that undersells it badly. The primal asks what to do; the dual asks what the constraints are worth. They have different variables, different units, and different audiences — a plan is for whoever executes it, prices are for whoever negotiates the constraints. The fact that their optimal values coincide on convex problems is a theorem, and a surprising one, not a definition. And weak duality, which needs no convexity at all, is the more useful half in practice: it is what lets a search on a problem with no strong duality — every integer program in unit 4 — still say how far from optimal it might be.
$\min\ x^2$ subject to $x \ge 2$, that is $2 - x \le 0$. Lagrangian $x^2 + \mu(2 - x)$.
One constraint, one multiplier.
Minimising over $x$: derivative $2x - \mu = 0$, so $x = \mu/2$ and $q(\mu) = \mu^2/4 + \mu(2 - \mu/2) = 2\mu - \mu^2/4$.
The dual function, in closed form.
Pick $\mu = 1$, which is feasible: $q(1) = 2 - 1/4 = 1.75$. Without solving anything, the optimum is at least $1.75$. Maximising instead gives $\mu = 4$ and $q(4) = 4$, which is the true optimum $2^2$ — the gap closes, as it must for a convex problem.
Any $\mu$ gives a bound; the best one closes the gap.
Primal: choose shipments $x_{ij}$ to minimise cost, subject to supplies and demands. Variables are a plan.
What to do.
Dual: choose a price $u_i$ at each factory and $v_j$ at each customer, subject to $v_j - u_i \le c_{ij}$ for every route, maximising $\sum_j d_j v_j - \sum_i s_i u_i$.
What it is worth.
The dual constraint says no route may be profitable to arbitrage: the value gained at the customer minus the cost at the factory cannot exceed the shipping cost. At the optimum the two objectives agree, and complementary slackness says a route is used only when its constraint is tight — used routes are exactly the ones where arbitrage breaks even.
Two descriptions of the same situation, meeting at the optimum.
A feasible plan at $27$ and a dual point at $27$. Weak duality says the optimum is at least $27$ and at most $27$.
Both bounds, at the same number.
So the optimum is exactly $27$, and the plan achieving it is optimal.
And so is the dual point: the argument is symmetric. Two optimality proofs for the price of one, and neither needed the optimum to be known in advance — which is why a solver reporting "gap 0.00%" is making a much stronger statement than one reporting that it converged.
For a minimisation problem, match each object to the bound it supplies.
| Upper bound on the minimum | Lower bound on the minimum | Proof both are optimal | |
|---|---|---|---|
| Feasible primal plan | |||
| Feasible dual point | |||
| Equal feasible primal and dual values |
A feasible plan for a minimisation costs $63$, and a feasible dual point gives the bound $60$. Work out each plan's cost and how far it still is from that bound.
| cost of the plan | gap to the dual bound of $60$ | |
|---|---|---|
| The plan in hand | 63 | |
| A revised plan, $2$ cheaper | ||
| A plan matching the dual bound |
The gap between a feasible plan at $19$ and a dual bound at $12$ is $7$. What has been established?
Build the proof of weak duality: every dual value is at most every feasible primal value.
This task has no paper form; do it on a device.
The primal is $\max\ 2x + 3y$ subject to $1x + 1y \le 4$ and $1x + 3y \le 6$. Write the dual's constraint matrix.
This task has no paper form; do it on a device.
A plan uses $10$ units of the first resource and $7$ of the second, with shadow prices $6$ and $6$. What are the resources worth at those prices?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The gap between a feasible plan at $27$ and a dual bound at $27$ is $0$. What has been established?
You can build a dual, prove weak duality, and read a duality gap as the amount still unknown. That closes unit 2. Next: the methods, starting with the simplest one that works.
10. Your turn: what does a gap of zero prove?, step 3