The Kuhn-Tucker theorem: a first look

Oct 17

The Kuhn-Tucker theorem: a first look

The Kuhn-Tucker theorem: a first look

In its simplest form, this theorem addresses optimization with an inequality constraint: maximize the objective function $f(x,y)$ subject to the inequality constraint $g(x,y)\geq 0$ .

If the solution $(x^\ast,y^\ast)$ satisfies

(1) $g(x^\ast,y^\ast)=0,$

the constraint is called efficient (binding), otherwise it is called slack (or nonbinding). Here we answer the question: when an efficient constraint is efficient? More precisely, what can be said if the maximum is attained at a point such that (1) is true, as opposed to $g(x^\ast,y^\ast)>0$ ? Note that when the maximum in fact satisfies (1), we can use the Lagrangian if the implicit function existence condition holds:

(2) $\left(\frac{\partial g}{\partial x},\frac{\partial g}{\partial y}\right)\neq 0.$

Constrained set as a union of level sets

Consider the curve (level set) $C_\eta=\{(x,y):g(x,y)=\eta\}$ , $\eta\geq 0$ . Obviously, the constrained set $\{(x,y):g(x,y)\geq 0\}$ is a union of these level sets. We need to compare the values of the objective function on $C_0$ with those on $C_\eta$ for $\eta>0$ .

Applying the Lagrangian multiplier interpretation

Assuming (2), let $\lambda$ be the Lagrangian multiplier for the equality constrained problem: maximize $f(x,y)$ subject to $g(x,y)=0.$ Writing $g(x,y)=\eta$ as $g(x,y)+c=0$ with $c=-\eta$ we can apply the equation

(3) $\frac{dF}{dc}|_{c=0}=\lambda$

where $F(c)=f(x,y(x,c))$ is the maximized value on the curve $C_{c}$ . To simplify the notation, the maximizing point on the curve $C_\eta$ is denoted $(x^\ast(\eta),y^\ast(\eta ))$ and the maximum value $F(\eta)=f(x^\ast(\eta),y^\ast(\eta)).$ In terms of the original variable $\eta$ equation (3) becomes

$\frac{dF}{d\eta }|_{\eta =0}=-\lambda .$

This equation explains everything. If the value $F(0)=f(x^\ast(0),y^\ast(0))$ is larger than or equal to $F(\eta)=f(x^\ast(\eta ),y^\ast(\eta ))$ , $\eta>0$ , then the derivative (1) is nonpositive, which translates to nonnegativity of $\lambda .$