---
title: Constrained Optimization
module: Symmetric Matrices, Quadratic Forms, and the SVD
moduleNumber: 7
lessonNumber: 3
order: 703
summary: >
  Maximizing a quadratic form xᵀAx over the unit sphere has an exact answer: the
  maximum is the largest eigenvalue of A, attained at its eigenvector, and the
  minimum is the smallest eigenvalue. Adding orthogonality constraints peels off
  the eigenvalues in order, characterizing the whole spectrum by optimization.
topics: [Symmetric Matrices, Quadratic Forms, and the SVD]
sources:
  - book: Lay
    ref: "Ch. 7 — Symmetric Matrices and Quadratic Forms; §7.3 Constrained Optimization"
draft: false
---

A [quadratic form](/linear-algebra/symmetric-quadratic-svd/quadratic-forms)
$Q(x) = x^\top A x$ has no finite maximum on all of $\mathbb{R}^n$: scaling $x$
by $t$ scales $Q$ by $t^2$, so an unbounded input makes an unbounded output. The
question becomes well posed once $x$ is confined to a bounded set, and the
natural choice is the unit sphere. This constrained problem has an exact
solution in terms of the eigenvalues, with no calculus of Lagrange multipliers
required.

The constraint that $x$ be a unit vector has several equivalent forms:

$$
\|x\| = 1, \qquad \|x\|^2 = 1, \qquad x^\top x = 1, \qquad x_1^2 + \cdots + x_n^2 = 1.
$$

The expanded version $x_1^2 + \cdots + x_n^2 = 1$ is the one that appears in most
applications.

## The diagonal case

When $Q$ has no cross-terms the answer can be read off directly.

> **Worked example.** Maximize and minimize $Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2$
> subject to $x^\top x = 1$. Since $x_2^2, x_3^2 \geq 0$, bounding the smaller
> coefficients above by the largest gives
> $$
> Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2 \leq 9x_1^2 + 9x_2^2 + 9x_3^2 = 9(x_1^2+x_2^2+x_3^2) = 9,
> $$
> so $Q$ never exceeds $9$ on the sphere, and $Q = 9$ at $x = (1,0,0)$: the
> maximum is $9$. Bounding instead by the smallest coefficient gives
> $Q(x) \geq 3(x_1^2+x_2^2+x_3^2) = 3$, attained at $x = (0,0,1)$. The constrained
> maximum and minimum are the largest and smallest diagonal entries, which for a
> diagonal matrix are its eigenvalues.

## The general theorem

For a general symmetric $A$, orthogonal diagonalization reduces the problem to
the diagonal case. Write the extreme values as

$$
M = \max\{\, x^\top A x : \|x\| = 1 \,\},
\qquad
m = \min\{\, x^\top A x : \|x\| = 1 \,\}.
$$

The set of attainable values $\{x^\top A x : \|x\| = 1\}$ is a closed interval
$[m, M]$ on the real axis, and its endpoints are eigenvalues.

> **Theorem (Extreme values on the unit sphere).** Let $A$ be symmetric with
> extreme values $M$ and $m$ as above. Then $M$ is the greatest eigenvalue
> $\lambda_1$ of $A$ and $m$ is the least eigenvalue $\lambda_n$. The value
> $x^\top A x$ equals $M$ when $x$ is a unit eigenvector for $\lambda_1$, and
> equals $m$ when $x$ is a unit eigenvector for $\lambda_n$.

> **Proof.** Orthogonally diagonalize $A = PDP^{-1}$ and substitute $x = Py$. An
> orthogonal $P$ preserves length, $\|x\| = \|Py\| = \|y\|$, so $x$ is a unit
> vector exactly when $y$ is, and
>
> $$
> x^\top A x = y^\top D y = \lambda_1 y_1^2 + \cdots + \lambda_n y_n^2.
> $$
>
> Order the eigenvalues $\lambda_1 \geq \cdots \geq \lambda_n$. Bounding each
> $\lambda_i y_i^2 \leq \lambda_1 y_i^2$ gives $y^\top D y \leq \lambda_1 \|y\|^2 =
> \lambda_1$, with equality at $y = e_1$. That $y = e_1$ corresponds to $x = Pe_1
> = u_1$, the eigenvector for $\lambda_1$. Thus $M = \lambda_1$, attained at $u_1$.
> The minimum argument is symmetric. $\;\blacksquare$

Geometrically, the level sets of $Q$ are nested conics, and on the unit circle
$Q$ reaches its largest value where the circle is tangent to the widest level
curve it touches, in the direction of the top eigenvector.

$$
% caption: On the unit circle, xᵀAx is largest where the circle meets the level
% curve tangent along u₁ and smallest along u₂; the tangency directions are the
% eigenvectors and the tangent values are the extreme eigenvalues.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  % unit circle
  \draw[black, thick] (0,0) circle (1.4);
  \node[black] at (0.0,-1.75) {unit circle};
  % level ellipses of Q (aligned to axes for clarity)
  \draw[thick] (0,0) ellipse (2.3 and 0.9);
  \draw[thin] (0,0) ellipse (1.85 and 0.72);
  % eigenvector directions
  \draw[->, acc, very thick] (0,0) -- (1.4,0) node[right, black] {$u_1$};
  \draw[->, acc, very thick] (0,0) -- (0,1.4) node[above, black] {$u_2$};
  \node[black] at (2.4,0.15) {$M$};
  \node[black] at (0.7,1.05) {$m$};
\end{tikzpicture}
$$

### The Rayleigh quotient

For nonzero $x$ that is not required to be a unit vector, dividing by $\|x\|^2$
normalizes the form. The result is the **Rayleigh quotient**

$$
R(x) = \frac{x^\top A x}{x^\top x},
$$

which is scale-invariant: $R(tx) = R(x)$, so its values over all nonzero $x$
match those of $x^\top A x$ over the unit sphere. The extreme-values theorem then reads
$\lambda_n \leq R(x) \leq \lambda_1$, with the bounds hit at the extreme
eigenvectors. Traversing the unit circle, $R$ oscillates between $m$ and $M$,
peaking each time the direction lines up with an eigenvector.

$$
% caption: The Rayleigh quotient traced around the unit circle for a 2×2 form
% swings between the two eigenvalues, reaching M at the u₁ direction and m at
% the u₂ direction.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black, ->] (0,0) -- (6.4,0) node[right, black] {angle};
  \draw[black, ->] (0,0) -- (0,3.0) node[above, black] {$R(x)$};
  % M and m guide lines (Q = 3 + 4 sin^2, min 3 max 7 -> scaled to 1..2.6)
  \draw[black, dashed] (0,2.6) -- (6.2,2.6) node[right, black] {$M$};
  \draw[black, dashed] (0,1.0) -- (6.2,1.0) node[right, black] {$m$};
  \draw[acc, thick] plot[domain=0:6.283, samples=80]
    (\x, {1.0 + 1.6*(sin(deg(\x)))^2});
  \node[acc] at (1.57,2.85) {$u_1$};
  \node[acc] at (4.71,2.85) {$u_1$};
\end{tikzpicture}
$$

> **Worked example.** Find the maximum of $x^\top A x$ over $\|x\| = 1$ for
> $$
> A = \begin{bmatrix} 3 & 2 & 1 \\ 2 & 3 & 1 \\ 1 & 1 & 4 \end{bmatrix},
> \qquad 0 = -\lambda^3 + 10\lambda^2 - 27\lambda + 18 = -(\lambda-6)(\lambda-3)(\lambda-1).
> $$
> The greatest eigenvalue is $6$, so the constrained maximum is $6$. Solving
> $(A - 6I)x = 0$ gives the eigenvector $(1,1,1)$, normalized to
> $u_1 = \tfrac{1}{\sqrt3}(1,1,1)$, the unit vector where the maximum is attained.

## Successive constrained maxima

Restricting to directions orthogonal to $u_1$ removes the top eigenvalue from
contention and exposes the next one.

> **Theorem (Second constrained maximum).** With $A$, $\lambda_1$, $u_1$ as in
> the extreme-values theorem, the maximum of $x^\top A x$ subject to $x^\top x = 1$ and
> $x^\top u_1 = 0$ is the second eigenvalue $\lambda_2$, attained at a unit
> eigenvector $u_2$.

The constraint $x^\top u_1 = 0$ deletes the $\lambda_1 y_1^2$ term from the
decoupled sum (it forces $y_1 = 0$), leaving $\lambda_2 y_2^2 + \cdots +
\lambda_n y_n^2$, whose maximum on the remaining unit sphere is now $\lambda_2$.
Continuing to constrain against $u_1, u_2, \dots$ in turn peels the eigenvalues
off one at a time.

> **Theorem (All eigenvalues by constrained maxima).** Order the eigenvalues
> $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ with orthonormal
> eigenvectors $u_1, \dots, u_n$. For each $k = 2, \dots, n$, the maximum of
> $x^\top A x$ subject to
> $$
> x^\top x = 1, \quad x^\top u_1 = 0, \quad \dots, \quad x^\top u_{k-1} = 0
> $$
> is the eigenvalue $\lambda_k$, attained at $x = u_k$.

The whole spectrum is thus recoverable by a sequence of constrained
maximizations, each carried out on the subspace orthogonal to the eigenvectors
already found. This deflation viewpoint is the idea behind the
[power method](/linear-algebra/eigenvalues/power-method) and its numerical
descendants.

$$
% caption: Each orthogonality constraint removes the eigenvector already found,
% so the successive constrained maxima descend through the spectrum
% λ₁ ≥ λ₂ ≥ λ₃.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  bar/.style={draw, fill=acc!12, minimum width=13mm}]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black, ->] (-0.3,0) -- (7.0,0);
  \draw[black, ->] (-0.3,0) -- (-0.3,3.3) node[above, black] {value};
  \node[bar, minimum height=27mm] (b1) at (0.8,1.35) {$6$};
  \node[bar, minimum height=15mm] (b2) at (3.0,0.75) {$3$};
  \node[bar, minimum height=6mm]  (b3) at (5.2,0.30) {$1$};
  \node[black, align=center] at (0.8,-0.7) {no\\constraint};
  \node[black, align=center] at (3.0,-0.7) {$x^T u_1 = 0$};
  \node[black, align=center] at (5.2,-0.78) {$x^T u_1 = 0$\\$x^T u_2 = 0$};
\end{tikzpicture}
$$

## Allocating a budget

Constrained maximization of a quadratic form arises whenever a decision variable
is bounded by resource limits.

> **Worked example.** A county plans to repair $x$ hundred miles of roads and
> improve $y$ hundred acres of parks, with resources capping the pair by
> $4x^2 + 9y^2 \leq 36$. Residents value a schedule by the utility
> $q(x,y) = xy$; maximize it on the boundary of the feasible set, where the
> resources are fully used. The constraint is not a unit sphere, but a change of
> variable makes it one. Rewrite $4x^2 + 9y^2 = 36$ as
> $$
> \left(\frac{x}{3}\right)^2 + \left(\frac{y}{2}\right)^2 = 1,
> $$
> and set $x_1 = x/3$, $x_2 = y/2$, so $x = 3x_1$, $y = 2x_2$ and
> $x_1^2 + x_2^2 = 1$. The utility becomes $q = (3x_1)(2x_2) = 6x_1 x_2$, a
> quadratic form with matrix $A = \begin{bmatrix} 0 & 3 \\ 3 & 0 \end{bmatrix}$,
> whose eigenvalues are $\pm 3$. By the extreme-values theorem the maximum utility on the unit
> circle is $3$, attained at the eigenvector $x_1 = x_2 = 1/\sqrt2$. In the
> original variables the optimal schedule is $x = 3/\sqrt2 \approx 2.1$ hundred
> miles of roads and $y = 2/\sqrt2 \approx 1.4$ hundred acres of parks, the point
> where the resource curve is tangent to the indifference curve $q = 3$.

$$
% caption: The budget curve 4x²+9y²=36 and the indifference curve xy=3 meet
% tangentially at the optimal schedule; there the resource limit is fully used
% and the utility is maximized.
\begin{tikzpicture}[scale=0.95, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black, ->] (0,0) -- (3.7,0) node[right, black] {$x$};
  \draw[black, ->] (0,0) -- (0,2.8) node[above, black] {$y$};
  \draw[black, thick] (3,0) arc (0:90:3 and 2);
  \draw[black, thick] plot[domain=1.55:2.95, samples=40] (\x, {3/\x});
  \fill[acc] (2.12,1.41) circle (2.2pt);
  \draw[black, dashed] (2.12,0) -- (2.12,1.41) -- (0,1.41);
  \node[acc] at (2.75,1.72) {optimum};
  \node[black] at (1.05,0.5) {$xy = 3$};
  \node[black] at (0.62,1.85) {budget};
\end{tikzpicture}
$$

The largest singular value of a matrix is this constrained maximum applied to
$A^\top A$, the starting point for the
[singular value decomposition](/linear-algebra/symmetric-quadratic-svd/singular-value-decomposition).