optional · interactive figures

Explore: gradients and constraints

Gradient methods on an elongated bowl you can reshape by choosing the step, and Frank–Wolfe's corner-hopping on the simplex.

optional: nothing in the lab depends on itback to the slides

29 · explore

Gradient steps on a κ = 10 bowl

Try: the step presets; t just under and over 0.2; momentum; drag the start onto an axis. Static version: gradient steps.

What it shows. $f(x, y) = \tfrac12(x^2 + 10y^2)$, so $L = 10$ and $\mu = 1$. Every iterate is computed in the page, with the same update rules as the reference gradient_descent, heavy_ball and nesterov; before drawing, the page checks its first 12 iterates for $t = 0.1$, $t = 0.19$, heavy ball ($t = 0.1$, $\beta = 0.5$) and Nesterov ($t = 0.1$) against the reference solution's, recorded by slides/viz/traces/u29.py, and refuses to draw if they differ.

$t = 1/L = 0.1$: $y$ is killed in one step (factor 0), $x$ crawls by 0.9 per step. The slide's table.
$t = 0.19$: $y$ flips sign every step (factor $-0.9$): the zig-zag.
$t = 0.21$: the factor for $y$ is $-1.1$ and the iterates fly off: past $2/L$ gradient descent diverges.
$t = 2/(L + \mu) \approx 0.18$: both factors have size $9/11$, the best any fixed step can do.
Heavy ball and Nesterov with $t = 0.1$: momentum carries the iterates along the flat $x$ direction faster.
Start on the $x$-axis: the steep direction never gets excited, and the step's effect on $y$ stops mattering.

29 · explore

Frank–Wolfe and projected gradient

Try: step Frank–Wolfe and watch the oracle hop between corners; switch to projected gradient in the menu. Static version: projection and Frank–Wolfe.

What it shows. Minimising $\tfrac12\|x - p\|^2$ over $\{x \ge 0,\ x_1 + x_2 + x_3 \le 1\}$ with $p = (0.8, 0.6, -0.2)$, drawn in an oblique view of the tetrahedron (the shaded face is $x_3 = 0$). Both runs are recorded by slides/viz/traces/u29.py from the reference frank_wolfe (its oracle is simplex_lmo, unit 02's simplex method) and projected_gradient with step 0.5.

Frank–Wolfe's first rows match the slide: gaps 0.80, 0.80, 0.36 and $f$ = 0.52, 0.22, 0.13.
The dashed line points from the iterate to the corner the oracle picked; the step size is $2/(k+2)$.
The gap always bounds $f - f^*$ from above, which is why solvers can stop on it.
Projected gradient starts from the projection of the origin onto $x_1 + x_2 + x_3 = 1$, $(\tfrac13, \tfrac13, \tfrac13)$, and reaches $(0.6, 0.4, 0)$ in a few steps.