Inequality constraints and the KKT conditions

Allowed regions

An inequality constraint $g(x, y) \le c$ allows a whole region: the curve $g = c$ and everything on one side of it. Many limits are like this. A quantity may not be negative, or may not exceed a capacity, but anything within the limit is fine.

Start in one variable, as in lesson 2.4.1: minimise $f(x) = (x - 3)^2$ subject to $x \le c$. The function's own lowest point is $x = 3$.

• $c = 5$: the point 3 is allowed, so the constraint changes nothing. The minimum is $f(3) = 0$, inside the allowed interval.
• $c = 1$: 3 is not allowed. $f$ falls all the way to the edge $x = 1$, where $f = 4$ and the slope is $f'(1) = -4$.

Slack or binding in two variables

Take the bowl $f(x, y) = x^2 + 2y^2$ of lesson 4.5.1 again. Its lowest point is the origin, where $f = 0$.

With $x + y \le 3$, the origin is allowed, since $0 \le 3$. The constraint is slack: the minimum is $(0, 0)$ and $\lambda = 0$.

With $x + y \ge 3$ the origin is not allowed, so the minimum must lie on the edge $x + y = 3$. Lesson 4.5.1 found it: $(2, 1)$, with $f = 6$ and $\lambda = 4$.

The sign of $\lambda$

At a binding constraint the allowed region lies on one side of the edge. At the minimum, no step into the region may go downhill. So $\nabla f$, the uphill direction, points into the allowed side, and that fixes the sign of $\lambda$.

• $x + y \ge 3$: the allowed side is the way $\nabla g = (1, 1)$ points. At $(2, 1)$, $\nabla f = (4, 4) = 4\nabla g$, so $\lambda = 4 \ge 0$.
• $x + y \le -1.5$: the origin is not allowed, and the allowed side is the way $-\nabla g$ points. Lesson 4.5.1's edge minimum is $(-1, -0.5)$, where $\nabla f = (-2, -2) = -2\nabla g$, so $\lambda = -2 \le 0$.
• One variable: for $x \le 1$, $f'(1) = -4$ points to the left, into the allowed side. Here $g = x$ has slope 1, so $\lambda = -4$.

The rate of lesson 4.5.1, $\lambda = \frac{df^*}{dc}$, says the same. Raising $c$ enlarges the region $g \le c$, so the best value can only fall: $\lambda \le 0$. It shrinks the region $g \ge c$, so the best value can only rise: $\lambda \ge 0$.

A wrong sign means a wrong guess

Suppose you guess that $x + y \le 3$ binds. The edge gives $(2, 1)$ with $\lambda = 4$, the wrong sign for a $\le$ constraint: $\nabla f$ points out of the allowed side. A step inward then goes downhill, so the constraint is slack, not binding.

The KKT conditions

The two cases and the sign fit into one list, named after Karush, Kuhn and Tucker.

The last condition, $\lambda(g - c) = 0$, is called complementary slackness. A product is 0 only if a factor is 0, so either $\lambda = 0$ (slack) or $g = c$ (binding).

Both can be 0 at once. With $x + y \le 0$, the bowl's lowest point $(0, 0)$ lies on the edge itself, and there $\nabla f = \mathbf{0}$, so $\lambda = 0$ while $g = c$.

To solve a problem, guess which case holds, solve it, and keep the guess that passes every condition. The table does this for the bowl:

Optimisation books usually write every constraint of a minimum as $g \le c$ and the first condition as $\nabla f + \mu\nabla g = \mathbf{0}$, with $\mu \ge 0$. That is the same list with $\mu = -\lambda$. This module keeps lesson 4.5.1's form, so that $\lambda$ is always the rate $\frac{df^*}{dc}$.

Two constraints

With two constraints, each multiplier belongs to its own constraint.

Minimise the bowl subject to $x + y \ge 3$ and $x \le 1$. Each constraint can be slack or binding, so there are four cases:

The second row is lesson 4.5.1's answer. The third minimises $1 + 2y^2$ on the line $x = 1$. Only the last point is allowed.

Check its signs at $(1, 2)$, where $\nabla f = (2, 8)$, $\nabla g_1 = (1, 1)$ and $\nabla g_2 = (1, 0)$. Solving $(2, 8) = \lambda_1(1, 1) + \lambda_2(1, 0)$ gives $\lambda_1 = 8$ and $\lambda_2 = -6$. The first is $\ge 0$ for a $\ge$ constraint and the second $\le 0$ for a $\le$ constraint, so $(1, 2)$ is the minimum, with $f = 9$.

Each multiplier is a rate again. Moving $c_1$ from 3 changes the best value at the rate 8; moving $c_2$ from 1, at the rate $-6$. Loosen $x \le 1$ to $x \le 2.5$ instead, and $(2, 1)$ is allowed: the second constraint goes slack, with $\lambda_2 = 0$.

With $k$ inequality constraints there are $2^k$ cases. Solvers search them far more cleverly, but they test the same conditions.

Checking with a solver

scipy.optimize.minimize, named in lesson 4.4.3, accepts constraints. Each is a dictionary: "type": "eq" means fun(v) = 0, and "type": "ineq" means fun(v) >= 0. The method "SLSQP" handles both.

So $x + y \ge 3$ is v[0] + v[1] - 3, and $x \le 1$ is 1 - v[0]. A $\le$ constraint must be turned round. Typed as v[0] + v[1] - 3, the constraint meant as $x + y \le 3$ silently becomes $x + y \ge 3$, and the solver returns $(2, 1)$ instead of $(0, 0)$.

Lesson 4.5.3 shows when a point that passes the KKT conditions is sure to be the minimum. Case study 4.5.5 uses them to forbid negative portfolio weights.

Common mistakes

1. Do not assume a constraint binds. With $x + y \le 3$ the bowl's minimum is the origin, inside the region.
2. Check that the point is allowed. The bowl's lowest point, $(0, 0)$, breaks $x + y \ge 3$.
3. Check the sign of $\lambda$. A binding guess for $x + y \le 3$ gives $\lambda = 4$, the wrong sign: the guess is wrong.
4. The sign depends on the direction. With $\nabla f = \lambda\nabla g$, a $\le$ constraint needs $\lambda \le 0$ and a $\ge$ constraint $\lambda \ge 0$. Books that write $\nabla f + \mu\nabla g = \mathbf{0}$ have $\mu = -\lambda$.
5. Complementary slackness allows both factors to be 0. With $x + y \le 0$ the minimum is on the edge and $\lambda = 0$.
6. SciPy's "ineq" means $\ge 0$. Write $x + y \le 3$ as 3 - v[0] - v[1].