28
Oct 17

The Kuhn-Tucker theorem: a first look

category: MT3042 Optimisation theory, Optimisation theory No Comments

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 .

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

Post Views: 37

Leave a Reply

You must be logged in to post a comment.