1
$\begingroup$

Given $f : \mathbb{R}^n \rightarrow \mathbb{R}$ and a sequence $\{ x_k\} \in \mathbb{R}^n$, a sequence $\{ v_k\} \in \mathbb{R}^n$ is said to be gradient related ([1]) if for any subsequence $\{ x_k\}_{k \in \mathcal{K}} $ of $\{ x_k\}$ which converges to a non-critical point (a non-critical point is a point $p \in \mathbb{R}^n$ where $\text{grad} f(p) \ne 0$) of $f$,

$$\limsup_{k \in \mathcal{K}}\langle\text{grad} f(x_k),v_k\rangle < 0$$

Let me present my understanding of this definition, and I'm requesting an evaluation of my understanding.

For my understanding of $\limsup$ I shall rely heavily on the answers to Can someone clearly explain about the lim sup and lim inf?

After choosing $\mathcal{K}$, define $d_i := \langle\text{grad} f(x_i),v_i\rangle$ for $i \in \mathcal{K}$.

$\limsup_i d_i < 0$ which means that after a finite $N$ for all $i>N$, $d_i<0$. This is because $$ \limsup_i d_i = \inf _{n=1,2,3,...}\big(\sup\{d_{n},d_{n+1},d_{n+2},... \}\big)$$ Now if the said condition does not hold after finite $N$ then the inner $\sup$ will always return a positive value and the outer $\inf$ will be at least $0$. (refer https://math.stackexchange.com/a/493529/361497).

What I am confused about is that whether $d_i<0$ for all $i \in \mathcal{K}$?

[1] Definition 4.2.1, Absil, P.-A.; Mahony, R.; Sepulchre, R., Optimization algorithms on matrix manifolds., Princeton, NJ: Princeton University Press

$\endgroup$
0
$\begingroup$

It seems to me that your question is more concerned with the properties of $\limsup$ of a given sequence of real values $\{ d_i\}_{i\in\mathcal{K}}$ than on the specific optimization by gradient descent problem, therefore I focus my answer on this topic. Let's first analyze the properties of the supremum of subsets of the real line $\mathbb{R}$: the starting point is the following, very basic, lemma, stated without its (however very elementary) proof.

Lemma 1 ([1], §I.9, p. 26, Problem 8.3a) Let $S\subset\mathbb{R}$ be a set bounded from above, i.e. it exists a number $\sup S\in \mathbb{R}\iff \sup S\neq\infty$ : then, for each $\epsilon >0$ there exists $x_0\in S$ such that $$ \sup S-\epsilon<x_0\le\sup S.\label{1}\tag{1} $$ By using this lemma, we are able to prove the following important property of supremums of subsets of real numbers:

Lemma 2 ([1], §I.12, p. 38, Problem 12.1a) If $S\subseteq T\subseteq \mathbb{R}$ and $T$ is bounded from above, then $\sup S$ exists and $$ \sup S\le \sup T\label{2}\tag{2} $$ Proof Since $T$ is bounded, there exists at least one real number $l_\mathrm{ub}$ such that $x\le l_\mathrm{ub}$ for all $x\in T$: but since $x\in T$ for each $x\in S$ since $S\subseteq T$, then $x\le l_\mathrm{ub}$ for all $x\in S$ th $S$ is upper bounded and $\sup S\in \mathbb{R}$. To prove \eqref{2} we proceed by contradiction: suppose that $\sup S> \sup T$. By \eqref{1} there exists $x_0\in S$ such that $$ \sup S-\epsilon<x_0\le\sup S\quad\forall \epsilon >0 $$ Now choosing $\epsilon=\sup S-\sup T>0$, we see that there exists $x_0\in S$ and therefore $x_0\in T$ such that $$ \sup S-\epsilon=\sup T < x_0\in T $$ and thus we have reached the sought for contradiction.

We are now ready to apply these results to your problem: define the family of sets $\{D_{\mathcal{K}_n}\}_{n\in\mathbb{N}}$ as $$ D_{\mathcal{K}_n}=\{d_k=\langle\text{grad} f(x_k),v_k\rangle|k\in\mathcal{K}, \;k\ge n\} $$ It is immediate to see that $$ D_{\mathcal{K}_0}\supseteq D_{\mathcal{K}_1}\supseteq D_{\mathcal{K}_2}\supseteq \ldots \supseteq D_{\mathcal{K}_n}\supseteq\dots $$ and this, by lemma 2, implies $$ \sup D_{\mathcal{K}_0}\ge \sup D_{\mathcal{K}_1}\ge \sup D_{\mathcal{K}_2}\ge \ldots \ge \sup D_{\mathcal{K}_n}\ge\dots $$ This implies that $\{\sup D_{\mathcal{K}_n}\}_{n\in\mathbb{N}}$ is a monotonically decreasing sequence of real numbers thus, since $$ \limsup_i d_i=\inf_{n\in\mathbb{N}} \sup D_{\mathcal{K}_n} <0, $$ the supremum of each member of the nested family of set will never return positive if its index is greater than $N$, thus $$ d_i\le \sup D_{\mathcal{K}_n} <0\quad \forall i>N \iff d_i <0 \quad \forall i\in \mathcal{K}, i>N $$

NEW EDIT. After the answer was accepted, having read the comments and the question again, I felt obliged to share some considerations on the concepts of $\limsup$, $\liminf$ and the way they are introduced and studied in several university courses on mathematical analysis.

  • It is costumary to introduce $\limsup$ and $\liminf$ as a byproduct of the $\lim$ definition, usually given in terms of the $\epsilon$-$\delta$ construction. In my opinion, this trend overshades the real importance of such concepts, because

    1. The structure of limits on the real line $\mathbb{R}$ (and perhaps on all euclidean vector/affine spaces $\mathbb{R}^n$, $n\ge 2$) relies more on its order theoretic (i.e. lattice theoretic) structure than on its metric one: this means that $\sup$, $\max$,$\inf$ and $\min$ and the related concepts are of paramount importance, and seeing them though the "glasses" of metric spaces, perhaps helps with later studies in functional analysis but makes more difficult to understand important propositions from real analysis.
    2. For a given sequence $\{a_i\}_{i\in\mathbb{N}}$ $\limsup a_n$ and $\liminf a_n$ always exists due to their monotonic (increasing for $\liminf$, decreasing for $\limsup$) behavior, while it is not always true that $$\limsup a_n=\liminf a_n\iff\lim a_n\text{ exists}.$$ Therefore the most basic concepts are the limit superior and limit inferior of a sequence, while the limit tout court is a sort of byproduct of them: this status is also confirmed by the customary practice in the application of so called direct methods in the calculus of variation.
  • The book [1] of Fischer, despite being affected by many (however non disturbing) typos, analyzes througly the properties of $\limsup$ and $\liminf$ (see chapter 3:"Real sequences and their limits), including the fundamental theorems on their structure that we have implicitly used in this question and in the answer: you can find them in chapter 3, §3.6 pages 110-119. These theorem are so fundamental that they hold in every complete lattice as the algebras of subset of a given set: I found them proved and used also in a fundamental, scarce text on functional analysis authored by Gaetano Fichera (only in Italian, it was never translated).

[1] Emanuel Fischer (1983), "Intermediate Real Analysis", Undergraduate Texts in Mathematics, Berlin-Heidelberg-New York: Springer-Verlag, ISBN 0-387-90721-1, xiv+770, MR681692 (84e:26004), 0506.26002.

$\endgroup$
  • 1
    $\begingroup$ But $d_i < 0$ for all $i \in \mathcal{K}$ is not necessarily true, am I correct? $\endgroup$ – Anant Joshi Nov 4 '18 at 18:33
  • 1
    $\begingroup$ Exactly. There can be a finite number of indexes $i\in\mathcal{K}$ such that $d_i\ge 0$, precisely within the first $N$, where $N$ is the first integer for which $\sup D_{\mathcal{K}_n}<0$. For all the integer greater than that, the relation $d_i< 0$ holds true. $\endgroup$ – Daniele Tampieri Nov 4 '18 at 18:41
  • $\begingroup$ @AnantJoshi. I have added a few considerations on the $\limsup$/$\liminf$ concepts, which I hope will be of some usefulness to you. $\endgroup$ – Daniele Tampieri Nov 6 '18 at 7:43

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.