The Kuhn-Tucker theorem: a first look
In its simplest form, this theorem addresses optimization with an inequality constraint: maximize the objective function subject to the inequality constraint
.
If the solution satisfies
(1)
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 ? Note that when the maximum in fact satisfies (1), we can use the Lagrangian if the implicit function existence condition holds:
(2)
Constrained set as a union of level sets
Consider the curve (level set) ,
. Obviously, the constrained set
is a union of these level sets. We need to compare the values of the objective function on
with those on
for
.
Applying the Lagrangian multiplier interpretation
Assuming (2), let be the Lagrangian multiplier for the equality constrained problem: maximize
subject to
Writing
as
with
we can apply the equation
(3)
where is the maximized value on the curve
. To simplify the notation, the maximizing point on the curve
is denoted
and the maximum value
In terms of the original variable
equation (3) becomes
This equation explains everything. If the value is larger than or equal to
,
, then the derivative (1) is nonpositive, which translates to nonnegativity of
Conclusion. If a constraint is efficient, then the Lagrange multiplier is nonnegative.
Leave a Reply
You must be logged in to post a comment.