Lagrange multipliers, duality and KKT
How to minimise with constraints — why the gradients line up at the optimum, what a Lagrange multiplier is worth, how every problem has a dual that bounds it from below, when the bound is tight (Slater), the KKT conditions, and the support vector machine's dual derived from scratch.
45 min
After this lesson you can
- Explain geometrically why the gradient of the objective is parallel to the gradient of an active constraint at a constrained optimum
- Form the Lagrangian and the Lagrange dual function, and prove weak duality
- State Slater's condition and what strong duality buys
- Write down the KKT conditions, derive complementary slackness, and say when KKT is necessary and when it is sufficient
- Interpret a multiplier as the sensitivity of the optimal value to the constraint
- Derive the dual of the hard-margin support vector machine and identify the support vectors from complementary slackness
In this lesson
- One constraint: the gradients line up
- Inequality constraints: active or not
- The Lagrangian and the dual
- Strong duality and Slater’s condition
- The KKT conditions
- What a multiplier is worth
- Worked example: the support vector machine’s dual
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.