338 ACTIVITY 24: Constrained Optimization: Kuhn Tucker Conditions

WHY:

This activity is designed to help you discover how to solve a nonlinear programming problem with equality and/or inequality constraints. We apply the Kuhn Tucker Conditions to these types of problems, as illustrated in the model below. Note that it is only under very special conditions that sufficient conditions for existence of a relative min are satisfied. In fact, it is not often that the Kuhn Tucker Conditions can be solved to find potential minima. These conditions are most often used to check a point for optimality which has been obtained by some other means.

LEARNING OBJECTIVES:

1. Review how to find potential min points for a problem with equality constraints and discover how to do so when the variables are restricted to be nonnegative.
2. Discover what happens when we change from equality to inequality constraints and use the Kuhn-Tucker conditions.
3. Transfer knowledge from solving unconstrained problems to help in the solution to constrained problems.

PERFORMANCE CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.
   • Completeness
   • Clarity
   • Depth
2. Ability of the team to apply the theory of constrained optimization to practical problems.

INFORMATION:

Kuhn Tucker Conditions

The following conditions are necessary for a point X₀ to solve the problem: minimize f(X) subject to g_k(X) >= 0 for k = 1,2,...,K and h_j(X) = 0 for j = 1,2,...,J. Let the Lagrangian Function F(X,U,V) = f(X) - u_kg_k(X) - v_jh_j(X). The Kuhn Tucker Conditions are as follows:

1. grad f(X₀) - sum u_k grad g_k(X₀) - sum v_j grad h_j(X₀) = 0
2. g_k(X₀) >= 0 for k = 1,2,...,K
3. h_j(X₀) = 0 for j = 1,2,...,J
4. u_kg_k(X₀) = 0 for k = 1,2,...,K
5. u_k >= 0 for k = 1,2,...,K
   
   

THEOREM 5.3.2

Let f be convex, the equality constraints all linear, and the inequality constraints all concave. If a point (X₀, U₀, V₀) satisfies the Kuhn Tucker conditions for this problem, then X₀ is the optimal solution to the problem.

RESOURCES:

1. Section 5.3, Strategic Mathematics
2. 30 minutes

PLAN:

1. Choose roles if you have not already done so.

MODEL:

          Maximize 3.6x - 0.4x2 + 1.6y -0.2y2
          Subject to 2x + y <= 10, x >= 0, y >= 0

We need to change the problem to -min -3.6x + 0.4x² - 1.6y + 0.2y² and let g₁(x,y) = 10 - 2x - y, g₂(x,y) = x,
and g₃(x,y) = y in order to apply the Kuhn Tucker conditions as follows:

1. -3.6 + 0.8x + 2u₁ - u₂ = 0
   
   
2. -1.6 + 0.4y + u₁ - u₃ = 0
   
   
3. g₁(x,y) >= 0 or 10 - 2x - y >= 0
   
   
4. g₂(x,y) >= 0 or x >= 0
   
   
5. g₃(x,y) >= 0 or y >= 0
   
   
6. u₁(10 - 2x - y) = 0
   
   
7. u₂x = 0
   
   
8. u₃y = 0
   
   
9. u₁ >= 0, u₂ >= 0, u₃ >= 0

   If u₁ = 0, u₂ = 0, u₃ = 0, then x = 3.6/.8 = 4.5 and y = 1.6/.4 = 4 but this violates condition 3.

   If u₁ = 0 and either u₂ or u₃ > 0 then conditions 1 or 2 will be violated (I.e. if u₂ > 0 then x = 0 from (7) and (1) becomes -3.6 - u₂ = 0). Thus u₁ > 0, so 2x + y = 10.

   If u₂ and u₃ are both 0, then substituting 10 - 2x for y in (2), and adding it to (1), we get -1.2 + 3u₁ = 0 or u₁ = 0.4.

   Substituting back into (1) and (2) we get x = 3.5 and y = 3. This satisfies all the conditions and is probably the minimum. Substituting this point into the original function, we get a minimum of 12.9.

   The only other possibilities are when either x or y is 0 (i.e. u₂ or u₃ > 0) and this yields the points (0, 10) which violates condition 2 and (5, 0) which violates condition 1. Looking at the Hessian for f, H =

   			| 0.8  0 |
   			|  0  0.4|
   

   we see that it is positive definite. Thus, f is convex and the inequality constraints are all linear and thus concave, so (3.5, 3) is optimal.

   CRITICAL THINKING QUESTIONS:

   These will be provided in class.

   SKILL EXERCISES:

   1. Set up problem 5.13 on page 165 assuming that the base of the box is square. Write out the Lagrangian and the Lagrange multiplier conditions for an optimal point. Solve for the potential maximum points. Assume that the variables must be non-negative.
      
      

   ---

   Math 338 Activity 24 -- Revised 12/4/98

   Return to the List of Activities