KKT Conditions: the Saddle Point of the Lagrangian
An interactive live film: the Lagrangian of a constrained problem is a saddle surface; its dual function touches the primal optimum at a Nash equilibrium. Drag (x, eta) until all four KKT conditions hold.
Narration
Minimize x minus two, squared, subject to x being at most c. The red wall is the constraint: only points to its left are allowed. With c equal to one, the best feasible point sits on the wall.
The Lagrangian folds the constraint into the objective with a multiplier eta, which must not be negative. Over the plane of x and eta it is a surface: a bowl in x, and a straight line in eta.
The rest of the narration is in the book's Companion.
More from Chapter 12
Interactive1:08Gradient Descent in an Ill-Conditioned ValleyChapter 12
Preview1:28The Descent Lemma: A Bowl That Bounds Every StepChapter 12
Preview1:33Heavy-Ball Momentum: Zig-Zags Cancel, the Valley Floor Adds UpChapter 12
Preview1:43A Large Step Selects a Flatter MinimumChapter 12
Preview2:12Sophia: Newton Steps with a ClipChapter 12
Preview2:14Adam and AdamW: A Step Size for Every CoordinateChapter 12
Preview1:55Backtracking Line Search and the Armijo ConditionChapter 12
Preview1:50Proximal Gradient and Soft-Thresholding: Exact ZerosChapter 12
Preview1:52Mirror Descent Stays Inside the SimplexChapter 12
Preview1:55The Polyak-Łojasiewicz ConditionChapter 12