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: →
has a unique minimum if and only if c is positive, in which case the minimum occurs at the point
This generalizes in an intuitive manner to multiple dimensions. A quadratic polynomial p: →
has a unique minimum if and only if c is positive definite, in which case the minimum occurs at the point
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.
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.)
Repeat Exercise 2.11 assuming c is negative semidefinite.
Consider the quadratic polynomial p: 3 → :
- Express the polynomial in matrix form [2.91]. Make sure your matrix c is symmetric.
- Apply the Cholesky algorithm to determine if your matrix c is positive definite.
- Solve for the point x indicated by [2.92].
- What is the polynomial’s value at the point x obtained in item (c)?
- Is your solution a maximum, minimum, or saddle point?