min x² s.t. x ≥ 1
x = 1, multiplier λ = 2
2x − λ = 0 at x = 1.
For minimising subject to , the KKT conditions at a minimum are , , and complementary slackness : a constraint either is active or has zero multiplier.
This page is easier if you are comfortable with:
Minimise subject to , i.e. . Stationarity: , , so ; complementary slackness with the active constraint gives , , and the minimum value is 2. The multiplier says that relaxing the constraint by lowers the optimum by about (a shadow price).
Minimise subject to (): and , so . Minimise subject to (): the unconstrained minimum 3 violates the constraint, so the constraint is active, , and gives , with minimum value 4. If the unconstrained minimum were feasible, would be 0.
With only equality constraints the conditions reduce to Lagrange multipliers (Lagrange multipliers); for convex problems (convex functions) the KKT conditions are sufficient as well as necessary. They are the basis of LP duality (linear programming duality) and support vector machines; the stationarity equation uses the gradient.
The KKT conditions describe the balance of forces at the best point of a constrained problem.
The level curve just touches the constraint where the gradients are parallel.
These examples are worked by hand, step by step, so you can compare your own working.
Find the minimum point, multiplier and value.
Find the multiplier at the minimum.
Find the multiplier and the minimum value.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
x = 1, multiplier λ = 2
2x − λ = 0 at x = 1.
x = y = 1, λ = 2
2x = λ.
λ(x − 1) = 0
Active constraint or λ = 0.
f(1, 1) = 2
The constrained minimum.
At a constrained minimum of a convex problem there are multipliers λᵢ ≥ 0 with ∇f + Σ λᵢ∇gᵢ = 0 (stationarity), primal feasibility, and complementary slackness λᵢgᵢ = 0.
Minimise x² subject to x ≥ 1. Find x and λ.
Minimise x² + y² subject to x + y = 2.
Find the minimum value.
Minimise (x − 3)² subject to x ≥ 1. Is the constraint active?
λ = −2 ✗
λ ≥ 0 for ≥ constraints (in this form) ✓
Sign convention matters.
λ ≠ 0 and constraint slack ✗
λ(g) = 0 ✓
One of them must be zero.
solved ∇f = 0 ✗
include constraints ✓
Check feasibility.
KKT guarantees optimum ✗
only necessary in general ✓
Convexity makes it sufficient.
Try each one on paper, then open the answer. Use the solver above to see the full working.
2
2
8
4
9
6
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Stationarity, feasibility, λ ≥ 0 and complementary slackness.
For convex problems.
Each multiplier times its constraint is zero.
One holding with equality.
convex functions.
linear programming duality.
More in Numerical methods and optimisation and the formula sheets.