2.8 Minimizing a Quadratic Polynomial

2.8  Minimizing a Quadratic Polynomial

In this section, we consider how to minimize quadratic polynomials. This problem is equivalent to that of maximizing a polynomial, since any maximum of a quadratic polynomial p occurs at a minimum of the quadratic polynomial –p.

Recall from elementary calculus that any minimum on of a differentiable function f :  →  occurs at a point x at which f ′(x) = 0. Generalizing to multiple dimensions, any minimum on n of a differentiable function f : n →  occurs at a point x at which f (x) = 0.

A quadratic polynomial p:  → 

[2.89]

has a unique minimum if and only if c is positive, in which case the minimum occurs at the point

[2.90]

This generalizes in an intuitive manner to multiple dimensions. A quadratic polynomial p:  → 

[2.91]

has a unique minimum if and only if c is positive definite, in which case the minimum occurs at the point

[2.92]

Compare [2.92] with [2.90]. This is another situation in which positive definite matrices play a role analogous to positive numbers. To understand our result more intuitively, consider Exhibit 2.9 It shows graphs for three quadratic polynomials of the form [2.91] from 2 to . The first one has a positive definite matrix c. Both of its eigenvalues are positive, and the polynomial has a minimum. The second polynomial has a matrix c with mixed eigenvalues. One is positive and the other is negative. The polynomial has a saddle shape, so it has neither a maximum nor a minimum. The third polynomial has a negative definite matrix c. Both of its eigenvalues are negative, and the polynomial has a maximum.

Exhibit 2.0: Three quadratic polynomials are graphed. The first has a positive definite matrix c. It achieves a minimum. The second has matrix c with mixed eigenvalues—one is positive and the other is negative. It achieves neither a maximum nor a minimum. The third has a negative definite matrix c. It achieves a maximum.
Exercises
2.11

Similar to the graphs of Exhibit 2.9, sketch a graph for a quadratic polynomial from 2 to that has a positive semidefinite matrix c. (Hint: Depending upon your solution, your polynomial will either have no minima or infinitely many.)
Solution

2.12

Repeat Exercise 2.11 assuming c is negative semidefinite.
Solution

2.13

Consider the quadratic polynomial p: 3 → :

[2.93]

  1. Express the polynomial in matrix form [2.91]. Make sure your matrix c is symmetric.
  2. Apply the Cholesky algorithm to determine if your matrix c is positive definite.
  3. Solve for the point x indicated by [2.92].
  4. What is the polynomial’s value at the point x obtained in item (c)?
  5. Is your solution a maximum, minimum, or saddle point?

Solution