# Convergence of the Gradient Sampling Algorithm on Directionally Lipschitz
Functions

J. V. Burke<EMAIL_ADDRESS>and  Q. Lin<EMAIL_ADDRESS>
###### Abstract.

The convergence theory for the gradient sampling algorithm is extended to
directionally Lipschitz functions. Although directionally Lipschitz functions
are not necessarily locally Lipschitz, they are almost everywhere
differentiable and well approximated by gradients and so are a natural
candidate for the application of the gradient sampling algorithm. The main
obstacle to this extension is the potential unboundedness or emptiness of the
Clarke subdifferential at points of interest. The convergence analysis we
present provides one path to addressing these issues. In particular, we
recover the usual convergence theory when the function is locally Lipschitz.
Moreover, if the algorithm does not drive a certain measure of criticality to
zero, then the iterates must converge to a point at which either the Clarke
subdifferential is empty or the direction of steepest descent is degenerate in
the sense that it does lie in the interior of the domain of the regular
subderivative.

This paper is dedicated to Terry Rockafellar on the occasion of his 85th
birthday.

###### Key words and phrases:

gradient sampling algorithm and non-Lipschitzian and directionally Lipschitz
and nonsmooth optimization

J. V. Burke, University of Washington, Seattle, WA. Supported in part by the
U.S. National Science Foundation grant DMS-1514559.

Q. Lin, Amazon Corp., 410 Terry Ave N., Seattle, WA.

##  1\. Introduction

The gradient sampling (GS) algorithm is designed to solve non-smooth
optimization problems by using locally sampled gradients to approximate the
Clarke subdifferential and the associated direction of steepest descent. The
objective is assumed to be continuously differentiable on an open set
$\mathcal{D}$ of full measure. Although the method was originally applied to
minimize non-Lipschitzian nonsymmetric spectral functions [4, 5, 6], the
existing convergence theory only applies to locally Lipschitz functions. The
purpose of this note is to extend the convergence theory to directionally
Lipschitz functions (see Definition 1). Directionally Lipschitz functions were
introduced by Rockafellar in [16] and further developed in [17]. Loosely
speaking, a function is directionally Lipschitz at a point ${\bar{x}}$ if it
is possible to “tilt” its epigraph in such a way that the tilted set is the
epigraph of a function that is locally Lipschitz at ${\bar{x}}$. A function
can be directionally Lipschitz at a point but not locally Lipschitz or even
continuous at that point. Some of the ideas for our approach appear in [12]
and are motivated by the results from [3, 6, 7, 11]. In particular, our choice
of directionally Lipschitz functions is inspired by [3, Corollary 6.1] (see
Theorem 3) where it is shown that nearby gradients can be used to approximate
their subdifferential. The primary difficulty in the non-Lipschitzian case is
the potential unboundedness or emptiness of the subdifferential. Indeed, in
this setting, it is not entirely clear what kind of convergence result can
reasonably be expected.

Both our choice of how the algorithm is stated and the consequent convergence
theory closely parallels those proposed by Kiwiel in [11] since his approach
provides the most complete picture in the Lipschitzian case. A nice discussion
of this approach as well as other recent advances and ongoing work is given in
[7]. The paper proceeds as follows. Section 2 is broken into 4 parts: (1)
notation and a review of the subdifferential calculus especially the Clarke
subdifferential and its relationship to the generalized (Mordukhovich or
limiting) subdifferential, (2) pointedness of cones and its use in
approximating the distance to a convex set, (3) the direction of steepest
descent for nonsmooth functions, and (4) an introduction to directionally
Lipschitz functions. In Section 3 we state the version of the gradient
sampling algorithm to be examined and present our convergence results. We
conclude in Section 4 with a few comments on on the algorithm and its
convergence.

##  2\. Preliminaries

###  2.1. Notation

Our notation is based on that used in [14]. We work in the $n$-dimensional
real Euclidean space $\mathbb{R}^{n}$ with the standard inner product
$\left\langle x\,,y\right\rangle$, with $\left\|\cdot\right\|$ denoting the
associated 2-norm whose closed unit ball is
$\mathbb{B}:=\left\\{x\in\mathbb{X}\,\left|\,\left\|x\right\|\leq
1\right.\right\\}$. Given $x\in\mathbb{R}^{n}$, define the open $\epsilon>0$
ball about $x$ as the set
$B_{\epsilon}(x):=\left\\{y\,\left|\,\left\|x-y\right\|<\epsilon\right.\right\\}$.
For $C\subset\mathbb{X}$, denote the closure, interior, and convex hull of $C$
by $\mathrm{cl}\,C,\ {\,\mathrm{int}\,C}$, and ${\mathrm{conv}\,}C$,
respectively. The distance to $C$ is defined by
$\mbox{dist}\left(x\,\left|\,C\right.\right):=\inf_{z\in
C}\left\|x-z\right\|$. The set of natural numbers is denoted by
$\mathbb{N}:=\\{1,2,\dots\\}$. The unit simplex in $\mathbb{R}^{n+1}$ is given
by
${\Delta}_{n}:=\left\\{\lambda\in\mathbb{R}^{n+1}_{+}\,\left|\,\lambda_{1}+\dots+\lambda_{n+1}=1\right.\right\\}$.
Let $\mathbb{R}_{+}$ the set of non-negative reals, and $\mathbb{R}_{++}$ the
set of positive reals.

A set $K\subset\mathbb{R}^{n}$ is said to be a cone if $0\in K$ and $\lambda
x\in K$ for all $x\in K$ and $\lambda\geq 0$. It is said to be a convex cone
if it is both a cone and a convex set. The cone $K\subset\mathbb{R}^{n}$ is
said to be _pointed_ if for all $k\geq 2$ and $x^{1},x^{2},\dots,x^{k}\in K$
one has $x^{1}+x^{2}+\dots+x^{k}=0$ if and only if $x^{i}=0,\ i=1,\dots,k$.

The horizon cone and polar of $C\subset\mathbb{R}^{n}$ are given by

$\displaystyle C^{\infty}$
$\displaystyle:=\left\\{w\,\left|\,\exists\\{x^{k}\\}\subset C,\
t_{k}\downarrow 0\text{ s.t. }t_{k}x^{k}\rightarrow w\right.\right\\}\
\text{and}$ $\displaystyle C^{*}$
$\displaystyle:=\left\\{v\in\mathbb{X}^{*}\,\left|\,\left\langle
v\,,x\right\rangle\leq 1\ \forall,x\in C\right.\right\\},$

respectively. The polar of a set is aways a closed convex set. The convex
indicator and support function for $C$ are give by

$\delta_{C}(x):=\begin{cases}0,&x\in C,\\\ +\infty,&x\notin
C\end{cases}\qquad\text{ and }\qquad\delta_{C}^{*}(v):=\sup_{x\in
C}\left\langle v\,,x\right\rangle\ ,$

respectively.

Given Euclidean spaces $\mathbb{X}$ and $\mathbb{Y}$, a mapping $S$ from
$\mathbb{X}$ to $\mathbb{Y}$ for which $S(x)$ is a subset of $\mathbb{Y}$ for
every $x\in\mathbb{X}$ (possibly empty) is called a multivalued mapping and is
denoted by $S:\,\mathbb{X}\Rightarrow\mathbb{Y}$. The domain of $S$ is the set
$\mathrm{dom}\left(S\right):=\left\\{x\,\left|\,S(x)\neq\emptyset\right.\right\\}$.
Such a mapping $S$ is said to be outer semicontinuous (osc) if

$\left\\{v\,\left|\,\exists\,(x^{k},v^{k})\rightarrow(x,v)\text{ with
}v^{k}\in S(x^{k})\,\forall\,k\right.\right\\}\subset
S(x)\quad\forall\,x\in\mathrm{dom}\left(S\right).$

The graph of $S$ is the set $\mathrm{graph}(S):=\left\\{(x,y)\,\left|\,y\in
S(x)\right.\right\\}$ and the osc hull of $S$ is the multivalued mapping
$\mathrm{cl}\,{S}:\,\mathbb{X}\Rightarrow\mathbb{Y}$ such that
$\mathrm{graph}(\mathrm{cl}\,{S})=\mathrm{cl}\,{\mathrm{graph}(S)}$.

Let
$f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}:=\mathbb{R}\cup\\{+\infty\\}$
and set

$\displaystyle\mathrm{dom}\left(f\right)$
$\displaystyle:=\left\\{x\,\left|\,f(x)<\infty\right.\right\\}$
$\displaystyle\mathrm{epi}{f}$
$\displaystyle:=\left\\{(x,\mu)\,\left|\,f(x)\leq\mu\right.\right\\}\subset\mathbb{R}^{n}\times\mathbb{R}.$

Let ${\bar{x}}\in\mathrm{dom}\left(f\right)$. The _regular subdifferential_ of
$f$ at ${\bar{x}}$ is given by
$\hat{\partial}f(x)\\!\\!:=\\!\\!\left\\{v\,\left|\,f(z)\geq f(x)+\left\langle
v\,,z-x\right\rangle+o(\left\|z-x\right\|)\right.\right\\}$. This set is
always closed and convex, but may be empty. The _subdifferential_ of $f$ at
${\bar{x}}$ is given by

$\partial f({\bar{x}})=\left\\{v\,\left|\,\exists\,x^{k}\rightarrow{\bar{x}},\
v^{k}\rightarrow v\text{ s.t. }v^{k}\in\hat{\partial}f(x^{k})\
\forall\,k\in\mathbb{N}\right.\right\\},$

and the _horizon subdifferential_ of $f$ at ${\bar{x}}$ is given by

(1)
$\partial^{\infty}f({\bar{x}}):=\left\\{v\,\left|\,\begin{array}[]{c}\exists\,x^{k}\rightarrow{\bar{x}},\
t_{k}\downarrow 0,\ t_{k}v^{k}\rightarrow v,\text{ s.t. }\\\
v^{k}\in\hat{\partial}f(x^{k})\
\forall\,k\in\mathbb{N}\end{array}\right.\right\\}.$

These sets are always closed, and if $f$ is lsc at ${\bar{x}}$ then either
$\partial f({\bar{x}})\neq\emptyset$ or $\partial^{\infty}f({\bar{x}})$
contains at least one nonzero element [14, Corollary 8.10]. These
subdifferentials are all mutivalued mappings with $\partial f$ and
$\partial^{\infty}f$ osc along $f$-attentive sequences by construction (an
$f$-attentive sequence is any sequence
$\\{x^{k}\\}\subset\mathrm{dom}\left(f\right)$ such that if
$x^{k}\rightarrow{\bar{x}}$ then $f(x^{k})\rightarrow f({\bar{x}})$). Given
$\epsilon>0$ define

$\bar{\partial}_{\epsilon}f({\bar{x}}):=\left\\{v\,\left|\,v\in\bar{\partial}f(x)\text{
for some }x\in{\bar{x}}+\epsilon\mathbb{B}\right.\right\\}$

to be the $\epsilon$-approximate subgradients of $f$ at ${\bar{x}}$.

Given a closed nonempty set $C\subset\mathbb{R}^{n}$ and a point ${\bar{x}}\in
C$, the regular normal cone to $C$ at ${\bar{x}}$ is the set

$\widehat{N}_{C}({\bar{x}}):=\left\\{v\,\left|\,\left\langle
v\,,x-{\bar{x}}\right\rangle\leq o(\left\|x-{\bar{x}}\right\|)\text{ for }x\in
C\right.\right\\}.$

The osc hull of this multivalued mapping is called the normal cone mapping and
is denoted by $N_{C}({\bar{x}})$. The _Clarke normal cone_ to $C$ a $x$ is
given by ${\bar{N}_{C}(x)}:=\mathrm{cl}\,{\mathrm{conv}\,}N_{C}({\bar{x}})$.
The cone of _regular_ tangents to $C$ at a point $x\in C$ where $C$ is locally
closed is $\widehat{T}_{C}(x):=N_{C}(x)^{*}$ [14, Theorem 6.28].

Given
$f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}:=\mathbb{R}\cup\\{+\infty\\}$
and ${\bar{x}}\in\mathrm{dom}\left(f\right)$ at which $f$ is lsc, the _Clarke
subdifferential_ of $f$ at ${\bar{x}}$ is
$\bar{\partial}f(x)\\!\\!:=\\!\\!\left\\{v\,\left|\,(v,-1)\in\bar{N}_{\mathrm{epi}{f}}(x,f(x))\right.\right\\}$,
and
${\bar{\partial}^{\infty}}f(x)\\!\\!:=\\!\\!\left\\{v\,\left|\,(v,0)\in\bar{N}_{\mathrm{epi}{f}}(x,f(x))\right.\right\\}$
is the _Clarke horizon subdifferential_ of $f$ at ${\bar{x}}$ [14, Theorem
8.49]. The subdifferential and the Clarke subdifferential reduce to the usual
subdifferential in convex analysis when $f$ is convex. Finally, the regular
subderivative of $f$ at $x\in\mathrm{dom}\left(f\right)$, denoted
$\hat{d}f(x):\,\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{\pm\infty\\}$, at
points where $f$ is lsc is defined by the relation
$\mathrm{epi}(\hat{d}f(x))=\widehat{T}_{\mathrm{epi}{f}}(x,f(x))$ [14, Theorem
8.17]. The regular subderivative coincides with Clarke’s directional
derivative when $f$ is locally Lipschitz [10]. The following theorem
establishes the relationships between the subdifferential and the Clarke
subdifferential.

######  Theorem 1 (Subdifferential Relationships).

[14, Theorem 8.49 and Exercise 8.23] Let
$f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ be locally lsc and finite-valued at
${\bar{x}}\in\mathbb{R}^{n}$. Then the following hold:

  1. (1)

$\partial f(x)$ and $\partial^{\infty}f(x)$ are osc at ${\bar{x}}$ with
respect to $f-$attentive convergence, that is, with respect to sequences
$\\{x^{k}\\}\subset\mathrm{dom}\left(f\right)$ such that
$(x^{k},f(x^{k}))\rightarrow(x,f(x))$.

  2. (2)

$\bar{\partial}f({\bar{x}})$ is a closed convex set and
${\bar{\partial}^{\infty}}f({\bar{x}})$ is a closed convex cone.

  3. (3)

${\bar{\partial}^{\infty}}f({\bar{x}})=\bar{\partial}f({\bar{x}})^{\infty}$
when $\bar{\partial}f({\bar{x}})\neq\emptyset$, or equivalently, $\partial
f({\bar{x}})\neq\emptyset$.

  4. (4)

If the cone $\partial^{\infty}f({\bar{x}})$ is pointed (or equivalently,
${\bar{\partial}^{\infty}}f({\bar{x}})$ is pointed), then

$\bar{\partial}f({\bar{x}})={\mathrm{conv}\,}\partial
f({\bar{x}})+{\mathrm{conv}\,}\partial^{\infty}f({\bar{x}})\ \mbox{ and }\
{\bar{\partial}^{\infty}}f({\bar{x}})={\mathrm{conv}\,}\partial^{\infty}f({\bar{x}}).$

Moreover, if $\bar{\partial}f({\bar{x}})\neq\emptyset$ (equivalently,
$\partial f({\bar{x}})\neq\emptyset$), then
$\hat{d}f(x)=\delta^{*}_{\bar{\partial}f(x)}.$

###  2.2. Pointedness

We review pointedness and a few of its properties.

######  Lemma 1.

Let $K$ be a non-empty closed cone in $\mathbb{R}^{n}$ and consider the
following statements:

  1. (i)

$K$ is pointed.

  2. (ii)

$K\cap(-K)=\\{0\\}$.

  3. (iii)

${\,\mathrm{int}\,K}^{*}\neq\emptyset$.

Statements (i) and (ii) are equivalent, and if $K$ is convex, both are
equivalent to (iii). Moreover, in the convex case,
$z\in{\,\mathrm{int}\,K}^{*}$ if and only if there exist $\epsilon>0$ such
that $\left\langle z\,,w\right\rangle\leq-\epsilon\left\|w\right\|$ for all
$w\in K$.

###### Proof.

The statements concerning (i)-(iii) follow from [14, Proposition 3.14,
Exercise 6.22]. Therefore, we need only establish the the final statement of
the lemma. Let $z\in{\,\mathrm{int}\,K}^{*}$ and $\epsilon>0$ be such that
$z+\epsilon\mathbb{B}\subset K^{*}$. Then, for all $w\in K$ and
$u\in\mathbb{B}$, $0\geq\left\langle z+\epsilon
u\,,w\right\rangle=\left\langle z\,,w\right\rangle+\epsilon\left\langle
u\,,w\right\rangle.$ Hence, $0\geq\left\langle
z\,,w\right\rangle+\epsilon\sup_{u\in\mathbb{B}}\left\langle
u\,,w\right\rangle=\left\langle z\,,w\right\rangle+\epsilon\left\|w\right\|$.

On the other hand, if there is a $z\in\mathbb{R}^{n}$ and $\epsilon>0$ is such
that $\left\langle z\,,w\right\rangle\leq-\epsilon\left\|w\right\|$ for all
$w\in K$, then, for all $u\in\mathbb{B}$ and $w\in K$, $\left\langle
z+\frac{\epsilon}{2}u\,,w\right\rangle\leq-\epsilon\left\|w\right\|+\frac{\epsilon}{2}\left\|w\right\|=-\frac{\epsilon}{2}\left\|w\right\|$
so that $z\in{\,\mathrm{int}\,K}^{*}$. ∎

We now connect the pointedness of $C^{\infty}$ to projections and the distance
function for a non-empty closed convex set. This result extends lemma [11,
Lemma 3.1] and introduces a condition that is key to our analysis of the non-
Lipschitzian setting.

######  Lemma 2 (Pointedness, and Projections).

Let $C$ be a non-empty closed convex subset of $\mathbb{R}^{n}$ such that
$C^{\infty}$ is pointed. Let $z\notin C$ be such that

(2) $z-\mathrm{proj}_{C}\,(z)\in{\,\mathrm{int}\,(}C^{\infty})^{*}\ .$

Then, for all $\beta\in(0,1)$, there is a $\delta>0$ such that if $u,v\in C$
with
$\left\|z-u\right\|\leq\mbox{dist}\left(z\,\left|\,C\right.\right)+\delta$,
then $\left\langle z-v\,,z-u\right\rangle>\beta\left\|z-u\right\|^{2}$. In
particular, if $z=0$, then $\left\langle
v\,,u\right\rangle>\beta\left\|u\right\|^{2}$ whenever $u,v\in C$ and $u$
satisfies
$\left\|u\right\|\leq\mbox{dist}\left(0\,\left|\,C\right.\right)+\delta$.

###### Proof.

Let $\beta\in(0,1)$. If the result were false, there exist a sequence
$\\{(u^{k},v^{k})\\}\subset C\times C$ with
$\left\|z-u^{k}\right\|\leq\mbox{dist}\left(z\,\left|\,C\right.\right)+1/k$
such that

(3) $\left\langle
z-v^{k}\,,z-u^{k}\right\rangle\leq\beta\left\|z-u^{k}\right\|^{2}\quad\forall\,k.$

Since $\\{u^{k}\\}$ is bounded we can assume with no loss of generality that
$u^{k}\rightarrow\mathrm{proj}_{C}\,(z)$. The projection theorem tells us that

$\left\langle
v-\mathrm{proj}_{C}\,(z)\,,z-\mathrm{proj}_{C}\,(z)\right\rangle\leq
0\quad\forall\,v\in C,$

or equivalently,

(4) $\mbox{dist}\left(z\,\left|\,C\right.\right)^{2}\leq\left\langle
z-v\,,z-\mathrm{proj}_{C}\,(z)\right\rangle\quad\forall\,v\in C.$

If $\\{v^{i}\\}$ has a bounded subsequence, we can again assume with no loss
in generality that $v^{i}\rightarrow{\bar{v}}\in C$. Then, by (3),
$\left\langle
z-{\bar{v}}\,,z-\mathrm{proj}_{C}\,(z)\right\rangle\leq\beta\mbox{dist}\left(z\,\left|\,C\right.\right)^{2}$
which contradicts (4) since $\beta\in(0,1)$ and
$\mbox{dist}\left(z\,\left|\,C\right.\right)>0$. Hence, the sequence
$\\{v^{i}\\}$ is divergent. Consequently, we can assume, with no loss in
generality, that $v^{i}/\left\|v^{i}\right\|\rightarrow{\bar{v}}\in
C^{\infty}$ with $\left\|{\bar{v}}\right\|=1$. Dividing (3) by
$\left\|v^{i}\right\|$ and taking the limit yields
$\left\langle{\bar{v}}\,,z-\mathrm{proj}_{C}\,(z)\right\rangle\geq 0$. But
${\bar{v}}\in C^{\infty}$ and
$z-\mathrm{proj}_{C}\,(z)\in{\,\mathrm{int}\,(}C^{\infty})^{*}$, so, by Lemma
1, there is an $\epsilon>0$ such that
$\left\langle{\bar{v}}\,,z-\mathrm{proj}_{C}\,(z)\right\rangle\leq-\epsilon\left\|{\bar{v}}\right\|$.
This contradiction establishes the result. ∎

Condition (2) plays a central role in our analysis of the GS algorithm. The
following lemma gives insight into this condition by describing properties of
the horizon cone $C^{\infty}$ and its polar.

######  Lemma 3 (Normal, Barrier, and Horizon Cones).

[8, Lemma 5] Let $C$ be a non-empty closed convex set and define
$K:=\bigcup_{x\in C}N_{C}(x)$. Then $\mathrm{ri}\,{\mathrm{bar}\,C}\subset
K\subset\mathrm{bar}\,C$, and

$\mathrm{cl}\,K=\mathrm{cl}\,{\mathrm{bar}\,C}=(C^{\infty})^{*}\ \mbox{ and }\
C^{\infty}=(\mathrm{bar}\,C)^{*},$

where $\mathrm{bar}\,C:=\mathrm{dom}\left(\sigma_{C}\right)$ is called the
barrier cone of $C$.

Recall that it is always the case that $z-\mathrm{proj}_{C}\,(z)\in
N_{C}\left(\mathrm{proj}_{C}\,(z)\right)$, and so, by Lemma 3, we have

$z-\mathrm{proj}_{C}\,(z)\in
N_{C}\left(\mathrm{proj}_{C}\,(z)\right)\subset\mathrm{cl}\,{\bigcup_{x\in
C}N_{C}(x)}=(C^{\infty})^{*}.$

In particular, if $C$ is bounded, then $(C^{\infty})^{*}=\mathbb{R}^{n}$ so
condition (2) is trivially satisfied. Intuitively, the “smaller” the horizon
cone of $C$ the more “likely” condition (2) is satisfied.

###  2.3. Steepest Descent Directions

In the smooth setting the direction of steepest decent is given by the
direction of unit length that minimizes the directional derivative. By
contrast, in the nonsmooth setting there are several notions of directional
derivative to choose from. From a numerical perspective, the most useful
permit a dual representation as the support function of an associated
subdifferential which in turn yields a dual representation of the direction of
steepest descent via the Minimum Norm Duality Theorem, e.g. see [9, Theorem
2.8].

Since our analysis uses the Clarke subdifferential, our direction of steepest
descent is based on the regular subderivative (see Theorem 1). That is, the
direction of steepest descent for $f$ at $x$ is given by

(5) ${\bar{d}}_{x}:=\mathop{\rm arg\,min}_{\left\|x\right\|\leq
1}\hat{d}f(x)(d)\ .$

The dual to this optimization problem is given by the Minimum Norm Duality
Theorem.

######  Theorem 2 (Minimum Norm Duality Theorem).

[13] Let $\mathbb{X}$ be a normed linear space with norm
$\left\|\cdot\right\|$ and dual norm $\left\|\cdot\right\|_{*}$, and let
$\mathbb{B}$ denote the closed unit ball in $\mathbb{X}$. Given a nonempty
closed convex set $C\subset\mathbb{X}^{*}$ and ${\bar{z}}\in\mathbb{X}^{*}$
with ${\bar{z}}\notin C$, we have

(6) $\text{dist}_{*}({\bar{z}}\mid C)=\sup_{\left\|v\right\|\leq
1}[\left\langle v\,,{\bar{z}}\right\rangle-\delta^{*}_{C}(v)],$

where $\delta_{C}$ is the convex indicator of $C$ and $f^{*}$ denotes the
convex conjugate of a function $f$. In particular, if ${\bar{z}}=0$, then

$\inf_{\left\|v\right\|\leq 1}\delta^{*}_{C}(v)=-\text{dist}_{*}(0\mid C).$

The Projection Theorem for convex sets tells us that for a nonempty closed
convex set $C$ and any ${\bar{z}}\in\mathbb{X}$ there is a unique vector
${\hat{z}}\in C$ such that
$\mbox{dist}\left({\bar{z}}\,\left|\,C\right.\right)=\left\|{\bar{z}}-{\hat{z}}\right\|$,
where ${\hat{z}}$ is characterized by the condition that
${\bar{z}}-{\hat{z}}\in N_{C}({\hat{z}})$. The vector ${\hat{z}}$ is called
the projection of ${\bar{z}}$ onto $C$ and is denoted by
$\mathrm{proj}_{C}\,({\bar{z}})$. This implies that
${\bar{v}}:=\frac{({\bar{z}}-\mathrm{proj}_{C}\,({\bar{z}}))}{\left\|{\bar{z}}-\mathrm{proj}_{C}\,({\bar{z}})\right\|}$
is the unique solution to the supremum problem in (6). By taking
$C=\bar{\partial}f(x)$, we obtain a dual interpretation for the direction of
steepest descent.

######  Corollary 1 (Steepest Descent Duality).

[9, Theorem 2.8] Let $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$x\in\mathrm{dom}\left(\partial f\right)$ be such that $f$ is lsc at $x$. Then

(7) $\inf_{\left\|d\right\|\leq
1}\hat{d}f(x)(d)=-\mbox{dist}\left(0\,\left|\,\bar{\partial}f(x)\right.\right),$

and the vector ${\bar{d}}_{x}$ in (5) is given by
${\bar{d}}_{x}=-\mathrm{proj}_{\bar{\partial}f(x)}\,({\bar{z}})/\left\|\mathrm{proj}_{\bar{\partial}f(x)}\,({\bar{z}})\right\|$.

###### Proof.

By Theorem 1, $\bar{\partial}f(x)$ is a nonempty closed convex set with
$\hat{d}f(x)=\delta^{*}_{\bar{\partial}f(x)}$. The corollary follows by taking
$C=\bar{\partial}f(x)$ and ${\bar{z}}=0$ in Theorem 2. ∎

###  2.4. Directionally Lipschitz Functions and Subdifferential Approximation

Rockafellar builds the notion of a directionally Lipschitzian function on that
of epi-Lipschitzian sets [15]. He then establishes a useful characterization
of directionally Lipschitzian functions through horizon subgradients [16]. We
circumvent the epi-Lipschitzian construction and instead use the
characterization given in [14, Exercise 9.42] as our definition.

######  Definition 1 (Directionally Lipschitzian Functions).

Suppose $f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ is finite at
$x\in\mathbb{R}^{n}$. We say $f$ is directionally Lipschitz at $x$ if there is
a unit vector $u$ and scalars $\epsilon>0$ and $M\in\mathbb{R}$ such that

$\frac{f(z+tv)-f(z)}{t}\leq M\quad\forall\,v\in B_{\epsilon}(u),\,z\in
B_{\epsilon}(x),f(z)\in B_{\epsilon}(f(x)),\,t\in(0,\epsilon].$

We say that $f$ is directionally Lipschitz if it is directionally Lipschitz at
every point of $\mathbb{R}^{n}$.

A simple characterization of directionally Lipschitz functions is obtained
through the pointedness of the horizon cone of the subdifferential.

######  Lemma 4.

[14, Exercise 9.42(b)] A function
$f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ finite at $x\in\mathbb{R}^{n}$
is directionally Lipschitz at $x$ if and only if $f$ is locally lsc at $x$ and
the horizon subdifferential $\partial^{\infty}f(x)$ is pointed.

In particular, locally Lipschitz functions are directionally Lipschitz. In
[14, Exercize 9.42(c)], Rockafellar and Wets show that a function
$f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ that is finite and locally lsc
at ${\bar{x}}$ is directionally Lipschitz at ${\bar{x}}$ if there is a convex
cone $K\subset\mathbb{R}^{n}$ having nonempty interior such that $f$ is
$K$-nonincreasing, i.e. $f(x+w)\leq f(x)$ for all $x\in\mathbb{R}^{n}$ and
$w\in K$. In [2, Theorem 6], it is shown that if
${\,\mathrm{int}\,K}\neq\emptyset$, then $K$-monotone functions
($K$-nonincreasing or $K$-nondecreasing) are continuous and almost every where
differentiable. These authors also establish the following characterization of
continuous directionally Lipschitz functions in terms of monotonicity.

######  Proposition 1.

[2, Proposition 8] A continuous function
$f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ is directionally Lipschitz at
$x$ if an only if it is locally representable near $x$ as $f=g+l$ where $g$ is
monotone with respect to a convex cone with interior and $l$ is linear.

The pointedness of $\partial^{\infty}f(x)$, or equivalently,
${\bar{\partial}^{\infty}}f(x)$, is also related to the continuity of the
regular subderivative $\hat{d}f(x)$.

######  Lemma 5 (Continuity of $\hat{d}f(x)$).

Suppose $f:\,\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ is finite at
$x\in\mathbb{R}^{n}$ with $\partial f({\bar{x}})\neq\emptyset$, then
$\hat{d}f(x)$ is continuous on

${\,\mathrm{int}\,[}({\bar{\partial}^{\infty}}f({\bar{x}}))^{*}]={\,\mathrm{int}\,\left[\mathrm{dom}\left(\hat{d}f({\bar{x}})(\cdot)\right)\right]}.$

###### Proof.

By Theorem 1, Lemma 3 and the closure properties of convex sets, we have

$\displaystyle{\,\mathrm{int}\,[}({\bar{\partial}^{\infty}}f({\bar{x}}))^{*}]$
$\displaystyle={\,\mathrm{int}\,[}(\bar{\partial}f({\bar{x}})^{\infty})^{*}]={\,\mathrm{int}\,[}\mathrm{cl}\,{\mathrm{bar}\,\bar{\partial}f({\bar{x}})}]$
$\displaystyle={\,\mathrm{int}\,[}\mathrm{bar}\,\bar{\partial}f({\bar{x}})]={\,\mathrm{int}\,[}\mathrm{dom}\left(\delta^{*}_{\bar{\partial}f({\bar{x}})}\right)]$
$\displaystyle={\,\mathrm{int}\,\left[\mathrm{dom}\left(\hat{d}f({\bar{x}})(\cdot)\right)\right]}.$

Since $\hat{d}f({\bar{x}})$ is convex, it is continuous on the interior of its
domain. ∎

In general, directionally Lipschitzian functions need not be locally Lipschitz
or even continuous at ${\bar{x}}$. For example, for every $\eta\geq 0$, the
function

(8) $f(x):=\begin{cases}x^{1/3}-\eta,&x\leq 0,\\\
x^{1/3}+\eta,&x>0,\end{cases}$

is directionally Lipschitz at ${\bar{x}}=0$ and continuous at ${\bar{x}}=0$ if
and only if $\eta=0$. Nonetheless, in [3, Corollary 6.1] it is shown that when
$\partial^{\infty}f(x)$ is pointed, then $\bar{\partial}f(x)$ can be locally
approximated by nearby gradients. We offer a slight improvement of this result
that is useful to our discussion. We begin with the following technical lemma.

######  Lemma 6 (Limits of Gradients).

Let $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
${\bar{x}}\in\mathrm{dom}\left(f\right)$ be such that,
$\partial^{\infty}f({\bar{x}})$ is pointed, $f$ is continuous on an open set
$\mathcal{V}$ containing ${\bar{x}}$ and differentiable on an open set
$\mathcal{Q}\subset\mathcal{V}$ of full measure in $\mathcal{V}$. For each
$x\in\mathcal{V}$ and $\delta>0$ such that
${\bar{x}}+\delta\mathbb{B}\subset\mathcal{V}$ set

(9) $G_{\delta}(x):={\mbox{cl\\! conv}\,}{\nabla f((x+\delta
I\\!\\!B)\cap\mathcal{Q})}.$

Let $x^{k}\rightarrow{\bar{x}}$ and $\delta_{k}\downarrow 0$ with
$x^{k}+\delta_{k}\mathbb{B}\subset\mathcal{V}$ for all $k\in\mathbb{N}$.

  1. (a)

If $w^{k}\rightarrow{\bar{w}}$ with $w^{k}\in G_{\delta_{k}}(x^{k})$ for all
$k\in\mathbb{N}$, then ${\bar{w}}\in\bar{\partial}f({\bar{x}})$.

  2. (b)

If $v^{k}\rightarrow{\bar{v}}$ with $v^{k}\in G_{\delta_{k}}(x^{k})^{\infty}$
for all $k\in\mathbb{N}$, then
${\bar{v}}\in{\bar{\partial}^{\infty}}f({\bar{x}})$.

###### Proof.

We only show (b) since the proof of (a) follows the same pattern but is
significantly simpler. By Carathéodory’s Theorem, for each $k\in\mathbb{N}$,
there exist sequences
$\\{(x^{kj1},\dots,x^{kj(n+1)})\,\mid\,j\in\mathbb{N}\\}\subset\mathop{\mathsf{X}}_{i=1}^{n+1}\mathbb{R}^{n},\
\\{\alpha^{kj}\in{\Delta}_{n}\,\mid\,j\in\mathbb{N}\\}$, and
$\\{t_{kj}\,\mid\,j\in\mathbb{N}\\}\subset\mathbb{R}_{+}$ such that
$t_{kj}\downarrow_{j}0$,
$x^{kji}\in({\bar{x}}+\delta_{k}I\\!\\!B)\cap\mathcal{Q}\
((j,i)\in\mathbb{N}\times\\{1,2,...,n+1\\})$, and
$t_{kj}\sum_{i=1}^{n+1}\alpha^{kj}_{i}\nabla
f(x^{kji})\overset{j}{\rightarrow}v^{k}$. Choose $\epsilon_{k}\downarrow 0$.
For each $k\in\mathbb{N}$, let $j_{k}\in\mathbb{N}$ be such that
$t_{kj_{k}}<\epsilon_{k}$ and
$\left\|v^{k}-t_{kj_{k}}\sum_{i=1}^{n+1}\alpha^{kj_{k}}_{i}\nabla
f(x^{kj_{k}i})\right\|\leq\epsilon_{k}$. For each $k\in\mathbb{N}$, set
$({\bar{x}}^{k1},\dots,{\bar{x}}^{k(n+1)}):=(x^{kj_{k}1},\dots,x^{kj_{k}(n+1)})$,
${\bar{\alpha}}^{k}:=\alpha^{kj_{k}}$ and ${\bar{t}}_{k}=t_{kj_{k}}$ so that
$({\bar{x}}^{k1},\dots,{\bar{x}}^{k(n+1)})\rightarrow({\bar{x}},\dots,{\bar{x}})$,
${\bar{t}}_{k}\downarrow 0$, and
${\bar{t}}_{k}\sum_{i=1}^{n+1}{\bar{\alpha}}^{k}_{i}\nabla
f({\bar{x}}^{ki})\rightarrow v$. By compactness, we can assume that
${\bar{\alpha}}^{k}\rightarrow{\bar{\alpha}}\in{\Delta}_{n}$.

Let us first suppose that the sequence $\\{{\bar{t}}_{k}(\nabla
f({\bar{x}}^{k1},\dots,\nabla f({\bar{x}}^{k(n+1)}))\\}$ is unbounded. If
$\nu_{k}$ denotes the norm of the $k$th member of this sequence, we can assume
that $\nu_{k}\uparrow\infty$. Then, with no loss in generality, there exists
$(w^{1},\dots,w^{(n+1)})$ such that

$(\tilde{t}_{k1}\nabla f({\bar{x}}^{k1}),\dots,\tilde{t}_{k(n+1)}\nabla
f({\bar{x}}^{k(n+1)}))\rightarrow(w^{1},\dots,w^{(n+1)})\neq(0,\dots,0),$

where $\tilde{t}_{ki}:=({\bar{t}}_{k}{\bar{\alpha}}^{k}_{i})/\nu_{k}$ for
$i=1,\dots,(n+1)$ and $k\in\mathbb{N}$. Since $\tilde{t}_{ki}\downarrow 0$ and
$\nabla f({\bar{x}}^{ki})\in\hat{\partial}f({\bar{x}}^{ki})$ for
$i=1,\dots,n+1$ and $k\in\mathbb{N}$, we have
$w^{i}\in\partial^{\infty}f({\bar{x}})$ for $i=1,\dots,(n+1)$ (see (1)). But
then $0=\sum_{i=1}w^{i}$ with $(w^{1},\dots,w^{(n+1)})\neq(0,\dots,0)$ which
contradicts the pointedness of $\partial^{\infty}f({\bar{x}})$.
Hence we can assume that the sequence $\\{{\bar{t}}_{k}(\nabla
f({\bar{x}}^{k1}),\dots,\nabla f({\bar{x}}^{k(n+1)}))\\}$ is bounded.
Therefore, we may assume that there exist
$w^{i}\in\partial^{\infty}f({\bar{x}})$ such that ${\bar{t}}_{k}\nabla
f({\bar{x}}^{ki})\rightarrow w^{i}$ for $i=1,\dots,(n+1)$. Consequently, by
Theorem 1,
$v=\sum_{i=1}^{n+1}{\bar{\alpha}}_{i}w^{i}\in{\mathrm{conv}\,}\partial^{\infty}f({\bar{x}})={\bar{\partial}^{\infty}}f({\bar{x}})$
proving the result. ∎

The outer semi-continuity of $\partial f$ and $\partial^{\infty}f$ along
$f$-attentive sequences [14, Proposition 8.7] implies that pointedness is a
local property and that the pointedness of $\partial^{\infty}f$ and
$G_{\delta}$ are related.

######  Lemma 7 (Pointedness of $\partial^{\infty}f(x)$ is a local property).

Let $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ be continuous near
${\bar{x}}\in\mathbb{R}^{n}$, and suppose $\partial^{\infty}f({\bar{x}})$ is
pointed. Let $\mathcal{Q}$ be a full measure subset of a neighborhood of
${\bar{x}}$ consisting of points where $f$ is differentiable, and let
$G_{\delta}(x)$ be as in (9). Then the following statements hold.

  1. (i)

There is an $\epsilon>0$ such that $\partial^{\infty}f(x)$ is pointed on
$({\bar{x}}+\epsilon\mathbb{B})\cap\mathrm{dom}\left(f\right)$.

  2. (ii)

There is a ${\bar{\delta}}>0$ such that $G_{\delta}({\bar{x}})^{\infty}$ is
pointed for all $\delta\in(0,{\bar{\delta}}]$.

  3. (iii)

There exist $\epsilon,\ {\bar{\delta}}>0$ such that both
$\partial^{\infty}f(x)$ and $G_{\delta}(x)^{\infty}$ are pointed for all
$x\in{\bar{x}}+\epsilon\mathbb{B}$ and $0<\delta<{\bar{\delta}}$.

###### Proof.

The statements (i)-(iii) are proved in essentially the manner. Therefore we
only prove (iii). If the result is false, then there exist sequences
$\\{x^{k}\\}\subset\mathrm{dom}\left(\partial f\right)$ with
$x^{k}\rightarrow{\bar{x}}$ and $\delta_{k}\downarrow 0$ such that either
$\partial^{\infty}f(x^{k})$ is not pointed for all $k=1,2,\dots$ or
$G_{\delta_{k}}(x^{k})^{\infty}$ is not pointed for all $k=1,2,\dots$. Let us
first suppose that the cone $\partial^{\infty}f(x^{k})$ is not pointed for all
$k=1,2,\dots$. Then there exist $v^{k1},\,v^{k2}\in\partial^{\infty}f(x^{k})$
such that $v^{k1}+v^{k2}=0$ and
$\left\|v^{k1}\right\|+\left\|v^{k2}\right\|=1$ for all $k$. Compactness and
the osc of $\partial^{\infty}f$ at ${\bar{x}}$ (Theorem 1) tells us that we
can also assume there exist
${\bar{v}}^{1},{\bar{v}}^{2}\in\partial^{\infty}f({\bar{x}})$ with
$(v^{k1},v^{k2})\rightarrow({\bar{v}}^{1},{\bar{v}}^{2})$,
${\bar{v}}^{1}+{\bar{v}}^{2}=0$ and
$\left\|v^{1}\right\|+\left\|v^{2}\right\|=1$. But this contradicts the
pointedness of $\partial^{\infty}f({\bar{x}})$. Next suppose that the cone
$G_{\delta_{k}}(x^{k})^{\infty}$ is not pointed for all $k=1,2,\dots$. Again,
there exist $v^{k1},\,v^{k2}\in G_{\delta_{k}}(x^{k})^{\infty}$ such that
$v^{k1}+v^{k2}=0$ and $\left\|v^{k1}\right\|+\left\|v^{k2}\right\|=1$ for all
$k\in\mathbb{N}$. Compactness tells us that we can assume there exist
${\bar{v}}^{1},{\bar{v}}^{2}$ with
$(v^{k1},v^{k2})\rightarrow({\bar{v}}^{1},{\bar{v}}^{2})$,
${\bar{v}}^{1}+{\bar{v}}^{2}=0$ and
$\left\|v^{1}\right\|+\left\|v^{2}\right\|=1$. But Lemma 6(b) tells us that
$v^{1},v^{2}\in{\bar{\partial}^{\infty}}f({\bar{x}})$ which contradicts the
pointedness of ${\bar{\partial}^{\infty}}f({\bar{x}})$. ∎

In the next lemma we establish a relationship between regular subgradients and
gradients at near by points. The lemma extracts a portion of the proof of [3,
Theorem 5.2] which we will use to extend [3, Corollary 6.1].

######  Lemma 8 (Gradients and Regular Subgradients).

Let $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ be continuous on
$B_{\delta}({\bar{x}})$ for ${\bar{x}}\in\mathbb{R}^{n}$ and $\delta>0$, and
assume that $\mathcal{Q}$ is a full measure subset of $B_{\delta}({\bar{x}})$
consisting of points where $f$ is differentiable. If either $f$ is absolutely
continuous on line segments in $B_{\delta}({\bar{x}})$ or $\mathcal{Q}$ is
open and $f$ is continuously differentiable on $\mathcal{Q}$, then
$\hat{\partial}f({\bar{x}})\subset G_{\delta}({\bar{x}}).$

###### Proof.

If $f$ is absolutely continuous on line segments in $B_{\delta}({\bar{x}})$,
the result is the first statement established in the proof of [3, Theorem
5.2]. If $\mathcal{Q}$ is open and $f$ is continuously differentiable on
$\mathcal{Q}$, the result requires only a very small change to this proof.

If $y\notin G_{\delta}({\bar{x}})$, the separation theorem tells us that there
exists a non-zero vector $z$ and $k\in\mathbb{R}$ such that

$\left\langle y\,,z\right\rangle>k\ \text{but}\ \left\langle\nabla
f(x)\,,z\right\rangle\leq k\
\forall\,x\in\mathcal{Q}\cap({\bar{x}}+\delta\mathbb{B}).$

If $y\in\hat{\partial}f({\bar{x}})$, then $f(x+tz)\geq
f({\bar{x}})+t\left\langle y\,,z\right\rangle+o(t)$. Let $\bar{t}>0$ be such
that $t\left\langle y\,,z\right\rangle+o(t)>kt$ for all $t\in(0,\bar{t}]$ so
that $f({\bar{x}}+tz)>f({\bar{x}})+k\bar{t}$ for all $t\in(0,\bar{t})$. By
continuity, given $t\in(0,\bar{t})$, for all points $w$ sufficiently close to
${\bar{x}}$, $f(w+\bar{t}z)>f(w)+k\bar{t}$. Hence, we can choose
$\bar{w}\in\mathcal{Q}$ and $\hat{t}\in(0,\bar{t})$ so that

(10) $w+sz\in\mathcal{Q}\cap({\bar{x}}+(\delta/2)\mathbb{B})\
\forall\,s\in(0,\hat{t}]\ \ \text{with}\ \ f(w+\hat{t}z)>f(w)+k\hat{t}.$

Now consider the function $g:\,[0,\hat{t}]\rightarrow\mathbb{R}$ defined by
$g(s):=f(w+sz)$. By construction $g$ is continuously differentiable on
$(0,\hat{t})$ with $g^{\prime}(s)=\left\langle\nabla
f(w+sz)\,,z\right\rangle\leq k$. Therefore, by the Fundamental Theorem of
Calculus, $f(w+\hat{t}z)=g(\hat{t})\leq g(0)+k\hat{t}=f(w)+k\hat{t}$ which
contradicts (10). ∎

######  Theorem 3 (Subdifferential Approximation).

Suppose that, close to ${\bar{x}}\in\mathbb{R}^{n}$, the function
$f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ is continuous and absolutely
continuous on line segments, with $\partial^{\infty}f({\bar{x}})$ pointed. If
$\mathcal{Q}$ is a full measure subset of a neighborhood of ${\bar{x}}$
consisting of points where $f$ is differentiable, then

$\bar{\partial}f({\bar{x}})=\bigcap_{\delta>0}G_{\delta}({\bar{x}})\quad\text{and}\quad\bar{\partial}^{\infty}f({\bar{x}})=\bigcap_{\delta>0}G_{\delta}({\bar{x}})^{\infty}.$

Moreover, if $\mathcal{Q}$ is open with $f$ continuously differentiable on
$\mathcal{Q}$, then the requirement that $f$ be absolutely continuous on line
segments can be dropped.

###### Proof.

The statement of the theorem differs in two respects from the result given in
[3, Corollary 6.1]. First, the result in [3] makes no mention of the case when
$\mathcal{Q}$ is open, and, second, there is no formula for the horizon cone
equivalence. The case when $\mathcal{Q}$ is open follows from Lemma 8 since
the lemma tells us that the implication in [3, Theorem 5.2] follows from this
hypothesis. Consequently, [3, Corollary 6.1] follows from this hypothesis as
well.

We now prove the horizon cone equivalence. By Lemma 8, for all small
$\delta>0$, $\hat{\partial}f(x)\subset G_{\delta/2}(x)\subset
G_{\delta}({\bar{x}})$ for all $x\in B_{\delta/2}({\bar{x}})$. Hence
$\partial^{\infty}f({\bar{x}})\subset G_{\delta}({\bar{x}})^{\infty}$, and so,
by Theorem 1(4), $\bar{\partial}^{\infty}f({\bar{x}})\subset
G_{\delta}({\bar{x}})^{\infty}$ for all small $\delta>0$. Consequently,
$\bar{\partial}^{\infty}f({\bar{x}})\subset\bigcap_{\delta>0}G_{\delta}({\bar{x}})^{\infty}$.
For the reverse inclusion let
$v\in\bigcap_{\delta>0}G_{\delta}({\bar{x}})^{\infty}$. Then there exist
sequences $\delta_{k}\downarrow 0$ and $v^{k}\rightarrow v$ such that
$v^{k}\in G_{\delta_{k}}({\bar{x}})^{\infty}$ for all $k\in\mathbb{N}$. By
Lemma 6(b), $v\in{\bar{\partial}^{\infty}}f({\bar{x}})$ which proves the
result. ∎

The next lemma establishes a key property of approximate directions of
steepest descent for directionally Lipschitz functions and extends the content
of [11, Lemma 3.1] to these functions.

######  Lemma 9 (Approximate Directions of Steepest Descent).

Let ${\bar{x}}\in\mathbb{R}^{n}$ be such that
$f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ is differentiable on a full measure
subset $\mathcal{Q}$ of an open convex neighborhood $\mathcal{N}$ of
${\bar{x}}$. Further suppose that $f$ is either continuous and absolutely
continuous along line segments in $\mathcal{N}$ or that $\mathcal{Q}$ is open.
If

(11) $0\not\in\bar{\partial}f({\bar{x}}),\
\emptyset\neq\bar{\partial}f({\bar{x}}),\mbox{ and
}-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)\in{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f({\bar{x}}))^{*},$

then, for all $\beta\in(0,1)$, there exists $\delta>0$ and $\eta>0$ such that
$0\notin G_{\eta}({\bar{x}})$ and, for every $u,v\in G_{\eta}({\bar{x}})$ with
$\left\|u\right\|\leq\mbox{dist}\left(0\,\left|\,G_{\eta}({\bar{x}})\right.\right)+\delta$,
we have $\left\langle v\,,u\right\rangle>\beta\left\|u\right\|^{2}$.

###### Proof.

Since $0\not\in\bar{\partial}f({\bar{x}})$, Theorem 3 tells us that there is
an $\bar{\eta}>0$ such that $0\notin G_{\eta}({\bar{x}})$ for all
$\eta\in(0,\bar{\eta}]$. Theorem 3 also tells us that
$\bar{\partial}f({\bar{x}})\subset G_{\eta}({\bar{x}})$ for all $\eta\geq 0$.
Therefore,
$\mbox{dist}\left(0\,\left|\,G_{\eta}({\bar{x}})\right.\right)\leq\mbox{dist}\left(0\,\left|\,\bar{\partial}f({\bar{x}})\right.\right)<\infty$
for all $\eta\geq 0$.

We suppose the result is false and establish a contradiction. Since the result
is false, there exist ${\hat{\beta}}\in(0,1)$ and sequences
$\\{(u^{i},v^{i})\\}$ in $\mathbb{R}^{2n}$ and $\\{(\eta_{i},\delta_{i})\\}$
in $\mathbb{R}^{2}_{+}$ with $\eta_{i}\downarrow 0$ and $\delta_{i}\downarrow
0$ such that, for all $i\in\mathbb{N}$,

(12)
$u^{i},v^{i}\\!\in\\!G_{\eta_{i}}({\bar{x}}),\,\left\|u^{i}\right\|\\!\leq\\!\mbox{dist}\left(0\\!\,\left|\,\\!G_{\eta_{i}}({\bar{x}})\\!\right.\right)+\delta_{i}\text{
and}\,\left\langle
v^{i}\,,u^{i}\right\rangle\\!\leq\\!{\hat{\beta}}\left\|u^{i}\right\|^{2}.$

Since $\\{\left\|u^{i}\right\|\\}$ is bounded by
$\mbox{dist}\left(0\,\left|\,\bar{\partial}f({\bar{x}})\right.\right)+\delta_{0}$,
we may assume that $u^{i}\rightarrow{\bar{u}}$, where
${\bar{u}}\in\bar{\partial}f({\bar{x}})$ by Lemma 6. Theorem 3 tells us that
$\bar{\partial}f({\bar{x}})\subset G_{\eta_{i}}({\bar{x}})$ for all
$i\in\mathbb{N}$. Hence, for all $i$ large,
$\left\|u^{i}\right\|\leq\mbox{dist}\left(0\,\left|\,\bar{\partial}f({\bar{x}})\right.\right)+\delta_{i}.$
Therefore, ${\bar{u}}=\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)$ and so
$-{\bar{u}}\in{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f({\bar{x}}))^{*}$
by (11).

Next consider the sequence $\\{v^{i}\\}$. If this sequence is bounded, then,
again, Lemma 6 tells us that, with no loss in generality, there is a
${\bar{v}}\in\bar{\partial}f({\bar{x}})$ such that
$v^{i}\rightarrow{\bar{v}}$. The projection theorem for convex sets tells us
that
$\left\langle{\bar{v}}\,,{\bar{u}}\right\rangle\geq\left\|{\bar{u}}\right\|^{2}$,
but, by construction,
$\left\langle{\bar{v}}\,,{\bar{u}}\right\rangle\leq{\hat{\beta}}\left\|{\bar{u}}\right\|^{2}<\left\|{\bar{u}}\right\|^{2}$.
This contradiction implies that the sequence $\\{v^{i}\\}$ is unbounded.
Therefore, with no loss in generality, $\\{v^{i}\\}$ is divergent. By
Carathéodory’s Theorem, there exists $\lambda^{i}\in{\Delta}_{n}$ and
$x^{ij}\in G_{\eta_{i}}({\bar{x}})$ such that
$v^{i}=\sum_{j=1}^{n+1}\lambda_{ij}\nabla f(x^{ij})$ for all $i$. Since the
sequence $\\{v^{i}\\}$ is divergent, the sequence defined by
${\hat{g}}_{i}:=(\lambda_{i1}\nabla f(x^{i1}),\dots,\lambda_{i(n+1)}\nabla
f(x^{i(n+1)}))$ must also be divergent, and so, again with no loss in
generality, there is a $({\bar{g}}^{1},\dots,{\bar{g}}^{n+1})$ such that
${\hat{g}}_{i}/\left\|{\hat{g}}_{i}\right\|\rightarrow({\bar{g}}^{1},\dots,{\bar{g}}^{n+1})\neq
0$, where we have taken
$\left\|{\hat{g}}_{i}\right\|:=\max_{j=1,\dots,n+1}\lambda_{ij}\left\|\nabla
f(x^{ij})\right\|$. Theorem 1 tells us that
${\bar{g}}^{j}\in\partial^{\infty}f({\bar{x}}),\,j=1,\dots,n+1$. Clearly,
$\left\|v^{i}\right\|\leq\left\|{\hat{g}}_{i}\right\|$ for all $i=1,2,\dots$.
If $\\{v^{i}/\left\|{\hat{g}}_{i}\right\|\\}$ has a subsequence convergent to
zero, then taking the limit along this subsequence yields
$\sum_{j=1}^{n+1}{\bar{g}}^{j}=0$ which contradicts the fact that
$\partial^{\infty}f({\bar{x}})$ is pointed. So we can assume that
$v^{i}/\left\|{\hat{g}}_{i}\right\|=\sum_{j=1}^{n+1}\lambda^{i}_{j}\nabla
f(x^{ij})/\left\|{\hat{g}}_{i}\right\|\rightarrow{\tilde{v}}\in\partial^{\infty}f({\bar{x}})\setminus\\{0\\}$.
Theorem 1 tells us that
${\tilde{v}}\in{\bar{\partial}^{\infty}}f({\bar{x}})=\bar{\partial}f({\bar{x}})^{\infty}$.
But
$-{\bar{u}}\in{\,\mathrm{int}\,(}\bar{\partial}f({\bar{x}})^{\infty})^{*}$,
so, by Lemma 1, $\left\langle{\tilde{v}}\,,{\bar{u}}\right\rangle>0$ while
$\left\langle{\tilde{v}}\,,{\bar{u}}\right\rangle\leq 0$ by (12). This final
contradiction establishes the result. ∎

The condition
$-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)\in{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f({\bar{x}}))^{*}$
in (11) plays an important role in our analysis. Although examples where it
fails to hold are easily generated, such points are _degenerate_ in the sense
that the direction of steepest descent for the regular subderivative does not
lie in the interior of its domain (see Lemma 5). Further discussion of this
issue is given in our concluding remarks.

######  Example 1.

Let $h:\,\mathbb{R}^{2}\rightarrow\mathbb{R}$ be given by $h(x):=\left\langle
y\,,x\right\rangle+[\mbox{dist}\left(x\,\left|\,\mathbb{R}^{2}_{+}\right.\right)]^{1/2}$,
where $y:=(-1,\beta)^{T}$. Then $\bar{\partial}h(0)=y+\mathbb{R}^{2}_{-},\
({\bar{\partial}^{\infty}}h(0))^{*}=\mathbb{R}^{2}_{+}$ and

$-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)=\begin{cases}(1,0)^{T}\not\in{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f(0))^{*}&,\
\beta\geq 0,\\\
(1,-\beta)\in{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f(0))^{*}&,\
\beta<0.\end{cases}$

##  3\. The Gradient Sampling Algorithm

Assume that $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfies the following
hypotheses:

$\mathcal{H}$: $f$ is continuous on $\mathbb{R}^{n}$ and continuously
differentiable
on an open full measure set $\mathcal{D}\subset\mathbb{R}^{n}$.

We use the form of the gradient sampling algorithm given in [7] based on the
version proposed by Kiwiel in [11].

The GS Algorithm (Gradient Sampling Algorithm)

Initialization: Let $x^{0}$ be a point at which $f$ is differentiable, choose
termination tolerances
$(\epsilon_{opt},\nu_{opt})\in[0,\infty)\times[0,\infty)$ and the initial
sampling radius $\epsilon_{0}\in(\epsilon_{opt},\infty)$, initial stationarity
target $\nu_{0}\in[\nu_{opt},\infty)$, sample size $m\geq n+1$, line search
parameters $(\beta,\gamma)\in(0,1)\times(0,1)$, and reduction factors
$(\theta_{\epsilon},\theta_{\nu})\in(0,1]\times(0,1]$

For $k\in\mathcal{N}$ do

  1. (i)

Independently sample $\\{x^{k,1},\dots,x^{k,m}\\}$ uniformly from
$x^{k}+\epsilon_{k}\mathbb{B}$.

  2. (ii)

Terminate the algorithm if
$\\{x^{k,1},\dots,x^{k,m}\\}\not\subset\mathcal{D}$.

  3. (iii)

Compute $g^{k}$ as the solution of
$\min_{g\in\mathcal{G}^{k}}\text{\small$\frac{1}{2}$}\|g\|^{2}$, where

$\mathcal{G}^{k}:={\mathrm{conv}\,}\\{\nabla f(x^{k}),\nabla
f(x^{k,1}),\dots,\nabla f(x^{k,m})\\}.$

  4. (iv)

If $\nabla f(x^{k})=0$ or ($\|g^{k}\|_{2}\leq\nu_{opt}$ and
$\epsilon_{k}\leq\epsilon_{opt}$), then terminate.

  5. (v)

If $\|g^{k}\|_{2}\leq\nu_{k}$

  6. (vi)

then set $\nu_{k+1}\leftarrow\theta_{\nu}\nu_{k}$,
$\epsilon_{k+1}\leftarrow\theta_{\epsilon}\epsilon_{k}$, and $t_{k}\leftarrow
0$

  7. (vii)

else set $\nu_{k+1}\leftarrow\nu_{k}$, $\epsilon_{k+1}\leftarrow\epsilon_{k}$,
$d^{k}\leftarrow-g^{k}/\left\|g^{k}\right\|$, and

(13) $\qquad\qquad
t_{k}\leftarrow\max\left\\{t\in\\{1,\gamma,\gamma^{2},\dots\\}:f(x^{k}+td^{k})<f(x^{k})-\beta
t\|g^{k}\|\right\\}.$

  8. (viii)

If $f$ is differentiable at $x^{k}+t_{k}d^{k}$

  9. (ix)

then set $x^{k+1}\leftarrow x^{k}+t_{k}d^{k}$

  10. (x)

else set $x^{k+1}$ randomly as any point where $f$ is

  11. differentiable and such that

$\begin{aligned} &f(x^{k+1})<f(x^{k})-\beta t_{k}\|g^{k}\|\ \ \text{and}\\\ &\
\|x^{k}+t_{k}d^{k}-x^{k+1}\|_{2}\leq\min\\{t_{k},\epsilon_{k}\\}\end{aligned}\
.$

End for

######  Remark 1.

As shown in [6, Page 756], the line search (13) in the algorithm is finitely
terminating when $\nabla f(x^{k})\neq 0$.

######  Remark 2.

In [11, Section 4.1] it is observed that one can also take $d^{k}$ to be the
un-normalized direction $-g^{k}$ when $f$ is Lipschitz. However, the argument
in [11] explicitly depends on $f$ being Lipschitz continuous. In the non-
Lipschitzian case, our proof of convergence requires the normalized direction
in the statement of the GS algorithm given above.

###  3.1. Convergence

We now introduce the key tools in analyzing the GS algorithm introduced in
[6]: for $\epsilon,\delta>0$ and ${\bar{x}},x\in\mathbb{R}^{n}$, let

(14)
$\rho_{\epsilon}(x):=\mbox{dist}\left(0\,\left|\,G_{\epsilon}(x)\right.\right)$

and set

$\displaystyle\mathcal{D}_{\epsilon}^{m}(x)$
$\displaystyle:=\prod_{1}^{m}((x+\epsilon\mathbb{B})\cap\mathcal{D})\subset\mathbb{R}^{n}\qquad\text{and}$
$\displaystyle V_{\epsilon}({\bar{x}},x,\delta)$
$\displaystyle:=\\!\\!\left\\{\\!(y^{1},y^{2},\dots,y^{m})\\!\\!\in\\!\mathcal{D}_{\epsilon}^{m}(x)\\!\\!\,\left|\,\\!\text{dist}(0\\!\mid\\!{\mathrm{conv}\,}\\!\\{\nabla
f(y^{i})\\}_{i=1}^{m})\\!\\!\leq\\!\\!\rho_{\epsilon}({\bar{x}})\\!\\!+\\!\\!\delta\\!\right.\right\\},$

where $m\geq n+1$ is as given in the statement of Algorithm I.

The next lemma shows that the convex hull of a collection of gradients can be
used to obtain directions of approximate steepest descent.

######  Lemma 10.

[6, Lemma 3.2(i)] [11, Lemma 3.2(i)] Let $\epsilon>0$ and
${\bar{x}}\in\mathbb{R}^{n}$. For all $\delta>0$ there is a $\tau>0$ and a
non-empty open set ${\bar{V}}$ such that ${\bar{V}}\subset
V_{\epsilon}({\bar{x}},x,\delta)$ for all $x\in B_{\tau}({\bar{x}})$ with
$\mbox{dist}\left(0\,\left|\,{\mathrm{conv}\,}\\{\nabla
f(y^{i})\\}_{i=1}^{m}\right.\right)\leq\rho_{\epsilon}({\bar{x}})+\delta$ for
all $(y^{1},\dots,y^{m})\in{\bar{V}}$.

######  Remark 3.

The statement of this lemma parallels the form given in [11, Lemma 3.2(i)]
rather than the form given in [6, Lemma 3.2(i)]. Essentially the same proof is
given in both papers and follows from the continuity of $\nabla f$ on
$\mathcal{D}$.

We make use of the following mean value theorem to provide a lower bound on
the step sizes $t_{k}$ in step (vi) of the GS algorithm when $0\notin\partial
f(x)$.

######  Theorem 4 (Approximate Mean Value Theorem).

[1, Theorem 3.4.7] Let $\varphi:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ be lsc
and assume that $r\in\mathbb{R}$ and $x,y\in\mathbb{R}^{n}$ are such that
$x\neq y$, $\varphi(x)<+\infty$, and $r<\varphi(y)-\varphi(x)$. Then there is
a ${\hat{x}}\in[x,y)$ such that for all $\epsilon>0$ there exists
$({\tilde{x}},\varphi({\tilde{x}}))\in
B_{\epsilon}(({\hat{x}},\varphi({\hat{x}})))$ and
${\tilde{v}}\in\hat{\partial}\varphi({\tilde{x}})$ for which

$\left\langle{\tilde{v}}\,,{\hat{x}}-{\tilde{x}}\right\rangle>-\epsilon,\ \
\left\langle{\tilde{v}}\,,y-x\right\rangle>r,\ \mbox{ and }\
\varphi({\tilde{x}})\leq\varphi(x)+|r|+\epsilon.$

######  Lemma 11 (Stepsize Bound).

Let $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ be such that $\mathcal{H}$
holds. Let $\beta,\gamma\in(0,1)$ be given, and let
${\bar{x}}\in\mathbb{R}^{n}$ be such that all three conditions in (11) hold.
Then there exist $\eta>0$ and $\delta>0$ so that the consequences of Lemma 9
hold. Moreover, given $\epsilon>0$, we can choose $\tau\in(0,\epsilon/3)$ so
that the consequences of Lemma 10 hold for this $\delta$. That is, there
exists a non-empty open set ${\bar{V}}$ such that ${\bar{V}}\subset
V_{\epsilon}({\bar{x}},x,\delta)$ for all $x\in B_{\tau}({\bar{x}})$ with
$\mbox{dist}\left(0\,\left|\,{\mathrm{conv}\,}\\{\nabla
f(y^{i})\\}_{i=1}^{m}\right.\right)\leq\rho_{\epsilon}({\bar{x}})+\delta$ for
all $(y^{1},\dots,y^{m})\in{\bar{V}}$. Then, for all $x\in
B_{\tau}({\bar{x}})$ and $(x^{1},\dots,x^{m})\in{\bar{V}}$,

(15)
${\bar{t}}\\!:=\\!\min\\{1,\gamma\epsilon/3\\}\\!\leq\\!{\hat{t}}\\!:=\\!\max\left\\{t\,\left|\,\begin{aligned}
&f(x+td)\\!<\\!f(x)-\beta t\left\|g\right\|\\\
&t\in\\{1,\gamma,\gamma^{2},\dots\\}\end{aligned}\right.\right\\},$

where $g:=\mathop{\rm
arg\,min}\left\\{\left\|v\right\|\,\left|\,v\in{\mathrm{conv}\,}\\{\nabla
f(x^{i})\\}_{i=1}^{m}\\}\right.\right\\}$ and $d:=-g/\left\|g\right\|$.

###### Proof.

Since the hypotheses of Lemmas 9 and 10 are satisfied, the parameters
$\eta,\,\delta$ and $\tau$ can be chosen as required. Set
$\widehat{G}:={\mathrm{conv}\,}\\!\\{\nabla f(x^{i})\\}_{i=1}^{m}$. Since
$(x^{1},\dots,x^{m})\\!\in\\!{\bar{V}}\\!\subset\\!V_{\epsilon}({\bar{x}},{\bar{x}},\delta)$,
Lemma 10 tells us that
$\mbox{dist}\left(0\,\left|\,\widehat{G}\right.\right)\leq\rho_{\epsilon}({\bar{x}})+\delta$
and $\widehat{G}\subset G_{\epsilon}({\bar{x}})$. Hence, $g\in
G_{\epsilon}({\bar{x}})$ and
$\left\|g\right\|\leq\rho_{\epsilon}({\bar{x}})+\delta$. Consequently, Lemma 9
tells us that

(16) $\left\langle v\,,g\right\rangle>\beta\left\|g\right\|^{2}\quad\forall\
v\in G_{\epsilon}({\bar{x}}).$

Assume to the contrary that the inequality (15) is false. Then ${\hat{t}}<1$
and so

$-\beta\gamma^{-1}{\hat{t}}\left\|g\right\|\leq
f(x+\gamma^{-1}{\hat{t}}d)-f(x).$

By taking $f=\varphi$, $x=x,\ y=x+\gamma^{-1}{\hat{t}}d$ and
$r=-\beta\gamma^{-1}{\hat{t}}\left\|g\right\|$ in Theorem 4, there exists
${\hat{x}}\in[x,\,x+\gamma^{-1}{\hat{t}}d)$ such that for all
${\tilde{\epsilon}}>0$ there exists $({\tilde{x}},f({\tilde{x}}))\in
B_{\epsilon}({\hat{x}},f({\hat{x}}))$ and
${\tilde{v}}\in\hat{\partial}f({\tilde{x}})$ such that

$-\beta\gamma^{-1}{\hat{t}}\left\|g\right\|<\gamma^{-1}{\hat{t}}\left\langle{\tilde{v}}\,,d\right\rangle,$

or equivalently,

$\left\langle{\tilde{v}}\,,g\right\rangle<\beta\left\|g\right\|^{2}.$

So ${\tilde{v}}\notin G_{\epsilon}({\bar{x}})$ by (16). Assume that we have
chosen ${\tilde{\epsilon}}\in(0,\epsilon/3)$. Since the inequality (15) is
false, ${\hat{t}}<\gamma\epsilon/3$ or equivalently,
$\gamma^{-1}{\hat{t}}\left\|d\right\|<\epsilon/3$. Consequently,
${\tilde{x}}\in B_{\epsilon}({\bar{x}})$ and $\partial f({\tilde{x}})\subset
G_{\epsilon}({\bar{x}})$. Therefore,
${\tilde{v}}\in\hat{\partial}f({\tilde{x}})\subset\partial
f({\tilde{x}})\subset G_{\epsilon}({\bar{x}})$. This contradiction establishes
the result. ∎

The main convergence result for the GS Algorithm now follows. Our proof is
inspired by Kiwiel’s proof of [11, Theorem 3.3].

######  Theorem 5 (Convergence: $0=\nu_{opt}=\epsilon_{opt}$).

Suppose $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfies $\mathcal{H}$. Let
$\\{x^{k}\\}$ be a sequence generated by the GS Algorithm with
$\nu_{0},\,\epsilon_{0}\in\mathbb{R}_{++}$,
$\theta_{\epsilon},\,\theta_{\nu}\in(0,1)$, and $\epsilon_{opt}=\nu_{opt}=0$.
With probability 1 the algorithm does not terminate in line (ii) and one of
the following must occur:

  1. (a)

There is a $k_{0}\in\mathbb{N}$ such that $\nabla f(x^{k_{0}})=0$ and the
algorithm terminates.

  2. (b)

$f(x^{k})\downarrow-\infty$.

  3. (c)

$0<\bar{\nu}:=\inf_{k}\nu_{k}$ and the sequence converges to some
${\bar{x}}\in\mathbb{R}^{n}$ for which at least one of the three conditions in
(11) must be violated, that is, either

(17) $\emptyset=\bar{\partial}f({\bar{x}}),\quad
0\in\bar{\partial}f({\bar{x}}),\quad\text{ or
}-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)\notin{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f({\bar{x}}))^{*}.$

  4. (d)

$\nu_{k}\downarrow 0$ and every cluster point ${\bar{x}}$ of $\\{x^{k}\\}$ (if
one exists) satisfies $0\in\bar{\partial}f({\bar{x}})$.

Moreover, if $f$ is locally Lipschitz, then outcome (c) cannot occur.

###### Proof.

If $f$ is locally Lipschitz, then the result follows from [11, Theorem 3.3].
The assumptions on the function $f$ imply that, with probability 1, the
algorithm does not terminate in line (ii) of the GS Algorithm, so we assume
$\\{x^{k,1},\dots,x^{k,m}\\}\subset\mathcal{D}$ for all $k$. We also assume
that neither (a) nor (b) occur and show that either (c) or (d) must occur. Let
$J\subset\mathbb{N}$ be those iterations for which $x^{k}\neq x^{k+1}$.
Observe that if $J$ is finite with maximum value $k_{0}$, then $\nabla
f(x^{k_{0}})=0$, hence, $J$ is infinite. Since

$f(x^{k+1})\leq f(x^{k})-\beta
t_{k}\left\|g^{k}\right\|\quad\forall\,k\in\mathbb{N},$

the sequence $\\{f(x^{k})\\}$ is non-increasing and bounded below, and so has
has a limit ${\tilde{f}}$. Summing this inequality over $k$ and taking the
limit tells us that

(18)
$\beta\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|\left\|g^{k}\right\|\leq\beta\sum_{k=1}^{\infty}t_{k}\left\|g^{k}\right\|\leq
f(x^{0})-{\tilde{f}}<\infty,$

where the first inequality follows from lines (viii)-(x) of the GS algorithm.
In particular,
$\left\|x^{k+1}-x^{k}\right\|\left\|g^{k}\right\|{\rightarrow}0$. We decompose
this fact into two mutually exclusive possibilities: either
$0<\bar{\nu}:=\inf_{k}\nu_{k}$ or $\nu_{k}\downarrow 0$.

Let us first suppose that $0<\bar{\nu}:=\inf_{k}\nu_{k}$. By lines (v) and
(vi) of the algorithm, $0<\bar{\epsilon}:=\inf_{k}\epsilon_{k}$ and
$\bar{\nu}\leq\inf_{k\in J}\left\|g^{k}\right\|$. Therefore, (18) tells us
that $\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|<\infty$ and
$t_{k}\downarrow 0$. In particular, this implies that the sequence
$\\{x^{k}\\}$ is Cauchy, and so there exists ${\bar{x}}$ such that
$x^{k}\rightarrow{\bar{x}}$. Assume to the contrary that none of the
conditions in (17) hold, or equivalently, the hypotheses of Lemma 11 (11) hold
at ${\bar{x}}$. Let $\epsilon,\,\eta,\,\delta,\,\tau\in\mathbb{R}_{++}$ and
${\bar{V}}\subset\mathbb{R}^{n}$ be an open set satisfying the conditions of
Lemma 11. We may assume that $\tau<\inf_{k}\epsilon_{k}$. Since for all $k$
sufficiently large $t_{k}<\gamma\epsilon/3$, we must have
$(x^{k1},\dots,x^{km})\notin{\bar{V}}$ for all large $k$. But since
${\bar{V}}$ is open, the probability of this event is zero. Hence, with
probability 1, Lemma 11 tells us that at least one of the three conditions in
(11) must hold, that is, (c) is satisfied.

Finally, suppose that $\nu_{k}\downarrow 0$. By line (vi) of the algorithm,
$\epsilon_{k}\downarrow 0$. Let ${\bar{x}}$ be a cluster point of the sequence
$\\{x^{k}\\}$. If there is any subsequence ${\widehat{J}}\subset\mathbb{N}$
such that

(19) $x^{k}\overset{{\widehat{J}}}{\rightarrow}{\bar{x}}\ \text{ and }\
\left\|g^{k}\right\|\overset{{\widehat{J}}}{\rightarrow}0,$

then $0\in\bar{\partial}f({\bar{x}})$ by Lemma 6. Therefore, we assume that no
such subsequence exists and establish a contradiction. In particular, this
implies that $x^{k}\not\rightarrow{\bar{x}}$. Since no subsequence satisfies
(19), there exist ${\bar{\nu}}>0$ such that if
$\left\|x^{k}-{\bar{x}}\right\|\leq{\bar{\nu}}$, then
$\left\|g^{k}\right\|>{\bar{\nu}}$; otherwise, there exists
${\widehat{J}}\subset\mathbb{N}$ and
${\bar{\nu}}_{k}\downarrow_{\widehat{J}}0$ and such that
$\left\|x^{k}-{\bar{x}}\right\|\leq{\bar{\nu}}_{k}$ and
$\left\|g^{k}\right\|\leq{\bar{\nu}}_{k}$ for all $k\in{\widehat{J}}$ which
implies that ${\widehat{J}}$ satisfies (19), a contradiction. Since
${\bar{x}}$ is a cluster point, the set
$K:=\left\\{k\,\left|\,\left\|x^{k}-{\bar{x}}\right\|\leq\bar{\nu}\right.\right\\}$
is infinite with $\left\|g^{k}\right\|>\bar{\nu}$ for all $k\in K$. Since
$x^{k}\not\rightarrow{\bar{x}}$, we can reduce $\bar{\nu}$ if necessary so
that the set $\mathbb{N}\setminus K$ is infinite. Observe that inequality (18)
tell us that $\sum_{k\in K}\left\|x^{k}-{\bar{x}}\right\|<\infty$. Let
${\widehat{K}}:=\left\\{k\,\left|\,\left\|x^{k}-{\bar{x}}\right\|\leq\bar{\nu}/3\right.\right\\}$.
Again ${\widehat{K}}$ is infinite since ${\bar{x}}$ is a cluster point of
$\\{x^{k}\\}$. Both $K$ and ${\widehat{K}}\subset K$ define subsequences of
$\\{x^{k}\\}$. Since $\mathbb{N}\setminus K$ is infinite, for each
$k\in{\widehat{K}}$ there is an ${\hat{k}}>k$ such that ${\hat{k}}\notin K$
but $x^{i}\in K$ for $k\leq i<{\hat{k}}$. By construction,
$\left\|x^{\hat{k}}-x^{k}\right\|\geq\bar{\nu}/3$ for all $k\in{\widehat{K}}$;
otherwise, $x^{\hat{k}}\in K$, a contradiction. By the triangle inequality, we
have
$\bar{\nu}/3\leq\left\|x^{\hat{k}}-x^{k}\right\|\leq\sum_{i=k}^{{\hat{k}}-1}\left\|x^{i+1}-x^{i}\right\|$
for all $k\in{\widehat{K}}$. But $\sum_{k\in
K}\left\|x^{k}-{\bar{x}}\right\|<\infty$ and ${\widehat{K}}\subset K$ so that
$\sum_{i=k}^{{\hat{k}}-1}\left\|x^{i+1}-x^{i}\right\|\overset{{\widehat{K}}}{\rightarrow}0$.
This contradiction implies that our assumption that there is no subsequence
satisfying (19) is false. That is, $0\in\bar{\partial}f({\bar{x}})$. ∎

In the Lipschitzian case, Theorem 5 differs from [11, Theorem 3.3] with the
introduction of possible outcome (c). Kiwiel’s proof of [11, Theorem 3.3]
shows that the case $0<\bar{\nu}:=\inf_{k}\nu_{k}$ does not occur if $f$ is
locally Lipschitz continuous. The absence of the case (c) requires that
$\bar{\partial}f$ is an osc, compact, convex valued operator whose domain is
all of $\mathbb{R}^{n}$, in particular, it requires that $f$ be locally
Lipschitz. On the other hand, if $f$ is not locally Lipschitz, then
$\bar{\partial}f$ is not locally bounded and possibly empty at some points.
These possibilities are reflected in the outcome (c), and only in (c). This
does not imply that $\bar{\partial}f({\bar{x}})$ is bounded in outcome (d),
but outcome (d) does require that $\bar{\partial}f({\bar{x}})$ be nonempty.
Note that outcome (c) signals why $\nu_{k}$ is not reduced to zero. These
observations are reviewed in our final comments. We conclude this section by
stating two corollaries that describe the behavior of the algorithm under
standard variations in the choice of of initial parameters.

######  Corollary 2 (Convergence: $0<\epsilon_{opt},\ 0<\nu_{opt}$).

Suppose $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfies $\mathcal{H}$. Let
$\\{x^{k}\\}$ be a sequence generated by the GS Algorithm with
$\nu_{0},\,\epsilon_{0}\in\mathbb{R}_{++}$,
$\theta_{\epsilon},\,\theta_{\nu}\in(0,1)$ and $0<\epsilon_{opt},\
0<\nu_{opt}$. With probability 1 the algorithm does not terminate in line (ii)
and one of the following must occur:

  1. (a)

There is a $k_{0}\in\mathbb{N}$ such that
$\mbox{dist}\left(0\,\left|\,\bar{\partial}_{\epsilon_{opt}}f(x^{k_{0}})\right.\right)\leq\nu_{opt}$
and the algorithm terminates.

  2. (b)

$f(x^{k})\downarrow-\infty$.

  3. (c)

$\nu_{opt}<\bar{\nu}:=\inf_{k}\nu_{k}$ and the sequence converges to some
${\bar{x}}\in\mathbb{R}^{n}$ at which at least one of the three statements in
(17) is true.

###### Proof.

By assumption the algorithm does not terminate in line (ii) of the GS
Algorithm with probability 1, so we assume
$\\{x^{k,1},\dots,x^{k,m}\\}\subset\mathcal{D}$ for all $k$. Next we assume
that neither (a) nor (b) occur and show that (c) must occur. Since (a) does
not occur and $\nabla f(x^{k})\in\bar{\partial}_{\epsilon_{k}}f(x^{k})$, the
algorithm does not terminate in step (iv) and step (v) of the algorithm occurs
at most finitely many times. Therefore,
$\nu_{opt}<\bar{\nu}:=\inf_{k}\nu_{k}$, the algorithm does not terminate and
the sequence $\\{x^{k}\\}$ is infinite. Consequently, Theorem 5 tells us that
(c) must occur and the final statement of the corollary follows. ∎

######  Corollary 3 (Convergence:
$0\\!<\\!\epsilon_{opt}\\!=\\!\epsilon_{0},\,0\\!=\\!\nu_{opt}\\!=\\!\nu_{0}$).

Suppose $f:\,\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfies $\mathcal{H}$. Let
$\\{x^{k}\\}$ be a sequence generated by the GS Algorithm with
$\nu_{opt}=\nu_{0}=0$, $\epsilon_{opt}=\epsilon_{0}>0$ and $0=\theta_{\nu},\
1=\theta_{\epsilon}$. Let $J\subset\mathbb{N}$ be those iterations for which
$x^{k}\neq x^{k+1}$. With probability 1 the algorithm does not terminate in
line (ii) and one of the following must occur:

  1. (a)

The algorithm terminates at some iteration $k_{0}\in\mathbb{N}$ with either
$\nabla f(x^{k_{0}})=0$ or $g^{k_{0}}=0$, and consequently
$0\in\bar{\partial}_{\epsilon_{opt}}f(x^{k_{0}})$.

  2. (b)

$f(x^{k})\downarrow-\infty$.

  3. (c)

The sequence $\\{x^{k}\\}$ is infinite with $\inf_{k\in
J}\left\|g^{k}\right\|>0$ in which case there exists
${\bar{x}}\in\mathbb{R}^{n}$ such that $x^{k}\rightarrow{\bar{x}}$ and at
least one of the conditions in (11) is satisfied.

  4. (d)

The sequence $\\{x^{k}\\}$ is infinite with $\inf_{k\in
J}\left\|g^{k}\right\|=0$ in which case every cluster point ${\bar{x}}$ of
$\\{x^{k}\\}$ (if one exists) satisfies $0\in\bar{\partial}f({\bar{x}})$.

###### Proof.

The proof strategy follows that of the Theorem 5. By assumption the algorithm
does not terminate in line (ii) of the GS Algorithm with probability 1, so we
assume $\\{x^{k,1},\dots,x^{k,m}\\}\subset\mathcal{D}$ for all $k$. We also
assume that neither (a) nor (b) occur and show that either (c) or (d) must
occur. Observe that if $J$ is finite with maximum value $k_{0}$, then, by step
(iv) of the algorithm, (a) occurs, hence, $J$ is infinite. Following the proof
of Theorem 5, we have that (18) holds. We analyze the two mutually exclusive
possible outcomes $\inf_{k\in J}\left\|g^{k}\right\|>0$ and $\inf_{k\in
J}\left\|g^{k}\right\|=0$ separately.

First suppose that ${\bar{\nu}}:=\inf_{k\in J}\left\|g^{k}\right\|>0$. By
(18), the sequence $\\{x^{k}\\}$ is Cauchy so that $x^{k}\rightarrow{\bar{x}}$
for some ${\bar{x}}\in\mathbb{R}^{n}$. The argument used in Theorem 5 applies
to show that one of the conditions in (11) is satisfied.

Next suppose that $\inf_{k\in J}\left\|g^{k}\right\|=0$ and ${\bar{x}}$ is a
cluster point of the sequence $\\{x^{k}\\}$. As in the proof of Theorem 5,
assume that there is no subsequence ${\widehat{J}}\subset\mathbb{N}$
satisfying (19). Following the proof of Theorem 5, we again find that
$0\in\bar{\partial}f({\bar{x}})$. ∎

##  4\. Concluding Remarks

The extension of the gradient sampling algorithm to non-Lipschitzian,
continuous, directionally Lipschitz functions addresses the possibility of
unbounded and potentially empty Clarke subdifferentials. These possibilities
effect both the construction of the algorithm and the convergence results.
Specifically, in line (vii) of the algorithm, we require that the direction of
steepest descent be normalized to have unit magnitude since it may happen that
the sequence $\\{g^{k}\\}$ is unbounded. Although other normalization
strategies are possible, we chose a unit normalization for simplicity. As for
the convergence results, the results differ from the Lipschitzian case only by
the inclusion of outcome (c) in Theorem 5 as well as Corollaries 2 and 3. This
outcome occurs only if the sequence $\\{g^{k}\\}$ does not converge to zero in
which case it is shown that the sequence $\\{x^{k}\\}$ converges to a limit
${\bar{x}}$. Lemma 11 indicates that this can be manifested in excessively
short stepsizes. Nonetheless, in this case failure to converge to a Clarke
stationary point only occurs when either
$\bar{\partial}f({\bar{x}})=\emptyset$ or $\bar{\partial}f({\bar{x}})$ is
unbounded and

$-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)\notin{\,\mathrm{int}\,[}({\bar{\partial}^{\infty}}f({\bar{x}}))^{*}]={\,\mathrm{int}\,\left[\mathrm{dom}\left(\hat{d}f({\bar{x}})(\cdot)\right)\right]},$

or equivalently, the regular subderivative $\hat{d}f({\bar{x}})(\cdot)$ is not
continuous at the direction of steepest descent (see Lemma 5). This
observation yields two open question in the directionally Lipschitz case.
First, is it possible for $\bar{\partial}f({\bar{x}})=\emptyset$, and if so,
when does this occur? Second, is there a away to modify the search direction
so that the iterates are not attracted to non-stationary points at which
$-\mathrm{proj}_{\bar{\partial}f({\bar{x}})}\,(0)\notin{\,\mathrm{int}\,(}{\bar{\partial}^{\infty}}f({\bar{x}}))^{*}$,
or is this fundamental limitation of the method?

Finally, we note that the class of directionally Lipschitz functions is still
not sufficiently broad to capture the non-symmetric spectral functions even
though the method has successfully been applied in this case [4, 5, 6]. For
these functions, there is still much more work to do and it is likely that a
very different approach to the convergence analysis is required.

## References

  * [1] J. Borwein and Q. J. Zhu.  Techniques of Variational Analysis.  Canadian Math Society, 2005.
  * [2] J.M. Borwein, J.V. Burke, and A.S. Lewis.  Differentiability of cone-monotone functions on separable Banach space.  Pro. Amer. Math. Soc., 132:1067–1076, 2003.
  * [3] J. V. Burke, A. S. Lewis, and M. L. Overton.  Approximating Subdifferentials by Random Sampling of Gradients.  Math. Oper. Res., 27(3):567–584, 2002.
  * [4] J. V. Burke, A. S. Lewis, and M. L. Overton.  Two Numerical Methods for Optimizing Matrix Stability.  Linear Algebra Appl., 351/352:117–145, 2002.
  * [5] J. V. Burke, A. S. Lewis, and M. L. Overton.  A Nonsmooth, Nonconvex Optimization Approach to Robust Stabilization by Static Output Feedback and Low-Order Controllers.  IFAC Proceedings Volumes, 36:175–181, 2003.
  * [6] J. V. Burke, A. S. Lewis, and M. L. Overton.  A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization.  SIAM Journal on Optimization, 15(3):751–779, 2005.
  * [7] James V. Burke, Frank E. Curtis, Adrian S. Lewis, Michael L. Overton, and Lucas E. A. Sim oes.  Gradient sampling methods for nonsmooth optimization.  In A.M. Bagirov, M. Gaudioso, N. Karmitsa, M.M. Mäkella, and S. Taheri, editors, Numerical Nonsmooth Optimization: State of the Art Algorithms, chapter 6, pages 201–225. Springer, 2020.
  * [8] James V. Burke and Sien Deng.  Weak sharp minima revisited, part ii: Applications to linear regularity and error bounds.  Math. Prog., 104:236–261, 2005.
  * [9] J.V. Burke.  Methods for Solving Generalized Systems of Inequalities with Application to Nonlinear Programming.  PhD thesis, University of Illinois at Urbana-Champaign, 1983.
  * [10] F. H. Clarke.  Optimization and Nonsmooth Analysis.  Wiley, New York, 1983.  Reprinted by SIAM, Philadelphia, 1990.
  * [11] K. C. Kiwiel.  Convergence of the Gradient Sampling Algorithm for Nonsmooth Nonconvex Optimization.  SIAM Journal on Optimization, 18(2):379–388, 2007.
  * [12] Qiuying Lin.  Sparsity and Non-Convex, Non-Smooth Optimization.  PhD thesis, University of Washington, Seattle, 2009.
  * [13] L. Nirenberg.  Lecture notes in functional analysis.  1961\.
  * [14] Ralph Tyrrell Rockafellar and Roger J.-B. Wets.  Variational analysis.  Springer, 1998.
  * [15] R.T. Rockafellar.  Clarke’s tangent cones and the boundaries of closed sets in $\mathbb{R}^{n}$.  Nonlin. Analysis: Th. Meth. and Appl., 3:145–154, 1979.
  * [16] R.T. Rockafellar.  Directionally lischitzian functions and subdifferential calculus.  proc. London Math. Soc., 39:331–355, 1979.
  * [17] R.T. Rockafellar.  Generalized directional derivatives and subdifferentials of nonconvex functions.  Canadian J. Math., 32:157–180, 1980.