Econ 50Q Section 2: Inequality Constraints and the KKT

Click here for the quiz on this reading.

The Karush-Kuhn-Tucker Method

Up to now, the course has introduced a consumer’s objective function (i.e. their utility function), which they’re trying to maximize, and their constraint (i.e. their budget constraint), which limits the domain of possible bundles.

In the next three lectures, the class will be introduced to the method of Lagrange multipliers to solve the constrained optimization problem (lecture 6), and also to analyze situations in which this method will fail to find the optimum (lecture 7 and lecture 8). Specifically, in , we’ll learn how to build a function called a Lagrangian to help determine which value of a choice variable $\vec{x} \in \mathbb{R}^n$ maximizes an objective $u(\vec{x})$ subject to a budget equality $\vec{p} \cdot \vec{x} = m$.

It’s assumed that students in 50Q have already seen the basic use of the Lagrangian, so this lesson will extend the Lagrangian method to help us solve more general optimization problems. It’s not a bad idea to read the notes for lectures 6 and 7 before reading these notes. And if you’re a little rusty on Lagrange, you should attend the non-Q sections this week and next as well as Q section!

OK, let’s get started by looking at the distinction between binding

Binding and Non-Binding Constraints

We say a constraint is “binding” if the solution to the problem is different when the constraint is present, and when it’s not. In World War I, for example, Stanford students weren’t allowed to leave campus. This was a binding constraint – there are things students likt to do off campus! But if Stanford passed a rule saying students weren’t allowed to travel to Antarctica, for the vast majority of students that would be a non-binding constraint, because even absent such a constraint most students aren’t finding their way to Antarctica.

For example, the unconstrained maximum of the function $f(x)=12x - x^2$ is at $x = 6$; but if you look only at the closed interval $x \in [1,5]$, the constrained maximum is at $x = 5$:

See interactive graph online here.

We can think of this interval $x \in [1,5]$ as being defined by two constraints: $x \ge 1$ and $x \le 5$. The first one is non-binding, because limiting $x$ to be greater than 1 wouldn’t prevent you from finding the unconstrained maximum at $x = 6$. However, the constraint $x \le 5$ is binding, because with that constraint you are prevented from getting to $x = 6$.

More formally, we will say an inequality constraint $x \leq K$ is binding for $x$ if the consumer optimally chooses $x=K$ exactly, and not binding if they choose some $x<K$. Of course, this depends on the value of $K$. Play around with the graph below to see when the constraint is binding, and when it’s not binding:

See interactive graph online here.

As you can see, when $K \le 6$ the constraint is binding, and the solution occurs at $x^\star = K$; and when $K \ge 6$ the constraint is non-binding, and the solution occurs at $x^\star = 6$. More formally, $x^\star = \argmax_{x \le K} 12x - x^2 = \begin{cases}K & \text{ if }K \le 6\\ 6 & \text{ if }K \ge 6\end{cases}$ In Lecture 7, in fact, we’ll look at situations like this; and for the purposes of the core Econ 50 class, we will simply assert that the constraint sometimes binds and sometimes doesn’t; but there’s a more elegant way to solve this problem in a more general way.

The Karush-Kuhn-Tucker Method

The main topic for this lesson is an extension to the Lagrangian framework that will let us handle inequality constraints. The ingredients will start out the same as the usual Lagrangian discussed in the readings for section 6.3:

A vector of choice variables $\vec{x}\in \mathbb{R}^n$, like good 1 and good 2 quantities
An objective function $f(\vec{x})$, that we try to maximize or minimize; for now, this is a utility function $u(\vec{x})$.
An equality constraint on the choice variable of the form $g(\vec{x}) = k$, like the budget constraint $\vec{p} \cdot \vec{x} = m$. The Lagrangian framework will actually work with several equality constraints, as we will see below.
We will call variables we do not get to choose ourselves, like $p_1,p_2,m$, the parameters of the problem.

If these are all we have to deal with, then we have the usual Lagrangian $\mathcal{L}(\vec{x},\lambda)=f(\vec{x})+\lambda (k - g(\vec{x}))$ For example, in section 6.3 of the reading we saw the Lagrangian $\mathcal{L}(\vec{x},\lambda)=u(\vec{x})+\lambda (m - \vec{p} \cdot \vec{x})$ We call $\lambda$ the Lagrange multiplier on the equality constraint.

The new component we will add is one or multiple inequality constraints on the choice variables, like $x_1 \ge 0$ or $x_1 + x_2 \le K$. We will also have a Lagrange multiplier on any inequality constraints, which we will label $\mu$. To set up a Lagrangian with an inequality constraint, first write it in the form $h(\vec{x}) \geq 0$. From there, the full Lagrangian may be written as $\mathcal{L}(\vec{x},\lambda,\mu)=f(\vec{x})+\lambda (k - g(\vec{x})) + \mu h(\vec{x})$ As with a standard Lagrangian, to find the optimal choice $x^\star$, we start by taking the first order conditions with respect to each of the choice variables in $\vec{x}$: $\begin{aligned} \frac{\partial \mathcal{L}}{\partial x_1} &= \frac{\partial f}{\partial x_1} - \lambda \times \frac{\partial g}{\partial x_1} + \mu \times \frac{\partial h}{\partial x_1}= 0\\ \\ \frac{\partial \mathcal{L}}{\partial x_2} &= \frac{\partial f}{\partial x_2} - \lambda \times \frac{\partial g}{\partial x_2} + \mu \times \frac{\partial h}{\partial x_2}= 0\\ \\ \vdots\\ \\ \frac{\partial \mathcal{L}}{\partial x_n} &= \frac{\partial f}{\partial x_n} - \lambda \times \frac{\partial g}{\partial x_n} + \mu \times \frac{\partial h}{\partial x_n}= 0 \end{aligned}$ Then, for the equality constraint, we take the derivative with respect to $\lambda$, which just gives us our equality constraint back: $\frac{\partial \mathcal{L}}{\partial \lambda} = k - g(\vec{x}) = 0 \Rightarrow g(\vec{x}) = k$ However, we do not take the derivative of the Lagrangian with respect to $\mu$ for a $\mu$ first order condition. We rather set up an equation called the “complementary slackness” condition, which looks like $\mu \times h(\vec{x}) = 0$ alongside the conditions that $h(\vec{x})\geq 0$ and $\mu \geq 0$. These conditions, as well as the first order conditions, characterize the optimal $x$ values as well as the Lagrange multipliers’ values.

General Process for solving a problem using KKT

In summary: when solving a KKT problem, you can use the following steps:

Step 1: set up the problem
- write the objective (for today, this is utility)
- write equality constraints as $k - g(\vec{x}) = 0$
- write inequality constraints as $h(\vec{x})\geq 0$
Step 2: write the Lagrangian
Step 3: write complementary slackness conditions, with one for each inequality constraint
Step 4: take the derivative w.r.t. each $x$ and $\lambda$, set to 0
Step 5: solve the system for the case when $\mu=0$ and the case when $\mu>0$. In the $\mu=0$ case, check if the found $x$ values violate the inequality constraint, and reject them if so.

Let’s work through two examples of this: the first with only one choice variable, and the second with two choice variables.

Inequality Constraints with One Choice Variable (Optional)

Let’s put this to the test with the simple univariate example we were looking at before: maximizing $f(x) = 12x - x^2$ subject to the constraint $x \le K$:

See interactive graph online here.

Recall that the solution we found via logic was $x^\star = \argmax_{x \le K} 12x - x^2 = \begin{cases}K & \text{ if }K \le 6\\ 6 & \text{ if }K \ge 6\end{cases}$ Let’s see how to solve this using the KKT method. First, we rewrite the constraint in the form $h(x) \ge 0$, where $h(x) = K - x$. Since there is no equality constraint, the Lagrangian is $\mathcal{L}(x,\mu) = f(x) + \mu h(x) = 12x - x^2 + \mu(K - x)$ The conditions for optimality are therefore: $\begin{aligned} \textbf{First-order condition: } & {\partial \mathcal{L}(x,\mu) \over \partial x} = 12 - 2x - \mu = 0\\ \\ \textbf{Complementary slackness condition: } & \mu(K-x) = 0\\ \\ \textbf{Inequality constraint: } & K - x \ge 0\\ \\ \textbf{Multiplier condition: } & \mu \ge 0 \end{aligned}$ Note that we can write the first-order condition as $\mu = 12 - 2x$ If we plug this into the complementary slackness condition, we get $(12 - 2x)(K - x) = 0$ In order for this to hold, one of two things must be true: either $x = 6$, or $x = K$ (or both). This is just what we found when we played around with the graph!

But which is it? Well, if $x = 6$, $\mu = 12 - 2x = 0$; in order for the inequality constraint $K - x \ge 0$ to hold, we must have $K - 6 \ge 0$, or $K \ge 6$. On the other hand, if $x = K$, then $\mu = 12 - 2K$; in order for the multiplier condition $\mu \ge 0$ to hold, it must therefore be the case that $12-2K \ge 0$, or $K \le 6$. In other words, one of two cases must occur:

$K \ge 6$, $x = 6$ and $\mu = 0$
$K \le 6$, $x = K$ and $\mu = 12-2K$

For example, if $K = 8$, the complementary slackness condition is $(12 - 2x)(8 - x) = 0$ This could hold true if $x = 6$ or $x = 8$; but if $x = 8$, then $\mu = -4$ which violates the constraint condition $\mu \ge 0$, so it must be that $x = 6$.

On the other hand, if $K = 4$, the complementary slackness condition is $(12 - 2x)(4 - x) = 0$ Now we might have $x = 6$ or $x = 4$; but if $x = 6$, then $4 - x < 0$, which violates the inequality constraint $x \le 4$, so it must be that $x = 4$.

In other words, by searching for a value of $x$ that satisfies all four conditions, we find the optimum systematically, regardless of whether the constraint binds or not!

It might help to look at what’s happening here visually by plotting out the Lagrangian function itself, and thinking about what $\mu$ really means. You can think of $\mu$ as being a reward for being within the constraint, and a punishment for exceeding it. Therefore, the Lagrangian is higher than the objective function $f(x)$ to the left of the constraint, and lower than $f(x)$ to the right:

See interactive graph online here.

As a sort of mnemonic, I like to think of the numerical value of $\mu$ as a “pushing force” from the inequality constraint on the optimal point. If $\mu=0$, then the inequality constraint doesn’t really affect/push on us, and so we aren’t actually at the constraint. If $\mu>0$, then we want to go past the constraint, but can’t since it’s pushing us back. Larger $\mu$ indicates that we want to go past the constraint even more. In order for the first-order condition to hold – that is, in order for the Lagrange function to reach its peak at $x = K$ – the punishment $\mu$ for exceeding the constraint must be exactly equal to the value of exceeding the constraint at that point, i.e. $f^\prime(K)$.

For this reason, in a utility setting, you can think of $\mu$ as the marginal utility of “relaxing” the constraint, meaning the marginal utility of taking a constraint like $x \leq K$ and making it $x \leq K + 1$. If $K = 8$, then relaxing the constraint $x \leq K$ makes no difference to us, because it’s not binding anyway, so we need no punishment for exceeding the constraint to get us to do the right thing. But if $K = 4$, relaxing the constraint would allow us to get to a higher value of $f(x)$, so we need a punishment $\mu > 0$ for exceeding the constraint.

Practically, this leaves us with two cases to check when doing KKT problems:

In one case, the constraint does not bind, and so $\mu=0$ in the system of equations
In the other case, the constraint does bind, and so we can set $h(x)=0$ when solving the system of equations

Let’s wrap this up by looking at how this applies to a standard utility maximization problem with two choice variables.

Inequality Constraints with Two Choice Variables

Let’s work through an example of an inequality constraint in an economic context with two choice variables, one equality constraint (the budget line), and one inequality constraint. Specifically, let’s think about a problem in which for some reason you can’t consume more than a certain amount of good 1.

We’ll build off the utility maximization problem from lecture 6: maximizing the utility function $u(x_1,x_2) = x_1^{3 \over 4}x_2^{1 \over 4}$ subject to the constraint $4x_1 + 2x_2 = 48$. Let’s make our lives a little easier mathematically and transform the utility function (by taking the natural log and multiplying by 4) to be $u(x_1,x_2) = 3 \ln x_1 + \ln x_2$ Therefore the Lagrangian for this problem is $\mathcal{L}(x_1,x_2,\lambda) = 3 \ln x_1 + \ln x_2 + \lambda(48 - 4x_1 - 2x_2)$ which gives us a solution at $(9,6)$:

See interactive graph online here.

Let’s now impose an inequality constraint on this problem: let’s say that this store limits purchases of good 1 to 4 units per customer: that is, $x_1 \le 4$. Let’s solve for the constrained optimal bundle using the KKT method, including the Lagrange multipliers $\lambda$ and $\mu$.

Step 1: Set up the problem $\begin{aligned} \text{objective:} \quad & u(x_1,x_2) = 3 \ln x_1 + \ln x_2\\ \text{equality constraint:} \quad & g(x_1,x_2) = 48 - 4x_1 - 2x_2 = 0\\ \text{inequality constraint:} \quad & h(x_1,x_2) = 4 - x_1 \geq 0 \end{aligned}$

Step 2: Write the Lagrangian $\begin{aligned} \mathcal{L}(x_1,x_2,\lambda,\mu) &= u(x_1,x_2) + \lambda g(x_1,x_2) + \mu h(x_1,x_2)\\ &= 3 \ln x_1 + \ln x_2 + \lambda(48 - 4x_1 - 2x_2) + \mu(4 - x_1)\end{aligned}$

Step 3: Write complementary slackness $\mu(4 - x_1) = 0$ This is equivalent to saying either $\mu=0$ (that is, the constraint is slack and does not bind), or $(4-x_1)=0$ (which implies $x_1=4$ and so the constraint binds). We do not yet know which will be the case.

Step 4: First-order conditions $\begin{aligned} \frac{\partial \mathcal{L}}{\partial x_1} &= \frac{3}{x_1} - 4\lambda - \mu = 0\\ \\ \frac{\partial \mathcal{L}}{\partial x_2} &= \frac{1}{x_2} - 2\lambda = 0\\ \\ \frac{\partial \mathcal{L}}{\partial \lambda} &= 48 - 4x_1 - 2x_2 = 0\end{aligned}$

Step 5: Solve each case. We need to check whether the inequality constraint will affect our choice or not. The most straightforward approach I like to use is to assume the constraint does not bind, look at the implied solution, and see whether we violate the inequality constraint.

Case 1: $\mu = 0$ (constraint slack): We can start by plugging $\mu=0$ into the first order conditions and solving for $\lambda$. This gives us just the same tangency condition as we had in the readings for lecture 6: $\frac{3}{x_1} = 4\lambda, \quad \frac{1}{x_2} = 2\lambda \implies x_2 = {2 \over 3}x_1$ As in that reading, we then plug the result into the budget constraint to find the optimum at $(9,6)$. However, this violates the constraint $x_1 \leq 4$, so we conclude $\mu$ must not be zero – that is, the inequality constraint $x_1 \le 4$ must bind.

Case 2: $\mu > 0$ (constraint binds): If the constraint binds, we know that $x_1 = 4$. This means our first-order conditions are now: $\begin{aligned} \frac{\partial \mathcal{L}}{\partial x_1} &= \frac{3}{4} - 4\lambda - \mu = 0\\ \\ \frac{\partial \mathcal{L}}{\partial x_2} &= \frac{1}{x_2} - 2\lambda = 0\\ \\ \frac{\partial \mathcal{L}}{\partial \lambda} &= 48 - 4 \times 4 - 2x_2 = 0\end{aligned}$ The last equation tells us $x_2 = 16$; plugging this into the second gives us $\lambda = 1/32$; plugging that into the first gives us $\mu = 5/8$. Since $\mu > 0$ is consistent with a binding constraint, this is the solution.

How do we interpret the two multipliers? Think about what would happen if each one were relaxed by a bit. The multiplier $\lambda$ measures the effect of the budget constraint; it says how much additional utility you’d get if you had another dollar. In this case, if you had another dollar, you would have to spend it on good 2, since you’re already buying the maximum possible good 1. Since $p_2 = 2$, this means you could buy 1/2 unit of good 2, which would increase your utility by $\Delta u = {1 \over p_2} \times MU_2(4,16) = {1 \over 2} \times {1 \over 16} = {1 \over 32}$ This is, indeed, what we found for $\lambda$!

On the other hand, if the restriction $x_1 \le 4$ was relaxed by one, you would buy one more unit of good 1, and two fewer units of good 2: therefore your change in utility would be $\Delta u = 1 \times MU_1(4,16) - 2 \times MU_2(4,16) = {3 \over 4} - {2 \over 16} = {5 \over 8}$ which is the value we found for $\mu$.

The diagram below shows how $x_1, x_2, \lambda,$ and $\mu$ change as the restriction $x_1 \le K$ changes. Before you play with it: what do you think happens to $\mu$ if $K > 9$?

See interactive graph online here.

The General Case

A more general Lagrangian, with $n$ choice variables, $N_E$ equality constraints, and $N_I$ inequality constraints, will look like this: $\mathcal{L} = u(x) + \sum_{j=1}^{N_E} \lambda_j h_j(x) + \sum_{k=1}^{N_I} \mu_k g_k(x)$

where each $h_j(x) = 0$ is one of the $N_E$ equality constraints, with multiplier $\lambda_j$, and each $g_k(x) \geq 0$ is one of the $N_I$ inequality constraints, with multiplier $\mu_k$.

The first-order conditions consist of one equation for each of the $n$ choice variables, $\frac{\partial \mathcal{L}}{\partial x_i} = \frac{\partial u}{\partial x_i} + \sum_{j=1}^{N_E} \lambda_j \frac{\partial h_j}{\partial x_i} + \sum_{k=1}^{N_I} \mu_k \frac{\partial g_k}{\partial x_i} = 0 \quad \text{for } i = 1, \dots, n$ and one equation for each of the $N_E$ equality multipliers, $\frac{\partial \mathcal{L}}{\partial \lambda_j} = h_j(x) = 0 \quad \text{for } j = 1, \dots, N_E$ As before, we do not differentiate with respect to the $\mu_k$; instead each of the $N_I$ inequality constraints contributes a complementary slackness condition, $\mu_k \, g_k(x) = 0, \quad \mu_k \geq 0 \quad \text{for } k = 1, \dots, N_I$

Reading Quiz

That's it for today! Click here to take the quiz on this reading.