Back to the on-screen lesson ·
Inequalities, complementary slackness, the sign condition, and when a KKT point is the answer.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the four KKT conditions, apply them to a small problem by guessing an active set and checking the guess, and read complementary slackness as the statement that a constraint which does not bind has no price. You will also be able to say why the multiplier on a $\le$ constraint must be non-negative, and when the conditions are merely necessary as against sufficient — which is exactly when the problem is convex.
Lagrange multipliers for equality constraints, and the reading of a multiplier as a price. Inequalities need one more idea: a constraint that is not binding should not influence the answer at all, and the conditions have to say so. That idea is complementary slackness, and it is the whole of the difference.
Inequality constraint: $g(x) \le b$. It may be touched or not, and which it is changes everything about the multiplier.
Active (binding): the constraint holds with equality at the point. Inactive: it holds strictly.
Primal feasibility: the decision satisfies every original constraint.
Dual feasibility: every inequality multiplier has the required sign — non-negative for a $\le$ constraint in a minimisation.
Stationarity: the objective's gradient is balanced by the active constraints' gradients.
Complementary slackness: $\mu\,(b - g(x)) = 0$ for each inequality — the slack or the multiplier is zero.
Constraint qualification: a regularity condition on the active gradients; without it the KKT conditions need not hold at an optimum.
Minimise $f(x)$ subject to $g_i(x) \le 0$ and $h_j(x) = 0$. The Karush–Kuhn–Tucker conditions at $x^\star$, with multipliers $\mu_i \ge 0$ and $\lambda_j$ free:
| Condition | Statement | What it says |
|---|---|---|
| Primal feasibility | $g_i(x^\star) \le 0$, $h_j(x^\star) = 0$ | the point is allowed |
| Dual feasibility | $\mu_i \ge 0$ | prices of $\le$ constraints are non-negative |
| Stationarity | $\nabla f + \sum_i \mu_i \nabla g_i + \sum_j \lambda_j \nabla h_j = 0$ | no feasible direction improves |
| Complementary slackness | $\mu_i\, g_i(x^\star) = 0$ for every $i$ | a slack constraint has no price |
The last is the new one, and it is the one that makes inequalities work. It says: for each constraint, either it binds or its multiplier is zero. A limit nothing is pressing against is worth nothing to relax — which is obvious as economics and is exactly what the algebra needs in order to ignore the inactive constraints.
Why $\mu \ge 0$. The multiplier is the rate at which the optimum improves as the constraint is loosened. Loosening enlarges the feasible set, and a minimum over a larger set cannot be worse. So the rate cannot have the wrong sign. Equality multipliers are free in sign because "loosening" is not defined for them.
What the conditions are. Necessary at a local minimum, given a constraint qualification. Sufficient when the problem is convex — convex objective, convex inequality constraints, affine equality constraints. That is the payoff: for a convex problem, a KKT point is the solution, and the multipliers come with it as prices.
Another way: picture
A ball resting in a bowl that has been tilted, inside a fence. Where the ball settles, either it is away from the fence and the ground is level there, or it is against the fence and the fence is pushing back exactly hard enough. The push is the multiplier; a stretch of fence the ball is nowhere near pushes with force zero.
Another way: steps
To use the conditions on a small problem:
Minimise $(x - 5)^2$ subject to $x \le 3$, $x \ge 0$. Write the second as $-x \le 0$.
Guess: neither active. Then both multipliers are zero, stationarity gives $2(x-5) = 0$, so $x = 5$ — which violates $x \le 3$. The guess fails on feasibility.
Guess: $x \le 3$ active. Then $x = 3$ and $\mu_2 = 0$. Stationarity: $2(3 - 5) + \mu_1 = 0$, so $\mu_1 = 4 \ge 0$. Feasibility: $3 \ge 0$ holds. Every condition checks out.
So the optimum is $x = 3$ with $\mu_1 = 4$: one more unit of allowance would improve the objective by about $4$. The problem is convex, so the KKT point is the answer and no further argument is needed — which is lesson 9 doing its work again.
Ignoring complementary slackness. Leaving a non-zero multiplier on an inactive constraint gives a point that satisfies stationarity and is not optimal.
Forgetting the sign check. A negative $\mu$ on a $\le$ constraint means the active-set guess was wrong: that constraint should be inactive. It is a signal, not an error.
Writing constraints in mixed directions. $g \le 0$ and $g \ge 0$ have multipliers of opposite sign. Put every inequality in one direction before starting.
Quoting sufficiency without convexity. The conditions are necessary in general and sufficient only for convex problems. On a non-convex problem a KKT point can be a saddle or a local maximum, and lesson 9's whole warning applies.
It looks like a failure — the method returned nothing for this constraint — and it is the opposite. A zero multiplier says the constraint is not what is stopping you, so relaxing it buys nothing and tightening it costs nothing until it starts to bind. In a model with forty constraints, typically a handful have non-zero multipliers and the rest are zero, and that short list is the whole of what a manager can act on. Reading the zeros as noise and only looking at the non-zeros is the right instinct; reading a zero as "the method could not price this" is the mistake, and it leads people to go looking for a number that is already there.
Minimise $(x-2)^2$ subject to $x \le 7$. The unconstrained minimiser is $x = 2$.
Check the unconstrained answer first.
It is feasible: $2 \le 7$, with slack $5$. So the constraint does not bind, and complementary slackness forces $\mu = 0$.
Slack constraint, zero price.
Stationarity reduces to the unconstrained condition, and the answer is $x = 2$ with $\mu = 0$. The price is zero and that is a real piece of information: buying more allowance here is worth nothing, so a manager should stop asking for it.
A zero multiplier is an answer, not an absence.
Minimise $x^2 + y^2$ subject to $x + y \ge 4$ and $x \le 10$. Rewrite: $4 - x - y \le 0$ and $x - 10 \le 0$.
One direction for every inequality.
Guess the first active, the second not: $\mu_2 = 0$, $x + y = 4$. Stationarity gives $2x = \mu_1$ and $2y = \mu_1$, so $x = y = 2$ and $\mu_1 = 4 \ge 0$.
Solve under the guess.
Check: $x = 2 \le 10$ holds, so the inactive guess was right, and $\mu_1 \ge 0$. Answer $(2,2)$, value $8$, and the only constraint worth negotiating is the first — worth about $4$ per unit relaxed, while the second is worth nothing.
The check is what makes the guess a proof.
Unconstrained minimiser $(1,1)$: is it feasible? $1 + 1 = 2 > 1$, so no. The budget constraint must be active.
Always start with the unconstrained answer.
Guess the non-negativities inactive. With $x + y = 1$, stationarity gives $2(x-1) + \mu = 0$ and $2(y-1) + \mu = 0$, so $x = y = 1/2$, and $\mu = 2(1 - 1/2) = 1 \ge 0$.
Check: $x = y = 1/2 > 0$, so the non-negativities really are inactive and their multipliers are zero. Every condition holds, the problem is convex, so $(1/2, 1/2)$ is the optimum — and $\mu = 1$ says one more unit of budget would improve the objective by about $1$.
Match each KKT condition to the fact it checks about a candidate.
| The decision satisfies every original constraint | Each inequality multiplier has the required sign | Objective and constraint gradients balance | A slack constraint has zero multiplier | |
|---|---|---|---|---|
| Primal feasibility | ||||
| Dual feasibility | ||||
| Stationarity | ||||
| Complementary slackness |
Minimise $(x - 6)^2$ subject to $x \le 4$ and $x \ge 0$. Where is the optimum?
Answer:
For the same problem, the optimum is $x = 4$. Fill in the slack and the multiplier of each constraint.
| slack at the optimum | multiplier | |
|---|---|---|
| $x \le 4$ | ||
| $x \ge 0$ |
Build the argument that a constraint with slack at the optimum has multiplier zero.
This task has no paper form; do it on a device.
Put the KKT checks in the order it is sensible to do them.
Number the steps in order (write the number in the box):
For a minimisation with $g(x) \le 9$, why must the multiplier be non-negative?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For the same problem, the optimum is $x = 3$. Fill in the slack and the multiplier of each constraint.
| slack at the optimum | multiplier | |
|---|---|---|
| $x \le 3$ | ||
| $x \ge 0$ |
You can apply the KKT conditions, use complementary slackness to eliminate inactive constraints, and say when a KKT point is the answer rather than a candidate. Next: the bound that makes all of this checkable — duality.
10. Your turn: minimise $(x-1)^2 + (y-1)^2$ subject to $x + y \le 1$, $x, y \ge 0$, step 3