7.3 Constrained optimization

Big idea

Ask a quadratic form how large it can get and the unconstrained answer is useless. If $Q(\mathbf{x})$ is ever positive, then $Q(10\mathbf{x}) = 100Q(\mathbf{x})$ is larger, and nothing stops the climb. The question only becomes interesting once the length of $\mathbf{x}$ is pinned down. So fix $\|\mathbf{x}\| = 1$ and ask which direction the form likes best.

The answer needs no calculus. Write the form in eigenvector coordinates, where it is $\lambda_1 y_1^2 + \cdots + \lambda_n y_n^2$. The change of variable is orthogonal, so it preserves length, and the constraint becomes $y_1^2 + \cdots + y_n^2 = 1$. The value of the form is then a weighted average of the eigenvalues with weights that are nonnegative and sum to one. An average cannot exceed the largest number being averaged or fall below the smallest.

That is the whole section. The maximum on the unit sphere is the largest eigenvalue, the minimum is the smallest, and both are reached by putting all the weight on one eigenvector. The generalization comes for free: rule out the top direction by requiring perpendicularity to it, and the best remaining value is the next eigenvalue down.

Decoder

Subject to the constraint $\mathbf{x}^{T}\mathbf{x} = 1$, the maximum of $\mathbf{x}^{T}A\mathbf{x}$ is the greatest eigenvalue of $A$, attained at a corresponding unit eigenvector.

The constraint $\mathbf{x}^{T}\mathbf{x} = 1$ is just $\|\mathbf{x}\| = 1$ written as a matrix product, so the search runs over the unit circle in two variables, the unit sphere in three, and the unit sphere in $\mathbb{R}^n$ after that. “Attained at” matters: the maximum is not approached, it is hit exactly, and you can name the point where it happens.

Definitions and results

The problem. Given a symmetric $A$, find the largest and smallest values of $Q(\mathbf{x}) = \mathbf{x}^{T}A\mathbf{x}$ among all $\mathbf{x}$ with $\|\mathbf{x}\| = 1$, and find where those values occur.

Order the eigenvalues. Write the eigenvalues of $A$ as $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$, repeating any that occur more than once, with orthonormal eigenvectors $\mathbf{u}_1, \dots, \mathbf{u}_n$ in matching order.

Maximum and minimum on the unit sphere. The greatest value of $Q$ on the unit sphere is $\lambda_1$, reached at $\mathbf{u}_1$; the least is $\lambda_n$, reached at $\mathbf{u}_n$. Both are also reached at the negatives of those vectors, since $Q(-\mathbf{x}) = Q(\mathbf{x})$, and at any other unit vector in the same eigenspace when the eigenvalue repeats.

Why. Set $\mathbf{x} = P\mathbf{y}$ with $P$ the orthogonal matrix of unit eigenvectors. Then $\|\mathbf{y}\| = \|\mathbf{x}\| = 1$ and

$$ Q = \lambda_1 y_1^2 + \lambda_2 y_2^2 + \cdots + \lambda_n y_n^2, \qquad y_1^2 + y_2^2 + \cdots + y_n^2 = 1 $$

Replacing every $\lambda_i$ by $\lambda_1$ can only raise the sum, and it gives $\lambda_1$. So $Q \leq \lambda_1$ everywhere on the sphere, with equality when all the weight sits on the first coordinate, that is at $\mathbf{x} = \mathbf{u}_1$. The same argument run downward gives the minimum. The numbers $y_i^2$ are the weights, and they are exactly the squared coordinates of $\mathbf{x}$ along the eigenvectors.

Eigenvectors are the critical directions. At $\mathbf{x} = \mathbf{u}_i$ the form equals $\mathbf{u}_i^{T}A\mathbf{u}_i = \lambda_i\mathbf{u}_i^{T} \mathbf{u}_i = \lambda_i$. So every eigenvalue appears as a value of $Q$ on the sphere, and the extremes are the two ends of that list.

Adding a perpendicularity constraint. Restrict further to unit vectors with $\mathbf{x} \cdot \mathbf{u}_1 = 0$. That forces $y_1 = 0$, so the weighted average now runs over $\lambda_2$ through $\lambda_n$ and the maximum is $\lambda_2$, reached at $\mathbf{u}_2$. Ruling out the top $k$ eigenvectors the same way leaves $\lambda_{k+1}$ as the best available value.

Off the unit sphere. For any nonzero $\mathbf{x}$, the ratio $\mathbf{x}^{T}A\mathbf{x} / \mathbf{x}^{T}\mathbf{x}$ lies between $\lambda_n$ and $\lambda_1$; it is the value of $Q$ at the unit vector pointing the same way. On the sphere of radius $r$ the maximum is $r^2\lambda_1$, because scaling $\mathbf{x}$ by $r$ scales $Q$ by $r^2$.

Reading the signs. The form is positive definite exactly when its minimum on the unit sphere is positive, which is the classification test of the previous section arrived at from a different direction.

Two traps. The first is reporting an unnormalized eigenvector as the place where the maximum occurs. An eigenvector of length $3$ does not satisfy the constraint, and the form there is nine times too large, so divide by the length before answering. The second is assuming the maximizer is unique. When the largest eigenvalue repeats, every unit vector in its eigenspace is a maximizer, and the honest answer names that eigenspace rather than one vector from it.

Worked examples

A diagonal case checked by substitution

Let $A = \begin{bmatrix} 3 & 0 \\ 0 & -1 \end{bmatrix}$, so $Q(\mathbf{x}) = 3x_1^2 - x_2^2$. The eigenvalues are $3$ and $-1$, so the prediction is a maximum of $3$ at $(1, 0)$ and a minimum of $-1$ at $(0, 1)$.

Check it by hand, with no eigenvalue theory. On the unit circle, $x_2^2 = 1 - x_1^2$, so

$$ Q = 3x_1^2 - (1 - x_1^2) = 4x_1^2 - 1 $$

and $x_1^2$ runs over $[0, 1]$. So $Q$ runs over $[-1, 3]$. The top end needs $x_1^2 = 1$, which is $(\pm 1, 0)$; the bottom end needs $x_1 = 0$, which is $(0, \pm 1)$. Predicted values and predicted locations, both confirmed.

Cross terms, with a trigonometric check

Let $A = \begin{bmatrix} 5 & 2 \\ 2 & 5 \end{bmatrix}$, the positive definite matrix from the previous section, with eigenvalues $7$ and $3$ and unit eigenvectors $\tfrac{1}{\sqrt{2}}(1,1)$ and $\tfrac{1}{\sqrt{2}}(1,-1)$. The claim is a maximum of $7$ and a minimum of $3$ on the unit circle.

Verify by parametrizing: $\mathbf{x} = (\cos t, \sin t)$ gives

$$ Q = 5\cos^2 t + 4\cos t \sin t + 5\sin^2 t = 5 + 2\sin 2t $$

using $\cos^2 + \sin^2 = 1$ and the double-angle identity. Since $\sin 2t$ runs over $[-1, 1]$, the form runs over $[3, 7]$, matching the eigenvalues exactly. The maximum needs $\sin 2t = 1$, so $t = \pi/4$ and $\mathbf{x} = \tfrac{1}{\sqrt{2}}(1,1)$, which is the eigenvector for $7$. The minimum needs $t = 3\pi/4$, giving $\tfrac{1}{\sqrt{2}}(-1,1)$, a unit eigenvector for $3$.

Check one of the values directly: at $\tfrac{1}{\sqrt{2}}(1,1)$ the form is $\tfrac{1}{2}(5 + 4 + 5) = 7$.

Three variables, with a second constraint

Let

$$ A = \begin{bmatrix} 4 & 1 & 0 \\ 1 & 4 & 0 \\ 0 & 0 & 2 \end{bmatrix} $$

The third standard basis vector is an eigenvector with eigenvalue $2$. The upper block behaves like the two by two above: $(1,1,0)$ gives $(5,5,0)$ so $\lambda = 5$, and $(1,-1,0)$ gives $(3,-3,0)$ so $\lambda = 3$. Trace check: $5 + 3 + 2 = 10 = 4 + 4 + 2$.

So on the unit sphere the maximum is $5$, at $\mathbf{u}_1 = \tfrac{1}{\sqrt{2}}(1,1,0)$, and the minimum is $2$, at $\mathbf{u}_3 = (0,0,1)$. Now add the constraint $\mathbf{x} \cdot \mathbf{u}_1 = 0$. The best remaining value is the next eigenvalue, $3$, at $\mathbf{u}_2 = \tfrac{1}{\sqrt{2}}(1,-1,0)$. Check that value: $Q(\mathbf{u}_2) = \tfrac{1}{2}\left(4 - 1 - 1 + 4\right) = 3$, and $\mathbf{u}_2 \cdot \mathbf{u}_1 = \tfrac{1}{2}(1 - 1 + 0) = 0$, so it satisfies the constraint.

Test a vector that is no eigenvector at all: $\mathbf{x} = \tfrac{1}{3}(1, 2, -2)$, which has length $1$ since $1 + 4 + 4 = 9$. Then

$$ Q(\mathbf{x}) = \frac{1}{9}\left(4(1) + 4(4) + 2(4) + 2(1)(2)\right) = \frac{4 + 16 + 8 + 4}{9} = \frac{32}{9} $$

That is about $3.56$, comfortably inside $[2, 5]$. The weighted-average view gives the same number: the squared coordinates along $\mathbf{u}_1$, $\mathbf{u}_2$, $\mathbf{u}_3$ are $\tfrac{1}{2}$, $\tfrac{1}{18}$, $\tfrac{4}{9}$, which sum to $1$, and

$$ 5 \cdot \frac{1}{2} + 3 \cdot \frac{1}{18} + 2 \cdot \frac{4}{9} = \frac{45 + 3 + 16}{18} = \frac{64}{18} = \frac{32}{9} $$

Practice

Everything starts with the eigenvalues, since the largest and smallest are the answers themselves.

Then the eigenvectors, since the question also asks where the extreme value occurs, and the answer is a unit vector from the matching eigenspace.

Videos

Watch the part where a quadratic form is read as a surface and positive definiteness becomes a bowl with a minimum at the origin. The extreme values on the unit sphere are the steepest and shallowest directions of that bowl.

Quiz

Five items on computing eigenvalues, identifying the eigenvector where an extreme value occurs, and the effect of a perpendicularity constraint.