2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – b00n heT
    Jul 21, 2016 at 11:42
  • $\begingroup$ Positive definite matrices have only positive Eigenvalues. Thus $\lambda > 0$? But how does this help? $\endgroup$ Jul 21, 2016 at 11:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – b00n heT
    Jul 21, 2016 at 11:50
  • $\begingroup$ Without the constraints, $x^TAx$ is minimized when $x=0$, which is not what you want... $\endgroup$ Jul 21, 2016 at 11:51
  • $\begingroup$ @b00nheT The eigenvalue is actually $-\lambda$. $\endgroup$ Jul 21, 2016 at 12:02

3 Answers 3

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .