Follow the central path to the optimal vertex
AdvancedOPT 07 · Equality Constraints and Interior-Point MethodsInteractive plot
Description
Raise the barrier weight t on a two-variable linear program and watch the central point, its dual bound and the gap m/t.
Try this: Multiply t by ten. How do the distance to the boundary, the true suboptimality and the bound m/t change? Then rotate the objective: does the path still end at a vertex?
Hints
The chapter section that uses this lab:
Explanation
Answer the prediction first, or open the explanation when you are ready.
Show the explanation
The gap is exactly m/t, so it is inversely proportional to t. With m = 5 constraints it is 5/t: 0.5 at t = 10 and 0.05 at t = 100. The central point moves toward the optimal vertex, and its true suboptimality never exceeds that bound.
Lab · Follow the central path to the optimal vertex
- Gap m/t
- 0.5
- Suboptimality c·x − p*
- 0.1841
- Distance to nearest edge
- 0.109
At t = 10 the central point is 0.109 from the nearest edge. Its suboptimality 0.1841 is at most the duality gap m/t = 0.5, and the gap computed from the dual point λ = 1/(t·slack) is 0.5.
Try this: Multiply t by ten. How do the distance to the boundary, the true suboptimality and the bound m/t change? Then rotate the objective: does the path still end at a vertex?
Minimize c·x over a convex pentagon with m = 5 edge constraints a_i·x ≤ b_i. The central point minimizes t·c·x − Σ log(b_i − a_i·x) (damped Newton). With λ_i = 1/(t s_i), where s_i is the slack, the dual objective is −b·λ and the duality gap equals Σ λ_i s_i = m/t exactly. The true suboptimality c·x − p* is at most m/t.