1
$\begingroup$

The question has to do with the trust-region method for unconstrained optimization. I came across it on p.~392 of Linear and Nonlinear Optimization, by Griva, Nash and Sofer.

Let $p(\lambda)$ be defined by $$\big(\nabla^2 f(x)+\lambda I\big)p(\lambda)=-\nabla f(x).$$ (Here $x$ is just some $x\in\mathbb{R}^n$; typically $x=x_k$ is your $k$-th estimate of the optimizer.)

Prove that $\lim_{\lambda\rightarrow\infty}\lambda p(\lambda)=-\nabla f(x).$

I'm sure this is not hard for any of you guys out there who actually know this stuff, but, sadly, I'm not one of you. Much appreciate your help.

By the way, I do not know if one could replace $\nabla^2f(x)$ with any symmetrical matrix, and the result would still hold, or if the argument I miss uses properties of $\nabla^2f(x)$ explicitly.

$\endgroup$
1
$\begingroup$

It only boils down the following statement: For a real symmetric matrix $A$, vector $b$, and $\lambda > -\lambda_\min(A)$ let $$ p(\lambda) = (A + \lambda I)^{-1} b. $$ Then, $\lambda p(\lambda)\to b$ for $\lambda\to\infty$.

Proof: Since the inversion of matrices is continuous, we obtain $$ \lambda p(\lambda) = \lambda(A + \lambda I)^{-1} b = \Bigl(\underbrace{\frac1\lambda A}_{\to 0} + I\Bigr)^{-1} b \to b $$ for $\lambda\to \infty$.

Old Proof:

Since $A$ is real symmetric, let w.l.o.g. $A$ be diagonal. Then, we have $$ \lambda p_i(\lambda) = b_i \underbrace{\frac{\lambda}{\lambda_i + \lambda}}_{\to 1} \to b_i $$ for $\lambda \to\infty$.

Aside:

The essence of this statement is: If $\lambda\ge 0$ is small, you get the Newton direction. If $\lambda \ge 0$ is large, you the steepest descent direction. The trust region direction is a mix of both.

$\endgroup$
  • $\begingroup$ Thanks a lot for wanting to help. Could you please elaborate on one point: why can we assume A is diagonal w.l.o.g.? I'm sure your right, I just don't see it. $\endgroup$ – Bart Patzer Apr 3 '16 at 8:17
  • $\begingroup$ @BartPatzer: That is because $A$ is similar to a diagonal matrix. One doesn't really need that fact. I edited the answer and add an elementary proof without using diagonalization. $\endgroup$ – user251257 Apr 3 '16 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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