Back to the on-screen lesson ·
Barriers, the central path, the duality gap as a stopping rule, and when to prefer this to simplex.
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 write the barrier form of a constrained linear program, say why its minimiser is always strictly inside the feasible region, and describe the central path as what the minimiser traces as the barrier parameter falls. You will also be able to read a duality gap as an interior point method's stopping rule, and to choose between simplex and interior point for a given problem on the grounds that actually decide it — size, sparsity, whether an exact vertex is needed, and whether the problem will be re-solved.
Simplex, which walks the boundary from vertex to vertex, and duality from lesson 13, which supplies a gap. This lesson is the other way to solve the same problem — go through the middle — and it is the one that made million-variable linear programming routine.
Simplex lives on the boundary. An interior point method stays strictly inside and approaches the optimum from within.
The barrier. Replace the constraints with a penalty that blows up as they are approached. For $\min c^\top x$ subject to $Ax \le b$:
$$\min\ c^\top x - \mu \sum_i \log(b_i - a_i^\top x).$$
Each term is finite while the slack $b_i - a_i^\top x$ is positive and tends to $+\infty$ as it tends to zero. So the problem is now unconstrained — the constraints are enforced by the objective itself — and lesson 16's Newton method applies directly.
The central path. The solution depends on $\mu$. Large $\mu$: the barrier dominates and the answer sits deep inside, near the "analytic centre". Small $\mu$: the objective dominates and the answer approaches the true optimum. The curve traced as $\mu \to 0$ is the central path, and it ends at the optimal vertex.
The method. Follow that path. Do not solve each barrier problem exactly — take one Newton step, reduce $\mu$, repeat. A primal-dual method tracks a dual point alongside, which gives a duality gap at every iteration and hence a stopping rule with a guarantee.
| Simplex | Interior point | |
|---|---|---|
| Where it lives | the boundary | strictly inside |
| Answer | an exact vertex, finitely | converges, never arrives |
| Iterations | usually modest, exponential worst case | a few dozen, almost regardless of size |
| Per iteration | one cheap pivot | one large sparse solve |
| Warm starts | excellent | poor |
Both are in every serious solver, and neither has replaced the other.
Another way: picture
A polygon with a curve drawn from somewhere near its middle to one corner. Simplex hops along the edges of the polygon; the interior point method glides along that inner curve. As the barrier weakens, the curve bends towards the corner and never quite touches it.
Another way: steps
A primal-dual interior point method:
Minimise $-x$ subject to $x \le 4$ and $x \ge 0$. The answer is obviously $x = 4$.
The barrier problem is $\min\ -x - \mu\log(4 - x) - \mu\log(x)$. Differentiating and setting to zero:
$$-1 + \frac{\mu}{4-x} - \frac{\mu}{x} = 0.$$
At $\mu = 1$ this gives roughly $x \approx 3.24$; at $\mu = 0.1$, about $3.90$; at $\mu = 0.01$, about $3.99$. The minimiser walks up towards $4$ and never reaches it.
That is the central path, computed. Notice two things: the constraints never appeared as constraints — the barrier enforced them — and the iterates are strictly feasible throughout, so the run can be stopped at any point and the current answer is usable.
Starting on the boundary. The barrier is infinite there. Interior point methods need a strictly feasible start, and finding one is a phase of its own, exactly as simplex needs a starting vertex.
Reducing $\mu$ too fast. The Newton step is only good near the central path. Cut $\mu$ aggressively and the iterate falls off the path and the step fails. The reduction factor is the main tuning knob and it is conservative for a reason.
Expecting an exact vertex. The method converges to one and stops short. When a vertex is genuinely needed — branch and bound needs a basis — a crossover step is run afterwards, and it is not free.
Warm-starting it. Re-solving after a small change is simplex's great strength and interior point's weakness: the previous interior solution is near the boundary and is a poor place to restart a barrier method from.
Interior point methods never land exactly on the answer, and that sounds like a concession next to simplex's exact vertex. It usually is not. The method reports a duality gap, so the answer comes with a proof of how far from optimal it can possibly be — typically $10^{-9}$ relative, which is smaller than the error in any input the model was built from. An exact optimum of a model whose costs are known to two significant figures is exact about the wrong thing. Where exactness genuinely matters is structural rather than numerical: branch and bound needs a vertex, with a basis, and that is what the crossover step exists to supply.
Each iteration reduces $\mu$ by a constant factor, so the number of iterations needed to get from $\mu_0$ to a tolerance depends on their ratio, not on the size of the problem.
The count is set by the parameter schedule.
Theory gives a bound proportional to $\sqrt{n}$ times the number of digits wanted; practice is blunter — a few dozen iterations, whether the problem has a thousand variables or a million.
Nearly size-independent.
What does grow is the cost per iteration: one solve on a matrix the size of the problem. So the method's scaling is the scaling of sparse linear algebra, which is a well-studied thing with good software — and that transfer of the difficulty is the real reason interior point methods changed what was solvable.
The difficulty moved somewhere better understood.
At some iteration, the primal point is feasible with value $55$ and the dual point is feasible with value $48$.
Both points maintained together.
By weak duality the optimum is between them, so the current plan is within $7$ of optimal — a fact, not an estimate.
The gap is a bound.
If $7$ is immaterial for the decision, stop now. This is the same stopping rule branch and bound uses in unit 4, on a problem where the gap will not close — which is why lesson 13 sits where it does, before any of the methods that rely on it.
One stopping rule, two units.
The slacks are $5 - 2 = 3$ and $2 - 0 = 2$; both positive, so the point is strictly inside and the barrier is finite.
Slacks first: they must all be positive.
The barrier objective is $-2 - \log 3 - \log 2 \approx -2 - 1.10 - 0.69 = -3.79$.
Now try $x = 4.99$: the objective term improves to $-4.99$, but $-\log(0.01) \approx 4.6$ swamps it, giving about $0$ — worse. With $\mu = 1$ the barrier is still holding the iterate well away from the boundary, and only reducing $\mu$ lets it approach. That trade, at every iteration, is the method.
For the constraint $x \le 4$ the barrier uses the slack $4 - x$. What is the slack at $x = 3$?
Answer:
The barrier parameter is reduced from $5$ towards zero. What happens to the minimiser of the barrier problem?
| Minimiser lies deep inside the feasible region | Minimiser approaches the true optimum | Central path | Take an approximate Newton step before reducing the parameter | |
|---|---|---|---|---|
| Large barrier parameter | ||||
| Barrier parameter near zero | ||||
| Track of barrier minimisers | ||||
| Practical path-following update |
An interior point run has a primal value of $55$ and a dual value of $48$. How far from optimal is the current point, at worst?
Answer:
Why can an interior point method never reach the boundary of the feasible region exactly?
| Approaches the feasible boundary | Tends to positive infinity | Remains strictly inside the region | Use a crossover procedure after convergence | |
|---|---|---|---|---|
| Slack tends to zero | ||||
| Barrier term $-\mu\log(\text{slack})$ | ||||
| Barrier-problem minimiser | ||||
| Need for an exact boundary vertex |
For the constraint $x \le 11$ the barrier uses the slack $11 - x$. What is the slack at $x = 1$?
Answer:
A linear program has two million variables and a sparse constraint matrix. Which method is the safer choice?
| A strong use case for interior point | A strong use case for simplex warm starts | Walks boundary pivots and returns an exact vertex | Uses a few large sparse solves while crossing the interior | |
|---|---|---|---|---|
| Huge sparse linear program | ||||
| Repeatedly re-solved problem with small changes | ||||
| Simplex | ||||
| Interior point |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The barrier parameter is reduced from $7$ towards zero. What happens to the minimiser of the barrier problem?
| Minimiser lies deep inside the feasible region | Minimiser approaches the true optimum | Central path | Take an approximate Newton step before reducing the parameter | |
|---|---|---|---|---|
| Large barrier parameter | ||||
| Barrier parameter near zero | ||||
| Track of barrier minimisers | ||||
| Practical path-following update |
You can form a barrier problem, explain the central path, and choose between the two linear programming methods on real grounds. Next: the quadratic case, which closes unit 3.
9. Your turn: what is the barrier objective at $x = 2$ for $x \le 5$, $x \ge 0$, with $\mu = 1$ and objective $-x$?, step 3