338 ACTIVITY 22: Constrained Optimization: Nonnegative Variables

WHY:

This activity is designed to help you discover how to solve a nonlinear programming problem in which the variables are constrained to be non-negative. We apply Theorem 5.1.1 to these types of problems, as illustrated in the model below. Since most problems in practice require nonnegative variables, this activity will prepare you to deal with real-life problems.

LEARNING OBJECTIVES:

1. Discover how to find relative minima when variables are restricted to be nonnegative.
2. Discover reasoning behind Theorem 5.1.1.
3. Realize the importance of getting back up to speed quickly after a vacation.

PERFORMANCE CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.
   • Completeness
   • Clarity
   • Depth
2. Speed and accuracy exhibited by the team during the activity.

INFORMATION:

Theorem 5.1.1

Let f be twice continuously differentiable defined on the nonnegative orthant {X |X >= 0}. The necessary conditions for f to have a local minimum at X* are:

1. f(X^*) >= 0
2. f(X^*) X^*T = 0 (this is shorthand for F_Xi(X^*) * X_i = 0 for all i)
3. X >= 0

RESOURCES:

1. Section 5.1, Strategic Mathematics
2. 30 minutes

MODEL:

Minimize x² + y² - 2xy where x >= 0 and y >= 0.

We first compute grad f(x, y) = (2x - 2y, 2y - 2x).

The conditions for Theorem 5.1.1 as applied to this problem:

1. 2x - 2y >= 0 => x >= y
2. 2y - 2x >= 0 => y >= x
3. x(2x - 2y) = 0 => x = 0 or x = y
4. y(2y - 2x) = 0 => y = 0 or y = x
5. x >= 0
6. y >= 0

Conditions 1 and 2 imply that x = y. This satisfies all the other conditions as long as x ò 0 and y ò 0 Thus all points on the line x = y which are in the first quadrant are stationary points. Checking the Hessian matrix, we get H =

			  | 2 -2 |
			  |-2  2 |

This matrix is singular, so we must use the definition to check it for definiteness. Since

[h₁ h₂]H[h₁ h₂]T = 2(h₁ - h₂)2 >= 0,

the Hessian is positive semidefinite and hence the function is convex. Thus all stationary points must be relative minima.

CRITICAL THINKING QUESTIONS:

These will be provided in class.

SKILL EXERCISES:

1. Apply Theorem 5.1.1 to find the absolute minimum of the following function under the restriction that all the variables are nonnegative. (i.e. X >= 0)

   f(x₁,x₂,x₃) = 4x₁² + x₂² + x₃² - 2x₁x₂ - 2x₁x₃ - 2x₁ + 8
   
   

Return to the List of Activities