Problem Solving with Multivariable Constrained and Unconstrained Optimization

Objectives:

• (1) Set up a solution process for multivariable optimization problems.
• (2) Recognize when applicable constraints are required.
• (3) Perform sensitivity analysis, when applicable, and interpret the results.
• (4) Know the numerical techniques to obtain approximate solutions and when to use them.

Unconstrained Optimization: Theory

A small company is planning to install a central computer with cable links to five new departments. According to their floor plan, the peripheral computers for the five departments will be situated as shown in Figure 4.1 below. The company wishes to locate the central computer to minimize the amount of cable used to link the five peripheral stations because signals degrade with cable length and high quality cable is expensive. Assume that cable is strung above the ceiling panels in a straight line from a point above a peripheral to a point above the central computer; the standard distance formula may be used to determine the length needed to connect a remote to the central computer. Ignore the segments of cable from any device to a point above the ceiling panel immediately over that device. That is, work only with lengths of cable strung over the ceiling panels—the cable segment from the peripheral to the ceiling doesn’t change with the different routings. The location coordinates of the five peripheral computers appear in Table 4.1.

TABLE 4.1: Grid of the Five Departments

FIGURE 4.1: Grid of the Five Departments

The central computer will be positioned at coordinates (m, n) where m and n are both integers in the grid representing office space. Determine the coordinates (m, n) that minimize the total amount of cable needed. Report the total number of feet of cable needed for this placement along with the coordinates (m, n).

To model and solve problems like this, we need multivariable optimization. In this chapter, our goal is to introduce both constrained and unconstrained nonlinear optimization. For a more thorough coverage, we suggest studying complete texts on the subject such as Ruszczynski’s Nonlinear Optimization (Princeton Univ. Press, 2006).

Basic Theory

We begin with how to find an optimal solution, if one exists, for the unconstrained nonlinear optimization problem

We assume that all the first and second partial derivatives of / exist and are continuous at all points in /’s domain. Let the partial derivative of / with respect to a:, be

Candidate critical points (stationary points) are found where

This set of conditions gives a system of equations that when solved yields one or more critical points (if any exist) of /. Each critical point will satisfy each equation df (critical point)/dxi = 0 for i = 1,,n.

Theorem. Local Extremum Characterization.

If x* = (a;(, x-2-,... , ж*) is a local extremum of the twice continuously differentiable function /, then x* satisfies

We have previously defined all points x that satisfy df(x)j'dx, = 0 for i = 1, 2, ..., n as critical points or stationary points. Not all critical points (stationary points) are local extrema. If a stationary point is not a local extremum (a maximum or a minimum), then it is called a saddle point.

The Hessian Matrix

We used a function’s concavity to recognize extrema in the single-variable case. How do we determine the “concavity” of functions of more than one variable?

Definition. Convex Multivariable Function.

A function /(x) is convex iff for every pair of points x⁽¹⁾ and x^<2* in /’s domain and any Л € [0,1], we have

Similarly, / is concave iff for every pair of points x⁽ b and x^<2l in /’s domain and any A € [0,1], we have

In words, this definition says that / is convex iff whenever we look at an x* on the line segment connecting x^! and x⁽² the value of the function at /(x*) is below the point the same distance along the line segment connecting /(x^¹)) and /(x'²)). For concave, change “below” to “above.”

Next, we introduce the Hessian matrix, named for Ludwig Hesse who studied surfaces in the 1800s, that allows us to determine the convexity of multivariable functions. The Hessian matrix will also provide additional information about the critical points.

Definition. The Hessian Matrix of /.

The Hessian matrix of a multivariable function / is the nxn matrix of second partial derivatives where the (г,j/')th entry is df /(dxidxj)

When / has continuous second partial derivatives, the mixed partials are equal and the Hessian matrix is symmetric.^[1]

In the 2-variable case of a function with continuous second partials,

Example 4.1. A Simple 2x2 Hessian.

Let .f{xi,X2) = x + 3x2- Find /’s Hessian. Since

then

So f’s Hessian is

Example 4.2. Another 2x2 Hessian.

Let g(xi,X2) = —x + 3xX2 — 3x- Find g’s Hessian. Since

then

So g’s Hessian is

The Hessian will play the role of the second derivative in the Second Derivative Test as we extend from single-variable to multivariable functions. We will use determinants to analyze the Hessian. Recall, the determinant of a 2 x 2 matrix A is

Calculating determinants of larger matrices is defined recursively using expansion by minors.^[2] We can use leading principal minors to analyze the Hessian.

Definition 4.1. Leading Principal Minor.

The ith leading principal minor of a square matrix A is the determinant of the ixi submatrix obtained by deleting n — i rows of A and deleting the same n — i columns of A where i = 0, 1, 2, ..., n — 1.

Example 4.3. The Leading Principal Minors of a Hessian Matrix.

Given the 3x3 Hessian matrix

determine all leading principal minors.

• 1. There are three 1st order leading principal minors, (i = 1: eliminate 3 — 1 =
• 2 rows and the same columns).

a. Eliminate rows 1 and 2 and columns 1 and 2: M = [З]. Then

b. Eliminate rows 1 and 3 and columns 1 and 3: M = [l]. Then

c. Eliminate rows 2 and 3 and columns 2 and 3: M = [l]. Then

The 1st order leading principal minors are the entries of the main diagonal.

• 2. There are three 2nd order leading principal minors, (г = 2: eliminate
• 3 — 2=1 row and the same column).

Г1 б!

• (a) Eliminate row 1 and column 1: M = _ _ . Then
• 5 о

Г2 4l

(b) Eliminate row 2 and column 2: M ⁼ 4 3 • Then

[2 0l

(c) Eliminate row 3 and column 3: M = ^ ^ . Then

3. There is only one 3rd order leading principal minor, the determinant of H itself.'* (Eliminate no rows or columns.) Then

Notice that the leading principal minors of a matrix are just the determinants of all the submatrices formed along the main diagonal.

How do we use all these determinants, the leading principal minors, of the Hessian matrix to determine the convexity of the multivariate function? The following theorem answers our question.

Theorem. Convexity and the Hessian Matrix.

Suppose f(xi,X2,... ,x_n) has continuous second partial derivatives at all points of its domain D. Let H be /’s Hessian matrix. Then

a. if all the leading principal minors of H are nonnegative, then / is convex;

b. if all the leading principal minors of H match the sign of (—l)^fc where k is the minor’s order (positive for even order, negative for odd), then f is concave;

c. otherwise, / is neither convex, nor concave.

Example 4.4. Determining Convexity.

Determine the convexity of the function f(x 1,3:2) = а^х+Зж^ using its Hessian matrix.

Maple uses the same notation for determinant. Enter the matrix H, then execute H.

1. The Hessian of / is

• 2. a. The 1st order leading principal minors are: |2| = 2 > Oand |6| = 6 > 0. b. The 2nd order leading principal minor is | //1 = 12 > 0.
• 3. Since all leading principal minors are nonnegative, the Convexity and the Hessian Matrix theorem tell us that / is a convex function.

Figure 4.2 shows /’s graph.

FIGURE 4.2: Graph of f(x,X2) = x + За,^

Example 4.5. Determining Concavity Using the Hessian.

Determine the convexity of the function д{х,хъ) = —x — Ъх + xX2 using ts Hessian matrix.

1. The Hessian of g is

• 2. a. The 1st order leading principal minors are: | — 2| = —2 < 0 & | — 6| =
• -6 < 0.

b. The 2nd order leading principal minor is II = 11 > 0.

3. Since the 1st order leading principal minors are negative and the 2nd order is positive, the Convexity and the Hessian Matrix theorem tells us that g is a concave function.

Figure 4.3 shows g’s graph.

FIGURE 4.3: Graph of д(х,хъ) = —x — 3x% + xX2

Example 4.6. Determining Nonconvexity Using the Hessian.

Determine the convexity of the function h(x,x2) = x — За?! + X1X2 using its Hessian matrix.

1. The Hessian of h is

2. The 1st order leading principal minors are: |2| = 2 > 0 & | — 6| = —6 < 0. Stop. Since we have opposite signs, h cannot be either convex or concave; h has a saddle point.

The function is neither convex nor concave; this Hessian matrix is called indefinite.

Unconstrained Optimization: Theory Figure 4.4 shows /г’s graph.

FIGURE 4.4: Graph of h(xi,X2) = x² — Ъх + xX2

A quick trip to Maple verifies the analysis.

Part a of the Convexity and the Hessian Matrix Theorem (pg. 126) says a convex function has all nonnegative leading principal minors; the function’s Hessian is then called positive definite. Part b of the theorem says a concave function has all nonpositive leading principal minors; the function’s Hessian is then called negative definite. Part c gives us an indefinite Hessian. The calculation of definiteness becomes more involved when variables appear in the function’s Hessian. Let’s use Maple to test and verify definiteness for the functions of our examples. (Remember to load both Student[VectorCalculus] and LinearAlgebra packages.)

Maple has a number of functions that compute the Hessian of a function. Versions of the Hessian command are in the Student[VectorCalculus], Vector- Calculus, and LinearAlgebra packages. Consult Maple’s Help pages to help you decide which version is best to use in a given situation.

In a more general setting, if a function has terms with power higher than 2 or includes transcendental functions, such as xx or sin (ж 1*2); the Hessian will have terms with variables. Then the analysis of definiteness for classifying a stationary point as a maximum, minimum, or saddle point is a bit more complicated.

For two variables, we use the quadratic form to test the Hessian matrix. In general, we use Q(x) = x^T Hx. Then define

Definition 4.2. Definiteness of a Matrix.

Let H be /’s Hessian matrix. Then H is

• 1. positive definite iff II > 0 for every nonzero vector 2 € domain(/),
• 2. positive semi-definite iff II > 0 for every nonzero vector z € domain(/),
• 3. negative definite iff H < 0 for every nonzero vector л € domain(/),
• 4. negative semi-definite iff II < 0 for every nonzero vector z € domain(/),
• 5. indefinite otherwise.

We can relate definiteness to the signs of the leading principal minors.

Positive Definite: All leading principal minors are positive.

Positive Semi-definite: All leading principal minors are non-negative (some may be zero).

Negative Definite: The leading principal minors follow the signs of ( — 1) , where к is the order of the leading principal minor. Even order leading principal minors are positive, and odd order leading principal minors are negative.

Negative Semi-definite: All nonzero leading principal minors follow the signs of ( —l)^fc, where к is the order of the leading principal minor. Even order nonzero leading principal minors are positive, and odd order nonzero leading principal minors are negative. Some may be zero.

Indefinite: Some leading principal minors do not follow any of the rules above.

If the Hessian is also a function of the independent variables, its definiteness might vary from one point to another. To test the definiteness of the Hessian at a point x*, evaluate the Hessian at the point. For example, in the matrix

the specific values of xi and a; 2 determine whether H is positive definite, positive semi-definite, negative definite, negative semi-definite, or indefinite at [xi,X2]- Give an example of each case!

Table 4.2 summarizes the relationship between the Hessian matrix definiteness and the classification of stationary points (extrema) as maximum, minimum, saddle points, or ‘inconclusive.’

TABLE 4.2: Summary of Hessian Definiteness

Example 4.7. Using the Summary Table.

1. Suppose the Hessian of the function f{x,X2) is given by

The 1st order leading principal minors are —2 and —4. The 2nd order leading principal minor is H{x,X2) = 7. Since the first orders are negative and the second order is positive, the leading principal minors follow the sign of (—1)*-'. The summary table indicates that / is concave and the stationary point found is a maximum. This Hessian matrix is negative definite.

2. Suppose the Hessian of the function / is given by

The 1st order leading principal minors are 3, 5, and 7. The 2nd order leading principal minors are 3, 12, and 3. The 3nd order leading principal minor, the determinant of II. is 0. All leading principal minors are positive or zero. The summary table indicates that / is convex and any corresponding stationary points found would be local minima. This Hessian matrix is positive semi-definite.

3. Suppose the Hessian of the function / is given by

The 1st order leading principal minors are —2 and —3. The 2nd order leading principal minor is H = —10. Since both the first orders and the second order are negative, the summary table indicates the Hessian is indefinite and the stationary point found is a saddle point.

• [1] The equalitj' of mixed partials for smooth functions is called Schwarz’s Theorem orClairaut’s Equality of Mixed Partials Theorem. Euler had discovered this very importantresult in 1734 when he was 27 years old.
• [2] For a full discussion of determinants, see, e.g., Gilbert Strang’s Introduction to LinearAlgebra.