3
$\begingroup$

Suppose that $f: \mathbb{R}^n \to \mathbb{R}$ is convex and globally Lipschitz continuous.

Let $(x^k) \subset \mathbb{R}^n$ be a sequence such that $ x^k \to \bar{x} $ for some $\bar{x} \in \mathbb{R}^n$.

Assume $(\varepsilon_k) \subset \mathbb{R}_{+}$ a sequence of positive scalars such that $\varepsilon_{k} \to 0 \, .$


Does the following hold:

$$ \operatorname{dist} \left( \, \partial_{\varepsilon_k} f(x^k) \, , \, \partial f (\bar{x}) \, \right):= \sup_{g \in \partial_{\varepsilon_k} f(x^k)} \, \, \inf_{h \in \partial f (\bar{x})} \, \| g - h \|_2 \to 0 $$

where

  • $\partial_{\varepsilon_k} f(\cdot)$ denotes the $\varepsilon_k$-subdifferential of $f$
  • $\partial f(\cdot)$ denotes the regular convex subdifferential of $f$
  • $\| \cdot \|$ denotes the Euclidean distance.

The following is all from Convex Analysis and Minimization Algorithms II and might be of use:

Definition 1.1.1 Given $x \in \mathbb{R}^n$ the vector $s \in \mathbb{R}^{n}$ is called an $\varepsilon$ -subgradient of $f$ at $x$ when the following property holds: $$ f(y) \geqslant f(x)+\langle s, y-x\rangle-\varepsilon \quad \text { for all } y \in \mathbb{R}^{n} $$

It follows immediately from the definition that

  • $\partial_{\varepsilon} f(x) \subset \partial_{\varepsilon^{\prime}} f(x)$ whenever $\varepsilon \leqslant \varepsilon^{\prime}$
  • $\partial f(x)=\partial_{0} f(x)=\cap\left\{\partial_{\varepsilon} f(x): \varepsilon>0\right\}\left[=\lim _{\varepsilon \downarrow 0} \partial_{\varepsilon} f(x)\right] $

Theorem 1.1.4 For $\varepsilon \geqslant 0, \partial_{\varepsilon} f(x)$ is a closed convex set, which is nonempty and bounded.

Proposition 4.1.1 Let $\left\{\left(\varepsilon_{k}, x_{k}, s_{k}\right)\right\}$ be a sequence converging to $(\varepsilon, x, s),$ with $s_{k} \in$ $\partial_{\varepsilon_{k}} f\left(x_{k}\right)$ for all $k .$ Then $s \in \partial_{\varepsilon} f(x)$.

Proposition 4.1.2 Let $\delta>0$ and $L$ be such that $f$ is Lipschitzian with constant $L$ on some ball $B(x, \delta),$ where $x \in \mathbb{R}^n$. Then, for all $\delta^{\prime}<\delta$ $$ \|s\| \leqslant L+\frac{\varepsilon}{\delta-\delta^{\prime}} $$ whenever $s \in \partial_{\varepsilon} f(y),$ with $y \in B\left(x, \delta^{\prime}\right)$.

As a result, the multifunction $\partial_{\varepsilon} f$ is outer semi-continuous, just as is the exact subdifferential.

Theorem 4.1.3 Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a convex Lipschitzian function on $\mathbb{R}^{n} .$ Then there exists $K>0$ such that, for all $x, x^{\prime}$ in $\mathbb{R}^{n}$ and $\varepsilon, \varepsilon^{\prime}$ positive: $$ \Delta_{H}\left(\partial_{\varepsilon} f(x), \partial_{\varepsilon^{\prime}} f\left(x^{\prime}\right)\right) \leqslant \frac{K}{\min \left\{\varepsilon, \varepsilon^{\prime}\right\}}\left(\left\|x-x^{\prime}\right\|+\left|\varepsilon-\varepsilon^{\prime}\right|\right) $$

This result implies the inner semi-continuity of $(x, \varepsilon) \longmapsto \partial_{\varepsilon} f(x)$ for a Lipschitz-continuous $f$.

In particular, for fixed $\varepsilon>0$

$$\partial_{\varepsilon} f(y) \subset \partial_{\varepsilon} f(x)+\|y-x\| B(0, \frac{K}{\varepsilon}) \quad \text{for all } x \text{ and } y \, .$$

Corollary 4.1.5 Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ be convex. For any $\delta \geqslant 0,$ there is $K_{\delta}>0$ such that $$\Delta_{H}\left(\partial_{\varepsilon} f(x), \partial_{\varepsilon} f\left(x^{\prime}\right)\right) \leqslant \frac{K_{\delta}}{\varepsilon}\left\|x-x^{\prime}\right\| \quad \text{ for all } x \text{ and } x^{\prime} \in B(0, \delta) \, .$$

Theorem 4.2.1 Let be given $f: \mathbb{R}^n \to \mathbb{R}$, $x \in \mathbb{R}^n$ and $\varepsilon \geqslant 0 .$ For any $\eta>0$ and $s \in \partial_{\varepsilon} f(x),$ there exist $x_{\eta} \in B(x, \eta)$ and $s_{\eta} \in \partial f\left(x_{\eta}\right)$ such that $\left\|s_{\eta}-s\right\| \leqslant \varepsilon / \eta$.

This result can be written in a set formulation: $$ \partial_{\varepsilon} f(x) \subset \bigcap_{\eta>0} \bigcup_{\|y-x\| \leqslant \eta}\left\{\partial f(y)+B(0, \frac{\varepsilon}{\eta})\right\} . $$


The following one is not from the above mentioned source but easy to prove:

Theorem Assume $f: \mathbb{R}^n \to \mathbb{R}$ is convex and let $x \in \mathbb{R}^n$. Then for every $\varepsilon > 0$ there is a $\delta > 0$ such that

$$ \bigcup_{y \in B_{\delta}(x)} \partial f(y) \subset \partial_{\varepsilon} f(x) \,. $$

$\endgroup$
0

2 Answers 2

2
$\begingroup$

The Clarke subdifferential is upper semi-continuous. By definition, for each $\epsilon>0$ and $k$ big enough we must have that $\partial f(x^k) \subset \partial f(x) + B(0, \epsilon).$ Hence, for such $k$ big enough,

$$\sup_{g_k \in\partial f(x^k)} \inf_{g \in\partial f(x)} \| g_k - g \| \leq \epsilon. $$ Consequently,

$$\lim \sup_{g_k \in\partial f(x^k)} \inf_{g \in\partial f(x)} \| g_k - g \| = 0$$

$\endgroup$
2
  • $\begingroup$ Many thanks for your reply. However, my question is concerning the $\varepsilon$-subdifferential. $\endgroup$ Commented Mar 25, 2021 at 22:10
  • $\begingroup$ If you don't mind and maybe have some time, would you have a look at this other question I have: math.stackexchange.com/questions/4219167/… Even a literature recommendation would help. Many thanks. $\endgroup$ Commented Aug 13, 2021 at 8:51
1
$\begingroup$

Your Theorem 4.2.1 and the upper semicontinuity of Clarke differential is enough to answer the question.

We want to prove that $$\lim \sup_{g \in \partial_{\varepsilon_k} f(x^k)} \, \, \inf_{h \in \partial f (\bar{x})} \, \| g - h \|_2 = 0. \tag{*}$$ The main idea is to note that, since $$\partial_{\epsilon} f (x) \subset \cup_{\|y-x\| \leq \sqrt{\epsilon}}\ \partial f (y) + B\left(0,\sqrt{\epsilon}\right),$$ each $g \in \partial_{\varepsilon_k} f(x^k)$ is an approximation of some Clarke differential close to $x$.

Aiming to prove (*), let $\epsilon>0$ be given, there exists $\delta>0$ such that for all $x' \in B(\bar{x},\delta)$ implies that $$\partial f(x') \subset \partial f(\bar{x})+B\left(0,\dfrac{\epsilon}{2}\right) \tag{1} $$ due to upper semicontinuity of Clarke differential. Choosing $k_0$ such that for each $k \geq k_0$ it's true that $$\sqrt{\epsilon_k}<\dfrac{\min\{\delta,\epsilon\}}{2} \tag{2}$$ and $$\|x^{k} - \bar{x}\| < \dfrac{\delta}{2}, \tag{3}$$ given $g \in \partial_{\epsilon_k} f(x^{k}) $, by the Theorem 4.2.1, there exist $y^{k}$ such that $$\|y^{k} - x^{k}\| \leq \sqrt{\epsilon_k}$$ and $$g \in \partial f (y^{k}) + B\left(0,\dfrac{\epsilon_k}{\sqrt{\epsilon_k}}\right) = \partial f (y^{k})+ B\left(0,\sqrt{\epsilon_k}\right).\tag{4}$$ Since $\|y^{k} - x^{k}\| < \dfrac{\delta}{2}$ and $\|x^{k} - \bar{x}\| < \dfrac{\delta}{2}$ by (2) and (3), we have $$\|y^{k} - \bar{x}\| \leq \|y^{k} - x^{k}\|+\|x^{k} - \bar{x}\|<\delta$$ which means, by (1), $$ \partial_{\epsilon_k} f(y^{k}) \subset \partial f(\bar{x})+B\left(0,\dfrac{\epsilon}{2}\right).$$ Consequently, by (4), \begin{align} g \in \partial f (y^{k})+ B\left(0,\sqrt{\epsilon_k}\right) \subset & \partial f(\bar{x})+B\left(0,\dfrac{\epsilon}{2}\right) + B\left(0,\sqrt{\epsilon_k}\right) \\ \subset & \partial f(\bar{x})+B\left(0,\dfrac{\epsilon}{2}\right) + B\left(0,\dfrac{\epsilon}{2}\right) \\ \subset & \partial f(\bar{x})+B\left(0,\epsilon \right).\end{align} Finally, $$\inf_{h \in \partial f(\bar{x})} \|g - h\|<\epsilon $$ for all $g\in \partial_{\epsilon_k} f (x^{k})$ which means $$\sup_{g\in \partial_{\epsilon_k} f(x^{k})} \inf_{h \in \partial f(\bar{x})} \|g - h\| \leq \epsilon.$$

$\endgroup$
3
  • 1
    $\begingroup$ Many, many thanks for your great effort! I will go through it and try to follow it step by step. When I understand everything I will mark it as answered. Again, thank you very much. =) $\endgroup$ Commented Mar 26, 2021 at 8:40
  • 1
    $\begingroup$ I did not have the time yet to follow every single step but I think this is exactly what I was looking for! $\endgroup$ Commented Mar 26, 2021 at 22:57
  • 1
    $\begingroup$ Take your time. You will find that it's correct. I have checked the proof of Theorem 4.2.1 on the aforementioned book and everything is fine. $\endgroup$ Commented Mar 26, 2021 at 23:10

You must log in to answer this question.

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