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