Constrained Optimization

A quadratic form $Q (x) = x^{⊤} A x$ has no finite maximum on all of $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, ∥ x ∥^{2} = 1, x^{⊤} x = 1, x_{1}^{2} + \dots + x_{n}^{2} = 1.

The expanded version $x_{1}^{2} + \dots + 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.

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^{⊤} A x : ∥ x ∥ = 1}, m = min {x^{⊤} A x : ∥ x ∥ = 1} .

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

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.

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.

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 ^{⊤} A x}{x ^{⊤} x},

which is scale-invariant: $R (t x) = R (x)$ , so its values over all nonzero $x$ match those of $x^{⊤} A x$ over the unit sphere. The extreme-values theorem then reads $λ_{n} \leq R (x) \leq λ_{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.

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.

Successive constrained maxima

Restricting to directions orthogonal to $u_{1}$ removes the top eigenvalue from contention and exposes the next one.

The constraint $x^{⊤} u_{1} = 0$ deletes the $λ_{1} y_{1}^{2}$ term from the decoupled sum (it forces $y_{1} = 0$ ), leaving $λ_{2} y_{2}^{2} + \dots + λ_{n} y_{n}^{2}$ , whose maximum on the remaining unit sphere is now $λ_{2}$ . Continuing to constrain against $u_{1}, u_{2}, \dots$ in turn peels the eigenvalues off one at a time.

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 and its numerical descendants.

Each orthogonality constraint removes the eigenvector already found, so the successive constrained maxima descend through the spectrum λ₁ ≥ λ₂ ≥ λ₃.

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 $4 x^{2} + 9 y^{2} \leq 36$ . Residents value a schedule by the utility $q (x, y) = x y$ ; 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 $4 x^{2} + 9 y^{2} = 36$ as

(\frac{x}{3})^{2} + (\frac{y}{2})^{2} = 1,

and set $x_{1} = x /3$ , $x_{2} = y /2$ , so $x = 3 x_{1}$ , $y = 2 x_{2}$ and $x_{1}^{2} + x_{2}^{2} = 1$ . The utility becomes $q = (3 x_{1}) (2 x_{2}) = 6 x_{1} x_{2}$ , a quadratic form with matrix $A = [0330]$ , 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/ 2$ . In the original variables the optimal schedule is $x = 3/ 2 \approx 2.1$ hundred miles of roads and $y = 2/ 2 \approx 1.4$ hundred acres of parks, the point where the resource curve is tangent to the indifference curve $q = 3$ .

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.

The largest singular value of a matrix is this constrained maximum applied to $A^{⊤} A$ , the starting point for the singular value decomposition.