Raising the bar

The Kuhn-Tucker theorem: a first look

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

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

(1) $latex 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 $latex 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) $latex \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) $latex C_\eta=\{(x,y):g(x,y)=\eta\}$, $latex \eta\geq 0$. Obviously, the constrained set $latex \{(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 $latex C_0$ with those on $latex C_\eta$ for $latex \eta>0$.

Applying the Lagrangian multiplier interpretation

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

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

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

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

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

Conclusion. If a constraint is efficient, then the Lagrange multiplier is nonnegative.