Quadratic Extrema Under Linear Constraints

From Linear Constraints to a Smaller Optimization Problem

A quadratic form can have very different extrema depending on which vectors are allowed. If the vectors must satisfy homogeneous linear equations, they lie in a subspace. The key is to describe that subspace with an orthonormal basis, so that coordinates within it preserve lengths. In those coordinates, the original quadratic form becomes a smaller symmetric matrix, and its eigenvalues determine the constrained extrema.

Throughout, let \(\mathbf{A}\in\mathbb{R}^{n\times n}\) be symmetric, so \(\mathbf{A}^{\top}=\mathbf{A}\). Its quadratic form is \(q(\mathbf{x})=\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\). We consider vectors in a linear subspace \(S\subseteq\mathbb{R}^n\) subject to \(\|\mathbf{x}\|=1\). The unit-length condition matters: without it, scaling a feasible vector can make the quadratic form arbitrarily large or small whenever it takes a positive or negative value.

Suppose the feasible subspace has dimension \(k\geq 1\), and let \(\mathbf{Q}\in\mathbb{R}^{n\times k}\) have as its columns an orthonormal basis of \(S\). Thus \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_k\), and every \(\mathbf{x}\in S\) can be written uniquely as \(\mathbf{x}=\mathbf{Q}\mathbf{y}\) for \(\mathbf{y}\in\mathbb{R}^k\). Orthonormality gives \(\|\mathbf{Q}\mathbf{y}\|^2=\mathbf{y}^{\top}\mathbf{Q}^{\top}\mathbf{Q}\mathbf{y}=\|\mathbf{y}\|^2\). Substituting this coordinate representation into the quadratic form gives \(q(\mathbf{x})=\mathbf{y}^{\top}(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q})\mathbf{y}\).

When constraints are written as \(\mathbf{C}^{\top}\mathbf{x}=\mathbf{0}\), the feasible subspace is \(S=\operatorname{Nul}(\mathbf{C}^{\top})\). Find an orthonormal basis for this null space, place its vectors in the columns of \(\mathbf{Q}\), and then form \(\mathbf{B}\). The columns of \(\mathbf{Q}\) can be obtained by taking a basis of the subspace and applying the Gram-Schmidt process.

The Constrained Extrema Theorem

Proof. Because \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_k\), the representation \(\mathbf{x}=\mathbf{Q}\mathbf{y}\) preserves length: \(\|\mathbf{x}\|=1\) exactly when \(\|\mathbf{y}\|=1\). Also, substitution gives \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=\mathbf{y}^{\top}\mathbf{B}\mathbf{y}\), and \(\mathbf{B}\) is symmetric. By the Spectral Theorem, \(\mathbf{B}\) has an orthonormal eigenbasis \(\mathbf{u}_1,\ldots,\mathbf{u}_k\) with real eigenvalues \(\lambda_1,\ldots,\lambda_k\). Write any unit \(\mathbf{y}\) as \(\mathbf{y}=\sum_{i=1}^k c_i\mathbf{u}_i\). Orthonormality gives \(\sum_{i=1}^k c_i^2=1\), and the eigenvector equations give \(\mathbf{y}^{\top}\mathbf{B}\mathbf{y}=\sum_{i=1}^k\lambda_i c_i^2\). This is a weighted average of the eigenvalues, with nonnegative weights \(c_i^2\) summing to \(1\). Therefore it is at least \(\lambda_{\min}\) and at most \(\lambda_{\max}\). Taking \(\mathbf{y}\) to be a unit eigenvector for either extreme eigenvalue attains the corresponding bound. Equality at the minimum requires \(c_i=0\) whenever \(\lambda_i>\lambda_{\min}\), since each such term contributes a strictly positive amount to \(\sum_i(\lambda_i-\lambda_{\min})c_i^2\). Thus \(\mathbf{y}\) lies in the eigenspace for \(\lambda_{\min}\). The same argument applied to \(\lambda_{\max}-\mathbf{y}^{\top}\mathbf{B}\mathbf{y}=\sum_i(\lambda_{\max}-\lambda_i)c_i^2\) shows that equality at the maximum occurs exactly in the largest-eigenvalue eigenspace. Mapping back by \(\mathbf{x}=\mathbf{Q}\mathbf{y}\) proves the assertion about feasible optimizers. \(\square\)

This theorem applies even when an extreme eigenvalue is repeated: every unit vector in its eigenspace gives the same extreme value. The eigenvalues to use are those of \(\mathbf{B}\), not automatically those of \(\mathbf{A}\). Restriction to a subspace changes the matrix that represents the quadratic form in feasible coordinates.

Worked Reductions and Checks

Common Pitfalls and Practical Checks

Do not omit the unit-norm condition. For example, take \(\mathbf{A}=\begin{bmatrix}1&0\\0&-1\end{bmatrix}\) and the feasible subspace \(S=\mathbb{R}^2\). The vector \((t,0)^{\top}\) is feasible for every real \(t\), and its quadratic-form value is \(t^2\), which has no finite maximum as \(t\) grows. Likewise, \((0,t)^{\top}\) gives value \(-t^2\), with no finite minimum. A wrong claim that the unconstrained-in-length maximum is the largest eigenvalue \(1\) fails at \((2,0)^{\top}\), where the value is \(4\). Eigenvalue extrema apply here to the unit sphere in the feasible subspace.

Do not substitute ambient eigenvalues for restricted ones. In the sum-constraint example, the ambient maximum eigenvalue is \(3\), but its eigenvector is infeasible. The restriction matrix has eigenvalues \(1\) and \(7/3\), so the constrained maximum is \(7/3\). The required calculation is \(\mathbf{Q}^{\top}\mathbf{A}\mathbf{Q}\), not merely a list of eigenvalues of \(\mathbf{A}\).

Check the basis before using it. Its columns must satisfy the constraints and be orthonormal. If they are not orthonormal, the coordinate vector need not have the same length as the original vector; the unit-vector optimization then requires an additional constraint in the new coordinates. Using an orthonormal basis makes the reduced problem exactly \(\|\mathbf{y}\|=1\).

The procedure is therefore: describe the feasible subspace, choose an orthonormal basis, compute the restriction matrix, and use its extreme eigenvalues. An eigenvector in the reduced coordinates must be mapped back by \(\mathbf{x}=\mathbf{Q}\mathbf{y}\), after which the constraints, unit norm, and quadratic-form value can all be checked directly. If the feasible subspace is \(\{\mathbf{0}\}\), it contains no unit vectors, so there is no feasible optimization problem of this form.