Full search page →

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?

Predict first

You multiply the barrier weight t by 10. What happens to the duality gap m/t?

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

Predict first

You multiply the barrier weight t by 10. What happens to the duality gap m/t?

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.

Method sources

Open in the Playground →