An eigenvalue algorithm to solve constrained quadratic form minimization

Question

I have a quadratic form $\mathbf{x}^T A \mathbf{x}$ (where $A\in \mathbb{R}^{n\times n}$ is symmetric matrix and $\mathbf{x}\in \mathbb{R}^n$) that I want to minimize given the normalization constraint $\mathbf{x}^T\mathbf{x}=1$.

Because $\mathbf{A}$ is a adjacency matrix of an undirected graph then I know that it is symmetric and real and also sparse.

What is an appropriate memory conservative algorithm to solve this kind of problem?

Is it good to solve the eigensystem $\mathbf{A}\mathbf{x}=\lambda \mathbf{x}$ and then taking as solution the first smallest nonzero eigenvalue and its related eigenvector?

If this is the way to proceed how is it possible to get the smallest eigenvalue with subspace iteration?

Answer 1

The optimal objective function value will be the minimal eigenvalue of $\mathbf{A}$, including zero eigenvalues, and the optimal solution will be the eigenvector of $\mathbf{A}$ corresponding to that eigenvalue.

Eigenvectors, by definition, must be nonzero vectors.

One way to derive this answer is to note that a symmetric matrix $\mathbf{A}$ will always have the eigendecomposition $\mathbf{A}$ = $\mathbf{Q}^{T}\boldsymbol{\Lambda}\mathbf{Q}$, where $\mathbf{Q}$ is an orthogonal matrix and $\boldsymbol{\Lambda}$ is a diagonal matrix consisting of the eigenvalues of $\mathbf{A}$ (such that they correspond correctly to the columns of $\mathbf{Q}$). Using the transformation $\mathbf{y} = \mathbf{Qx}$, and recalling that orthogonal matrices preserve the standard inner product norm, the problem $\min_{\mathbf{x}^{T}\mathbf{x} = 1}\mathbf{x}^{T}\mathbf{A}\mathbf{x}$ is equivalent to $\min_{\mathbf{y}^{T}\mathbf{y} = 1} \mathbf{y}^{T}\boldsymbol{\Lambda}\mathbf{y}$. The solution to the latter problem is a vector whose only nonzero entry is a one, at the index corresponding to the minimal eigenvalue.

As Arnold Neumaier states, Lanczos would work.

Answer 2

$x=0$ does not satisfy the constraint, hence is irrelevant. The solution to your problem is any normalized eigenvector belonging to the smallest eigenvalue of $A$.

An eigenvector to the smallest eigenvalue of a large and sparse matrix can be found efficiently by the Lanczos algorithm, see http://en.wikipedia.org/wiki/Lanczos_algorithm