Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $A$ is a positive definite matrix, then the solution to the minimization problem $(1/2)x^TAx - b^Tx$ is given by $A^{-1}b$. I'm interested in the generalization of this to a Hilbert space. What conditions on $A$ should be required for this to be true in a Hilbert space? Also is there a reference that includes this? I searched Google books, but couldn't find it.

share|improve this question
2  
Have you looked at this? I think self-adjointness along with positivity ($\langle x | A x\rangle > 0$) is what you want, but don't listen to me because I don't know anything about Hilbert spaces. –  Rahul Nov 18 '10 at 8:31
add comment

1 Answer

up vote 2 down vote accepted

What you need is to look at some texts on functional analysis, especially about "Direct Methods" in "Calculus of Variations". I'll give a quick primer here to flesh out what Rahul Narain said in the comments, but it will be by no means complete.

First let us review how the minimization problem is solved in finite dimensional spaces. We will consider a finite dimensional vector space $V$ with an inner product $\langle,\rangle$. Let $A$ be a self-adjoint linear operator $V\to V$, and $b$ some element of $V$. We consider the minimization problem with the non-linear functional $J(x) = \frac12 \langle x,Ax\rangle - \langle b,x\rangle$. There are two steps used in finding the minimizer.

Step 1) Existence of a minimizer. First we need to show that $J(x)$ is bounded from below. This is where we first use that $A$ has only non-negative eigenvalues. If $A$ were to have negative eigenvalues, let $v$ be its eigenvector, and look at $J(kv)$ for $k$ a scalar. Letting $k\nearrow\infty$ we see that $J(kv)\searrow -\infty$ and there cannot be an minimum. Next, if $A$ were to have a non-empty kernel, such that there exists some vector $v$ with the property $Av = 0$ and $\langle b,v\rangle \neq 0$, then again taking $J(kv)$ and sending $k$ to either $\pm\infty$, we will have that the functional $J$ is not bounded below.

So $A$ must only have positive eigenvalues. Now, let $\lambda$ be the smallest of $A$'s eigenvalues. Then we have $\langle x,Ax\rangle > \lambda \|x\|^2$. Using Cauchy-Schwarz inequality, we then have

$$ J(x) > \frac12 \lambda \|x\|^2 - \|b\|\|x\| $$

So we see that for $\|x\| > 2\|b\| / \lambda$, $J(x) > 0$. And by continuity, $J(x)$ is bounded below.

Now, let $j = \inf J < 0$. (The infimum is negative since by choosing $w$ a sufficiently small multiple of $b$, we see that $J(w) < 0$.) By the definition of infimum, there exists a sequence of vectors $(v_k)$ such that $J(v_k) \searrow j$. Since the infimum is less than 0, by our previous computations we know that the sequence $(v_k)$ must all satisfy $\|v_k\| \leq 2\|b\|/\lambda$. Now, this set is a bounded closed ball in a finite dimensional vector space. In particular, it is compact. Hence up to a subsequence $v_k$ must converge. Now using continuity of $J$, you have that the limit element $v_\infty$ of the sequence attains the minimum. That is $J(v_\infty) = j$.

Step 2) Computing the minimizer. Here we just use the Euler-Lagrange equations. At the minimizer, the functional is stationary. That is $(\frac{\delta}{\delta x}J)(v_\infty) = 0$. Taking the variation of the functional $J$, we get, using again that $A$ is self-adjoint, that

$$ \frac{\delta}{\delta x}J = 0 \iff Ax - b = 0 $$

Since $A$ only has positive eigenvalues, it is invertible, so we can solve $v_\infty = A^{-1}b$.


Formally, we can try to do the same thing in infinite dimension. But there are a few caveats. First is that it is not enough that $A$ only has positive eigenvalues. You need that $A$ is coercive in the following sense:

$$ \langle x, Ax\rangle > \lambda \|x\|^2$$

for some $\lambda$. In finite dimensions that $A$ is positive implies the existence of this $\lambda$. In infinite dimensions this is not true. Imagine the $\ell^2$ Hilbert space with standard inner product and the standard basis $(e_k)$. Let $Ae_k = \frac1k e_k$. Then $A$ has only positive eigenvalues. But by taking larger and larger $k$'s, we can make the eigenvalue approach 0 as closely as we want, and violate coercivity. Coercivity allows us to guarantee that the functional $J(x)$ has a bottom.

The second problem is that a closed bounded set in a Hilbert space is not necessarily compact. So we cannot conclude immediately that a minimizing sequence converges in the norm topology. However, using Banach-Alaoglu theorem, the minimizing sequence must have a convergent subsequence in the weak topology of your Hilbert space. So it is sufficient to show that your functional $J(x)$ is what is called "sequentially weakly lower-semicontinuous" to get the desired conclusion. (That condition just guarantees that for any weakly converging sequence $w_k\to_w w_\infty$, $\lim\inf J(w_k) \geq J(w_\infty)$.)

In our particular case, things can be made slightly easier. If we in addition assume that $A$ is a bounded linear operator. Then we can use $(x,y) = \langle x,Ay\rangle$ as an equivalent inner product on our Hilbert space. Then $A^{-1}b$ exists by the Riesz representation theorem, and our functional can be written as $J(x) = \frac12 (x,x) - (A^{-1}b, x)$. Now we run through our previous arguments again. Now $w_k\to_w w_\infty$, and therefore $(A^{-1}b,w_k) \to (A^{-1}b,w_\infty)$ strongly by the definition of weak limits. And we also use the property of weak limits that

$$ \lim\inf (w_k,w_k) \geq (w_\infty,w_\infty)$$

which gurantees lower semi-continuity as desired. So now we've shown that the minimizer exists, and computing the variation we see that the minimizer must satisfy $w_\infty = A^{-1}b$.

So to repeat, a sufficient condition is that $A$ is self-adjoint, bounded, and coercive.

share|improve this answer
    
Thanks so much for your time! It has been very helpful. –  AgCl Nov 18 '10 at 21:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.