2.1 The Karush-Kuhn-Tucker Method

In lecture 6 of Econ 50, you learned 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$.

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 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.

In the notes for lecture 7, it’s discussed how 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$:

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:

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}\) The method we used in Lecture 7 was to 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.