How can I solve an optimization problem $x^T A x$ with constraint $x^T x = 1$?

Question

Let $A \in \mathbb{R}^{n \times n}$ be a positive definite matrix.

\begin{align} &\operatorname*{minimize}_{x \in \mathbb{R}^n} & & x^T A x \\ &\text{subject to} &&x^T x = 1 \end{align}

What is the minimum which fulfills the constraints?

My thoughts

• The constraint means that all possible solutions are on a unit sphere.
• A necessary condition (if there were no constraints) would be

$$ \frac{\partial x^T A x}{\partial x} = 2 A x \overset{!}{=} 0 $$

• The Lagrange function is

\begin{align} \mathcal{L} (x, \lambda) &= x^T A x + \lambda (x^T x - 1)\\ \nabla_x \mathcal{L} &= \nabla_x (x^*)^T A x^* + \lambda \nabla_x ((x^*)^T x^* - 1) \\ &= 2 \cdot A \cdot x^* + \lambda \cdot 2 \cdot x^* \overset{!}{=} 0\\ \Leftrightarrow 0 &\overset{!}{=} A \cdot x^* + x^*\\ \Leftrightarrow 0 &\overset{!}{=} (A + \lambda I) \cdot x^*\\ \frac{\partial}{\partial \lambda} \mathcal{L} &= x^T x - 1 = 0 \end{align}

I have no idea if this is correct / how to continue.

Answer 1

Sketch:

• Since $A$ is positive-definite, it is symmetric and hence has an orthonormal eigenbasis. Let $v_1,\cdots,v_n$ be the eigenvectors with corresponding eigenvalues $\lambda_1,\cdots,\lambda_n$.

• Therefore we can write $x=\sum a_iv_i$ where $\sum a_i^2=1$. The sum condition comes from the fact that $\langle\sum a_iv_i,\sum a_iv_i\rangle=\sum a_ia_j\langle a_i,a_j\rangle=\sum a_i^2\langle a_i,a_i\rangle=\sum a_i^2$ by orthonormality.

• One can easily calculate $x^TAx$ by noting that $Ax=\sum a_i\lambda_iv_i$ and then taking the inner product as above. This results in $\sum a_i^2\lambda_i$ by orthonormality, which is minimized/maximized when all but one $a_i$ is zero.

See also Raleigh Quotient.

Answer 2

$$\mathrm x^T \mathrm A \mathrm x \geq \lambda_{\min} (\mathrm A) \|\mathrm x\|_2^2 = \lambda_{\min} (\mathrm A) > 0$$

because $\|\mathrm x\|_2 = 1$ and $\mathrm A \succ \mathrm O$. The minimum is attained at the intersection of the eigenspace of $\lambda_{\min} (\mathrm A)$ with the unit Euclidean sphere.

Answer 3

The above approaches are correct, but just to make the link with your solution, here is another way of writing things:

$$ \begin{cases} \nabla_x \mathcal{L} = 0\\ \nabla_{\lambda} \mathcal{L} = 0\\ \end{cases} \quad \Rightarrow\quad \begin{cases} Ax = \lambda x\\ x^{T}x=1\\ \end{cases} $$

In other words, unitary eigenvectors of $A$ satisfy the Lagrangian condition.

Note that the set $x^{T}x=1$ is not convex, but it is compact, so $f(x)=x^{T}Ax$ does reach its minimum on $x^{T}x=1$. So our unitary eigenvectors are definitely good candidates here.

Let $\hat{x}$ be a unitary eigenvector of $A$. It follows that $$ f(\hat{x})=\hat{x}^{T}A\hat{x}=\lambda x^{T}x=\lambda $$

We can conclude that the minimum of $f$ is the smallest eigenvalue of $A$, and is reached by its unitary eigenvector.