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

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.

• Note that you are getting the equation for the eigenvalues $(A+\lambda I)x=0$... But you know that your matrix is positive definite by assumption... Thus order the Eigenvalues from the smallest to the largest and you will be done. Jul 21 '16 at 11:42
• Positive definite matrices have only positive Eigenvalues. Thus $\lambda > 0$? But how does this help? Jul 21 '16 at 11:45
• Your equation $0=(A+\lambda I)x^\ast$ has a nontrivial solution ($x\neq 0$) iff $\lambda$ is an eigenvalue of the matrix, and the second constraint tells us that we are only considering normed eigenvectors. So, plugging such a solution into the function $x^\top A x$ gives ${x^\ast}^\top \lambda {x^\ast}=\lambda$. Now, to minimize the function, take the smallest such lambda and you will be done. Jul 21 '16 at 11:50
• Without the constraints, $x^TAx$ is minimized when $x=0$, which is not what you want... Jul 21 '16 at 11:51
• @b00nheT The eigenvalue is actually $-\lambda$. Jul 21 '16 at 12:02

$$\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.

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.

$$\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.