Trust-region method

210 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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.