optional · interactive figures
04
Explore: ellipsoid and interior point
The ellipsoid method cut by cut, the central path under a slider, and the one-variable barrier.
optional: nothing in the lab depends on it back to the slides
These figures support the slides; they don't replace them, and the unit is complete
without them. Each one is computed from the unit's own data or reference solution, so
what you see agrees with the numbers on the slides.
Inside a figure, the arrow keys and drags belong to the figure; click outside it (or
press Esc) to use them for the slides again.
04 · explore
The ellipsoid method, one cut at a time
Try: step the deck's example, then the thin corner; on the empty set, tick "zoom to the ellipse" and watch the area shrink. Static version: two ellipsoid steps .
What it shows. Each step: the current ellipse (solid), the previous one (dashed), the
green target region, the centre, and the cut through the centre parallel to the most violated
row, with the kept half shaded. The run replays the loop of the reference
ellipsoid_feasible, calling the reference ellipsoid_step; centres and
matrices are recorded by slides/viz/traces/u04.py, and the ellipses are drawn from
them in the page.
The deck's example ($x + y \ge 3$): two cuts, as on the slide, centre $(1.96, 1.96)$.A thin corner : six cuts; the ellipse flattens along the target's direction.An empty set ($y \ge 0.2$ and $y \le 0.1$): every step keeps 0.77 of the area, forever. After enough steps no ball of the promised radius fits, and the method answers "empty".
04 · explore
Along the central path
Try: slide t from left to right; watch y approach (0, 0, 1.5, 0.5) and every y·s stay equal to 1/t. Static versions: the central path , duality on the path .
What it shows. The central path of $\max 2x + y$ on unit 01's polygon, from the
reference central_path with $t_0 = 0.01$ and $\mu = 1.25$ (56 points, up to
$t \approx 2100$). For each point: the slacks, the dual point $y = 1/(ts)$, the check
$A^\top y = c$, and the gap $b^\top y - c^\top x$ against $m/t$.
At small $t$ the point sits near the analytic centre; as $t$ grows it bends toward $(2.5, 1.5)$.
Every product $y_i s_i$ equals $1/t$: approximate complementary slackness, the same value in every row.
The gap and $m/t$ agree to the centering tolerance (they differ in the fourth decimal at the largest $t$).
04 · explore
The barrier on one variable
Try: slide t over four orders of magnitude; the minimizer walks from ½ toward 1 and the gap is always 2/t. Static version: the barrier on one variable .
What it shows. $f_t(x) = -tx - \log x - \log(1 - x)$ for $\max x$ on $[0, 1]$, drawn in
the page from the formula, with its minimizer from the closed form
$x^*(t) = (t - 2 + \sqrt{t^2 + 4})/2t$, the dual point $y = (1/(tx), 1/(t(1-x)))$ and the gap.
The walls at 0 and 1 are where the curve shoots up.