Ch07 Symmetric Matrices and Quadratic Forms

7.3 Constrained Optimization

Engineers, economists, scientists, and mathematicians often need to find the maximum or minimum value of a quadratic form $Q(\textbf{x})$ for $\textbf{x}$ in some specified set. Typically, the problem can be arranged so that $\textbf{x}$ varies over the set of unit vectors. This constrained optimization problem has an interesting and elegant solution. The requirement that a vector $\textbf{x}$ in $\mathbb{R}^n$ be a unit vector can be stated in several equivalent ways:

$$||\textbf{x}|| = 1, ||\textbf{x}||^2 = 1, \textbf{x}^T\textbf{x} = 1,\\ \text {and} \\ x_1^2 + x_2^2 + \cdots + x_n^2 =1 \tag{1}$$

The expanded version (1) of $\textbf{x}^T\textbf{x}=1$ is commonly used in applications.

When a quadratic form $Q$ has no cross-product terms, it is easy to find the maximum and minimum of $Q(\textbf{x})$ for $\textbf{x}^T\textbf{x} = 1$.

$$m = \text{min}\left\{ \textbf{x}^TA\textbf{x} : ||\textbf{x}||=1\right\}, \\ M = \text{max}\left\{ \textbf{x}^TA\textbf{x} : ||\textbf{x}||=1\right\} \tag{2}$$

Theorem 6

Let $A$ be a symmetric matrix, and define $m$ and $M$ as in (2).

• Then $M$ is the greatest eigenvalue $\lambda_1$ of $A$and
• $m$ is the least eigenvalue of $A$. The value of $\textbf{x}^TA\textbf{x}$ is $M$ when $\textbf{x}$ is a unit eigenvector $\textbf{u}_1$ corresponding to $M$. The value of $\textbf{x}^TA\textbf{x}$ is $m$ when $\textbf{x}$ is a unit eigenvector corresponding to $m$.

Proof

Orthogonally diagonalize $A$ as $PDP^{-1}$. We know that

$$\textbf{x}^TA\textbf{x} = \textbf{y}^TD\textbf{y} \text{ when } \textbf{x} = p \textbf{y} \tag{3}$$

Also,

$$||\textbf{x}||=||P\textbf{y}||=\textbf{y} \text{ for all }\textbf{y}$$

Because $P^T P=I$ and $||P\textbf{y}||^2 = (P\textbf{y})^T (P\textbf{y}) = \textbf{y}^TP^TP\textbf{y} = \textbf{y}^T\textbf{y} = ||\textbf{y}||^2$. In particular, $||\textbf{y}||=1$ if and only if $||\textbf{x}||=1$.

Thus, $\textbf{x}^TA\textbf{x}$ and $\textbf{y}^TD\textbf{y}$ assume the same set of values as $\textbf{x}$ and $\textbf{y}$ range over the set of all unit vectors.

To simplify notation, suppose that $A$ is a $3\times 3$ matrix with eigenvalues $a \le b \le c$. Arrange the columns of $P$ so that $P=\begin{bmatrix} \textbf{u}_1 & \textbf{u}_2 & \textbf{u}_3 \end{bmatrix}$ and

$$D = \begin{bmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \end{bmatrix}$$

Given any unit vector $\textbf{y} \in \mathbb{R}^3$ with coordinates $y_1, y_2,y_3$, observe that

$$ay_1^2 = ay_1^2 \\ by_2^2 \le ay_2^2 \\ cy_3^2 \le ay_3^2$$

and obtain these inequalities:

$$\begin{align*} \textbf{y}^TD\textbf{y} &= ay_1^2+by_s^2+cy_3^2 \\ &\le ay_1^2+ay_s^2+ay_3^2 \\ &= a \left( y_1^2+y_2^2+y_3^2\right) \\ &= a ||\textbf{y}||^2 = a \end{align*}$$

Thus $M \le a$, by definition of $M$. However, $\textbf{y}^TD\textbf{y}=a$ when $\textbf{y}=\textbf{e}_1=(1,0,0)$ ,so in fact $M=a$. By (3), the $textbf{x}$ that corresponds by $\textbf{y}=\textbf{e}_1$ is the eigenvector $\textbf{u}_1$ of $A$, because

$$\textbf{x} = P \textbf{e}_1 = \begin{bmatrix} \textbf{u}_1 & \textbf{u}_2 & \textbf{u}_3 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} =\textbf{u}_1$$

Thus $M=a=\textbf{e}_1^TD\textbf{e}_1= \textbf{u}_1^TA\textbf{u}_1$, which proves the statement about $M$. A similar argument shows that $m$ is the least eigenvalue, $c$, and this value of $\textbf{x}^TA\textbf{x}$ is attained when $\textbf{x}=P\textbf{e}_3=\textbf{u}_3$. $\blacksquare$

Example 3

Let $A=\begin{bmatrix} 3& 2& 1 \\ 2& 3& 1 \\ 1& 1& 4 \end{bmatrix}$. Find the maximum value of the quadratic form $\textbf{x}^TA\textbf{x}$ subject to the constraint $\textbf{x}^T\textbf{x}$ and find a unit vector at which this maximum value is attained.

Solution

By Theorem 6, the desired maximum value is the greatest eigenvalue of $A$. The characteristic equation turns out to be

$$0=-\lambda^3+10 \lambda^2 -27 \lambda +18 = -(\lambda-6)(\lambda-3)(\lambda-1)$$

The greatest eigenvalue is 6.

The constrained maximum of $\textbf{x}^TA\textbf{x}$ is attained when $\textbf{x}$ is a unit eigenvector for $\lambda=6$. Solve $(A-6I)\textbf{x}=0$ and and find an eigenvector $\begin{bmatrix}1\\1\\1\end{bmatrix}$. Set $\textbf{u}_1 = \begin{bmatrix}1/\sqrt{3} \\ 1/\sqrt{3} \\ 1/\sqrt{3} \end{bmatrix}$. $\blacksquare$

In Theorem 7 and in later applications, the values of $\textbf{x}^TA\textbf{x}$ are computed with additional constraints on the unit vector $\textbf{x}$.

Theorem 7

Let $A$, and $\textbf{u}_1$ be as in Theorem 6. Then the maximum value of $\textbf{x}^TA\textbf{x}$ subject to the constraints

$$\textbf{x}^T\textbf{x}=1, \textbf{x}^T\textbf{u}_1 = 0$$

is the second greatest eigenvalue $\lambda_2$, and this maximum is attained when $\textbf{x}$ is an eigenvector $\textbf{u}_2$ corresponding to $\lambda_2$.

Theorem 7 can be proved by an argument similar to the one above in which the theorem is reduced to the case where the matrix of the quadratic form is diagonal. The next example gives an idea of the proof for the case of a diagonal matrix.

Example 4

Solution of Example 4

Theorem 8

Let $A$ be a symmetric $n \times n$ matrix with an orthogonal diagonalization $A=PDP^{-1}$, where the entries on the diagonal of $D$ are arranged so that $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_n$ and where columns of $P$ are corresponding unit eigenvectors $\textbf{u}_1, \textbf{u}_2, \cdots, \textbf{u}_n$. Then for $k=2, \cdots, n$, the maximum value of $\textbf{x}^TA\textbf{x}$ subject to the constraints

$$\textbf{x}^T\textbf{x}=1, \textbf{x}^T\textbf{u}_1=0, \cdots, \textbf{x}^T\textbf{u}_{k-1}=0$$

is the eigenvalue $\lambda_k$,

and this maximum is attained at $\textbf{x}=\textbf{u}_k$.