1

I'm trying to understand the proof of the convergence of the Broyden method through the book Numerical Methods for Unconstrained Optimization and Nonlinear Equations, and at some point the proof relies on the following lemma (page 77):

Lemma 4.1.15 Let $F$, $J$ satisfy the conditions of Lemma 4.1.12. Then, for any $v, u \in D$,

$||F(v)-F(u)-J(x)(v-u)|| \leq \frac{\gamma}{2}(||v-x||+||u-x||)||v-u||$

For context, $J$ is the Jacobian matrix of $F$ and Lemma 4.1.12 says the following:

Lemma 4.1.12 Let $F:\mathbb{R}^n \rightarrow \mathbb{R}^m$ be continuously differentiable in the open convex set $D \in \mathbb{R}^n, x \in D$, and let $J$ be Lipschitz continuous at $x$ in the neighborhood $D$, using a vector norm and the induced matrix operator norm and the constant $\gamma$. Then, for any $x+p \in D$,

$||F(x+p)-F(x)-J(x)p|| \leq \frac{\gamma}{2}||p||^2$

You can find the proof of $4.1.12$ here, page 13.

Unfortunately, the proof of Lemma 4.1.15 is left as an exercise to the reader and I'm unable to figure it out. By manipulating the initial expression, I can show that

$||F(v)-F(u)-J(x)(v-u)|| \leq \frac{\gamma}{2}(||v-x||^2+||u-x||^2)$

but this is not the required inequality.

Any hints?

Luís Pureza
  • 193

2 Answers2

0

Letting $p = v-u$, we have \begin{align*} \| F(v) - F(u) - J(x)(v-u)\| & = \| F(u+p) - F(u) - J(x) p\| \\ & \leq \| F(u+p) - F(u) - J(u)p\| + \| J(u)p - J(x)p\|. \end{align*} The first term can be bounded using Lemma 4.1.12 by \begin{align*}\frac{\gamma}{2} \|p\|^2 & = \frac{\gamma}{2} \|v-u\| \|v-u\| \\ & \leq \frac{\gamma}{2} \left(\|v-x\| + \|u-x\|\right) \|v-u\|. \end{align*} The second term can be bounded since $J$ is Lipschitz, \begin{align*}\|J(u)p-J(x)p\| & \leq \|J(u)-J(x)\| \|p \| \\ & \leq \gamma \|u-x\| \|v-u\|. \end{align*} So, we get the result if we enlarge the constant a bit.

user197427
  • 516
0

So the person who did it isn't wrong but isn't right either. First, recall what Lipschitz continuous means

$$ Lip_\gamma (x) $$

means $\gamma$ is the best constant that satisfies $|f(x) - f(y)| \le \gamma|x-y|$

Now, for this problem, you need to think about change in variable.

$ \|F(v) - F(u) - J(x)(v-u)\| = \|\int_u^v J(z)dz - J(x)(v-u)\| \\ = \|\int_u^v( J(z) - J(x) )dz \| \\ = \|\int_0^1 (J(u + t(v-u)) - J(x)) (v-u)dt\| $

For this, I let $z = u + t(v-u)$ so $dz = dt(v-u)$. I want to integrate from 0 to 1 to make my life easier. Now, think about adding 0. The text book you are using shows many different ways of adding 0.

$ u + t(v-u) = u + t(v-u) + xt - xt \\ = u(1 - t) - x(1-t) + t(v-x) $

Now insert this back into the integral.

$ \|\int_0^1 J(u + t(v-u)) - J(x) (v-u)dt\| = \|(v-u)\int_0^1 (J(u(1 - t) - x(1-t) + t(v-x)) - J(x) )dt \| \\ \le \|(v-u)\int_0^1 \gamma(u(1 - t) - x(1-t) + t(v-x)-x )dt \| $

Do the integration and you will get your answer. The main idea is to figure out WHERE and HOW you add 0.

anonymous
  • 1