9
$\begingroup$

I am reading a paper where

$$\frac{\|g_{k+1}\|}{\|g_{k}\|^2} \leq c \tag{1}$$ as $k\to \infty$ where $g_k = g(x_k) \stackrel{\Delta}{=} \nabla f(x_k)$ and $\| \nabla^2 f(x_k)\| \leq L_H$. Then, it is stated that from Taylor expansion of $g_k$ and $g_{k+1}$ around $x_*$ and from $g(x_*)=0$ we get

$$\frac{\|x_{k+1} - x_*\|}{\|x_{k} - x_*\|^2} \leq c \tag{2}$$ as $k\to \infty$. I know that the Taylor expansion is

$$g_{k+1} = \nabla f (x_k + p_k) = \nabla f (x_k) + \int_{0}^{1} \nabla^2 f (x_k + t p_k) p_k dt$$ with $p_k = x_{k+1} - x_k$ but I found it confusing to apply it in $x_*$ instead of $x_k$. The most possibly useful relation I have found is

$$\nabla f_k -\nabla f_* = \int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt \tag{3}$$ in the proof of Theorem 3.5 in [1] but again I could not understand how it is derived from Taylor's theorem in Theorem 2.1 in [1]. Taking the norm of $(3)$ we get

$$\begin{aligned}\| \nabla f_k\| \leq & \underbrace{\|\nabla f_k \|}_{0}+ \|\int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt \| \\ \leq & \underbrace{\|\nabla f_k \|}_{0}+ \int_{0}^{1} \|\nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)\|dt \leq L_H \|x_k - x_* \|\end{aligned}\tag{4}$$ where $\|\nabla^2 f(x) \| \leq L_H$ is used. Similarly for step $k+1$ we get

$$\| \nabla f_{k+1}\| \leq \|x_{k+1} - x_* \|$$ which get as close to $(2)$. Could you please someone help to proceed?

[1]Jorge Nocedal, Numerical Optimization

$\endgroup$
10
  • $\begingroup$ Can You give The link of the paper!!! $\endgroup$
    – user860474
    Commented Jun 20, 2022 at 16:09
  • 1
    $\begingroup$ @Math_Buddy Thanks for the response. You can see the end of the proof of Theorem 13 here and more specifically, eq. (82). $\endgroup$
    – Thoth
    Commented Jun 20, 2022 at 16:42
  • 1
    $\begingroup$ The same fact can be found in the end of the proof of Corollary 4.8 here. $\endgroup$
    – Thoth
    Commented Jun 20, 2022 at 18:54
  • 1
    $\begingroup$ Can someone explain why $$\nabla f_k -\nabla f_* = \int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt$$ using $$g_{k+1} = \nabla f (x_k + p_k) = \nabla f (x_k) + \int_{0}^{1} \nabla^2 f (x_k + t p_k) p_k dt$$? You can found this equation in Theorem 3.5 book Jorge Nocedal, Numerical Optimization. $\endgroup$
    – Thoth
    Commented Jun 24, 2022 at 12:01
  • 1
    $\begingroup$ your first line is just $n$ dimensional version of: $$f'(a) - f('b) = \int_0^1 f''(a + t(b-a))(b-a)dt$$ $\endgroup$
    – dezdichado
    Commented Jun 24, 2022 at 15:15

2 Answers 2

4
$\begingroup$

For simplicity in notation assume $x_*=0$ from now on. It looks as if you work in Euclidean space $V={\Bbb R}^n$ (but the result in fact holds in any Banach space). $|\cdot|$ denotes norm in $V$ and $\|\cdot\|$ is the induced operator (or matrix) norm in $L(V)$.

In order for this to work you need that the Jacobian $J=Dg(0)=D^2f(0)$ be invertible, i.e. there exists $0<\alpha\leq \beta<+\infty$ so that $$ \alpha |x| \leq |J x| \leq \beta |x|, \ \ \forall\ x\in V.$$ $f$ should also be $C^2$ so that for any $\epsilon>0$ there is $\delta(\epsilon)>0$ so that $\|Dg(x)-J\| < \epsilon$ for $|x|<\delta(\epsilon)$.We have

$$ g(x) = g(x)-g(0) = \int_0^1 \left( \frac{d}{dt} g(tx)\right) dt = \left(\int_0^1 Dg(tx) \; dt \right)x. $$ Taking $\epsilon=\alpha/2$ we get for $|x|<\delta(\alpha/2)$ $$ |g(x)-Jx| = \left| \int_0^1 \left( Dg(tx)-Dg(0)\right) dt \ x \right| \leq \left\| \int_0^1 \left( Dg(tx)-Dg(0)\right) dt \right\|\ |x| \leq \alpha/2 |x|,$$ so we get for such $x$: $$ \alpha/2 \; |x| \leq |g(x)| \leq (\beta+\alpha/2) \; |x| .$$ From this the equivalence of (1) and (2) follows (with distinct constants $c$) when the points are close enough to $x_*$ ($=0$). For example, if $|x_k|,|x_{k+1}|<\delta$ and $|g(x_{k+1})|/|g(x_k)|^2 \leq c$ then $|x_{k+1}| / |x_k|^2 \leq c \times \frac{2}{\alpha} \times (\beta+\alpha/2)^2$.

$\endgroup$
6
  • $\begingroup$ Thanks for the response! I am trying to get into your point. You assume that $J$ is positive definite. Can we relax this by assuming positive semi-definiteness? From the technical point of view I do not understand the calculations with the integrals involving $g$. Could you please provide some more details? In addition, the upper bound of $| g(x) - Jx|$ is $\epsilon a / 2$ more correctly? Finally, could you please provide some more details on how $(1) \equiv (2)$ is implied when using the last inequality? $\endgroup$
    – Thoth
    Commented Jun 25, 2022 at 20:35
  • 1
    $\begingroup$ $J$ need not be postive definite. But it must be invertible, so no zero eigenvalues. Otherwise, for $|x|>0$, the value of $|g(x)|$ may be arbitrarily close to zero. Not sure what you need for understanding the integrals. The first expresses that $g$ is the integral of its derivative (which I then calculate). The second uses the trivial identity: $Jx=Dg(0)x = \int_0^1 Dg(0) x \; dt$. I have added one direction (1) implies (2) just using the previous upper/lower bound on $|g(x)|/|x|$. $\endgroup$
    – H. H. Rugh
    Commented Jun 25, 2022 at 21:58
  • $\begingroup$ Thanks for the comment and the edit! I have two questions. Why $| g(x)|$ goes to zero if $J$ has zero eigenvalue? In addition, I have some questions about $|x|<\delta(\epsilon)$? Why we need that? In addition, I am not used to bounds like $\delta(\epsilon)$. I mean using $\delta$ as a function of $\epsilon$. In the same scope, why do we use $\epsilon = a/2$? Could you please provide some details? $\endgroup$
    – Thoth
    Commented Jun 26, 2022 at 15:15
  • 1
    $\begingroup$ For the $\delta=\delta(\epsilon)$ part you could just as well say: For any $\epsilon$ there is $\delta$ such that... In the present context you could say given $\epsilon=\alpha/2$ (which is what we need in the end because we want to get a non-zero lower bound for $g(x)$) there is $\delta>0$ such that ... etc.... If $v\neq 0$ is in the kernel of $J$ then for $x=v$ you have no control of what happens to $g(v)$. It could e.g. simply equal zero if $g(x)=Jx$. $\endgroup$
    – H. H. Rugh
    Commented Jun 26, 2022 at 17:28
  • $\begingroup$ Thanks for the response again. I am trying to understand the example. So if there is a zero eigenvalue, then there might $a=0$ witch makes $| g(x) - Jx| \leq a |x| = 0$ which implies $g(x)=Jx$? In addition, a last question I hope. We define $| g(x) - Jx| $ to reach arithmetically the finally result but is there any intuition to compare $g(x)$, i.e., the gradient, with $Jx$, i.e., a Hessian-vector product? In other words, I am trying to understand the rationale as I didn't do it my self. Any help is highly appreciated. $\endgroup$
    – Thoth
    Commented Jun 27, 2022 at 11:32
4
+25
$\begingroup$

REVISED

From Theorem 2.1 in your citation $[1]$ we have: for $p_k=h_k=x_{k}-x_{*}$ and $x_k$ is a sequence of points in $\textbf{R}^N$ such that $\lim_{k\rightarrow \infty}x_k=x_{*}$ , $\nabla f(x_{*})=0$, $\nabla^2 f(x_{*})\neq 0$. Hence for all $x$ in an open ball $B$ with center $x_{*}$ we have $||\nabla^2f(x)||>0$. $$ \nabla f(x_k)=\nabla f(x_{*}+h_k)=\nabla f (x_*)+\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt\Rightarrow $$ $$ \nabla f(x_k)=\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt.\tag 1 $$ Since $L_H\geq ||\nabla^2f(x)||\geq L'>0$ : $(2)$ in $B$, we get $$ ||g_k||=||\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt||\leq \int^{1}_{0}||\nabla^2f(x_*+th_k)||\cdot ||h_k||dt= $$ $$ \leq L_H\int^{1}_{0}dt(||h_k||)=L_H ||h_k||. $$ Also it holds from the definition of norm of matrices $A,B$, where $A\in M_{n\times n}$ and $B\in M_{n\times 1}$ that $||A\cdot B||\leq ||A||\cdot ||B||$ hence we can define $\Gamma(A,B)$ to be such that $\Gamma(A,B)=\frac{A\cdot B}{||A||\cdot ||B||}$. (Note that $\Gamma(A,B)$ is a vector and if $A\in M_{n\times n}$, $B\in M_{n\times 1}$, then $\Gamma=\Gamma(A,B)\in M_{n\times 1}$ and $0\leq ||\Gamma(A,B)||\leq 1$ see also Matrix Norm provited that $B$ is small enough and positive). One can see that one such norm is $$ ||A||_2:=\left(\sum^{n}_{i,j=1}|a_{i,j}|^2\right)^{1/2}\textrm{, }A\in M_{n\times n} $$ and $$ ||B||_2:=\left(\sum^{n}_{i=1}|b_i|^2\right)^{1/2}\textrm{, }B\in M_{n\times 1}.\tag 2 $$ Hence there holds if $A,C\in M_{n\times n}$ and $B\in M_{n\times 1}$ $$ i)\textrm{ }||A||_2\geq 0\textrm{ and }||A||_2=0\Leftrightarrow A=0 $$ $$ ii)\textrm{ }||cA_2||_2=|c|\times ||A||_2 $$ $$ iii)\textrm{ }||A+C||_2\leq ||A||_2+||C||_2 $$ $$ iv)\textrm{ }||A\cdot C||_2\leq ||A||_2\cdot ||C||_2 $$ $$ v)\textrm{ }||A\cdot B||_2\leq ||A||_2||B||_2. $$ Also if $A=(a_{i,j})_{n\times n}$ and $0<||A||_2\leq 1$, then exists $i_0,j_0$ such that $a_{i_0,j_0}\neq 0$ and for all $i,j\Rightarrow |a_{i,j}|\leq 1$ and if $B=(b_{i,j})_{n\times 1}$ and $0<||B||_2\leq 1$, then exists $i_0$ such that $b_{i_01}$ and for all $i$, $0<|b_{i,1}|\leq 1$. In our case it is $$ A=\nabla^2f(x_{*}+th_k)\in M_{n\times n}\textrm{ and }\Gamma_k(t),g_k,h_k\in M_{n\times 1}. $$ Also $$ \Gamma_k(t)=\frac{\nabla^2f(x_{*}+th_k)\cdot h_k}{||\nabla^2f(x_{*}+th_k)||_2\cdot ||h_k||_2}. $$ Hence $$ g_k=\int^{1}_{0}\nabla^2f(x_{*}+th_{k})\cdot h_kdt=\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\cdot ||h_k||_2\Gamma_k(t)dt= $$ $$ =||h_k||_2\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\Gamma_k(t)dt. $$ Here $\Gamma_k(t)=\sum^{n}_{j=1}\Gamma^{(j)}_{k}(t)\left(\overline{e}_{j}\right)^T$, where $\overline{e}_1=\{1,0,0,\ldots,0\}$, $\overline{e}_{2}=\{0,1,0,\ldots,0\}$,$\ldots$, $\overline{e}_{N}=\{0,0,0,\ldots,1\}$ is the usual base of $\textbf{R}^{n}$ and $\Gamma^{(j)}_{k}(t)$ are continuous functions of a single variable in $\textbf{R}$ such that $0\leq ||\Gamma_k(t)||_2\leq 1\Rightarrow 0\leq |\Gamma^{(j)}_k(t)|\leq 1$, (since we can choose such norm). Hence in our case it is $$ g_k=||h_k||_2\cdot \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\left(\sum^{n}_{j=1}\Gamma^{(j)}_{k}(t)(\overline{e}_j)^T\right)dt= $$ $$ =||h_k||_2\cdot \sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_{k}(t)dt\right)(\overline{e}_j)^T. $$ Hence $$ ||g_k||_2=||h_k||_2\cdot ||\sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_{k}(t)dt\right)(\overline{e}_j)^T||_2. $$ But $$ 0<||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2= $$ $$ =\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right|^2\right)^{1/2}\leq C. $$ Otherwise for all $j$ it would hold
$$ \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt=0\Rightarrow ||g_k||_2=0\Rightarrow g_k=0, $$ for a certain $k=k_0\in\textbf{N}$ hence we have two points $x_{k_0},x_{*}\in B$, such that $\nabla f(x_{*})=\nabla f(x_{k_0})=0\Rightarrow \exists \xi\in B: \nabla^2f(\xi)=0$, which is imposible (see Mean value theorem). If we have two distinct points $P_1,P_2$ near each other with zero gradient, then exists point $P_0$ near $P_1,P_2$ such that Hessian is zero at $P_0$.

Thus from not vanish of $$ ||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2= $$ $$ =\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right|^2\right)^{1/2} $$ we have that exists at least one $j=j_0$ such that
$$ 0<m^{(j_0)}_k\leq \left|\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j_0)}_{k}(t)dt\right|. $$ Hence from the continuity of all $\Gamma^{(j)}_{k}(t)$, we can write for some costants $m,M$ such that $0<m<M<\infty$ that $$ 0<m ||h_k||_2\leq ||g_k||_2\leq ||h_k||_2 M. $$ Hence $$ \frac{m ||h_{k+1}||_2}{M^2 ||h_k||_2^2}\leq\frac{||g_{k+1}||_2}{||g_k||_2^2}\leq \frac{M||h_{k+1}||_2}{m^2||h_k||_2^2} $$ Hence we have using $||g_{k+1}||_2\leq c ||g_k||_2^2$ that $$ ||h_{k+1}||_2\leq c \frac{M^2}{m}||h_k||_2^2=c' ||h_k||_2^2\textrm{, when }k>>1. $$

Note

  1. In this way $||.||_2$ it is a traditional norm plus the condition $||A\cdot x^{T}||\leq ||A||_2\cdot ||x^{T}||_2$. For $A$ given and $x^T$ small enough (where $x=\{x^{(1)},x^{(2)},\ldots,x^{(n)}\}$).

  2. We have $$ S=||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2= $$ $$ =||\sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right)(\overline{e}_j)^T||_2= $$ $$ ||\left( \begin{array}{cc} \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(1)}_k(t)dt\\ \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(2)}_k(t)dt\\ \ldots \\ \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(n)}_k(t)dt \end{array} \right)||_2 $$ Hence from relation $(2)$, we get $$ S=\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+h_kt)||_2\Gamma^{(j)}_{k}dt\right|^2\right)^{1/2} $$

$\endgroup$
16
  • $\begingroup$ Thanks for the response. In (1) $h_k$ shouldn't have transpose? In addition, (2) how is formed? If you apply norm in (1) shouldn't have an inequality? $\endgroup$
    – Thoth
    Commented Jun 24, 2022 at 20:35
  • $\begingroup$ Thanks for the response! When $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ is applied, $A$ is $\nabla^2f (x_* + t h_k)$ which is a matrix and $B$ is $h_k$ which is not a matrix. $B$ shouldn't be a matrix too? In other words, can we apply $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ in this case? $\endgroup$
    – Thoth
    Commented Jun 27, 2022 at 10:55
  • $\begingroup$ @Thoth. $B=h_k$ is also a matrix $n\times 1$ i.e. $h_k=\left(x^{(1)}_{k}-x^{(1)}_{*},x^{(2)}_{k}-x^{(2)}_{*},\ldots,x^{(N)}_k-x^{(N)}_{*}\right)^{T}$. $\endgroup$ Commented Jun 27, 2022 at 16:00
  • $\begingroup$ Thanks for he response. I found it strange because in this case $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ involves both spectral norm and $\ell_2$ norm for vectors but the definition is only about the norm between matices. This way $cos (\theta_k) = \Gamma$ is not $n \times n $ matrix but a $n \times 1$ vector. Am I suspicious without reason? Could you please explain a little? $\endgroup$
    – Thoth
    Commented Jun 27, 2022 at 16:51
  • 1
    $\begingroup$ @Thoth. I have added a note (see Note-(2)) in my proof. If you want to ask something else please feel free to ask. $\endgroup$ Commented Jul 25, 2022 at 9:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .