# Does $\partial_{\varepsilon_k} f(x^k)$ approximate $\partial f (\bar{x})$ for $x^k \to \bar{x}$ and $\varepsilon_{k} \to 0$?

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) \,.$$

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$$

• Many thanks for your reply. However, my question is concerning the $\varepsilon$-subdifferential. Commented Mar 25, 2021 at 22:10
• 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. Commented Aug 13, 2021 at 8:51

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.$$

• 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. =) Commented Mar 26, 2021 at 8:40
• I did not have the time yet to follow every single step but I think this is exactly what I was looking for! Commented Mar 26, 2021 at 22:57
• 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. Commented Mar 26, 2021 at 23:10