4
$\begingroup$

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{+\infty\}$ be an extended real-valued function that is proper, lower semicontinuous, and Lipschitz continuous over its domain $\newcommand{\dom}{\text{dom}}\dom(f)$ with constant $L$, i.e., $$|f(x)-f(y)|\leq L\|x-y\|,\quad\forall\,x,y\in\dom(f),$$ where $$\dom(f):=\{x\in\mathbb{R}^n:f(x)<+\infty\}.$$ is a closed convex set, possibly with empty interior. Let $\hat{\partial}f(x)$ denote the Fréchet subdifferential of $f$ at $x\in\dom(f)$.

My question: can we show $d(0,\hat{\partial}f(x))\leq L$ for $x\in\dom(f)$ satisfying $\hat{\partial}f(x)\ne\emptyset$? or in fact $d(0,\hat{\partial}f(x))$ can be arbitrarily large?

Here $d(0,\hat{\partial}f(x))$ denotes the distance from $0$ to the set $\hat{\partial}f(x)$. It is well-defined and achieved by a unique element because the set is closed and convex.


Recall the Fréchet subdifferential of $f$ at $\bar{x}\in\dom(f)$ is given by $$\hat{\partial} f(\bar{x}):=\left\{v\in\mathbb{R}^n:\liminf_{x\to \bar{x}}\frac{f(x)-f(\bar{x})-\langle v,x-\bar{x}\rangle}{\|x-\bar{x}\|}\geq 0\right\}.$$ It is well known that $\hat{\partial} f(\bar{x})$ can be empty for many $x\in\dom(f)$, but all points where $\hat{\partial} f(\bar{x})\ne\emptyset$ form a dense subset of $\dom(f)$.

Furthermore, if $\bar{x}$ is an interior point of $\dom(f)$, then the desired result is obviously true because $\hat{\partial} f(\bar{x})\subset\partial^C f(\bar{x})$, where the set of Clarke subdifferential $\partial^C f(\bar{x})\ne\emptyset$ and every Clarke subgradient $v\in \partial^C f(\bar{x})$ satisfies $\|v\|\leq L$. However, if $\bar{x}$ is on the boundary, then $\partial^C f(\bar{x})$ can be unbounded, and so is $\hat{\partial} f(\bar{x})$. This means we cannot expect every element to be controlled by a constant, but I observe that I can always find one element with small enough norm so that it is controlled by certain constant. I am not sure whether it is true in general.

$\endgroup$
1
  • $\begingroup$ Just an ituitive idea, which you may already considered. How about consider the tangent cone $C=T_xdom(f)$ of the convex set $dom(f)$? If the subdifferential $v\in\partial f(x)$ belongs to $C$ you might probably argue similary to the case $x$ is interior point. Otherwise probably the projection of $v$ to $C$ is still subdifferential and this reduces to the case $v\in C$ (hopefully). $\endgroup$
    – anything
    Jan 4 at 15:42

2 Answers 2

5
+50
$\begingroup$

Let $C$ be a triangle on the plane with a vertex at origin and angle $179^\circ$ at this vertex; $f(x)=-\|x\|$, it is Lipschitz with $L=1$. Then we have $f(x)\geqslant \langle v,x\rangle$, where $v$ is a very long vector whose direction is opposite to that of an angle bisector of $C$ at the origin. However, there seem to be no short vector in the subdifferential of $f$ at 0.

$\endgroup$
2
$\begingroup$

$\newcommand\R{\mathbb R}\newcommand\de{\delta}\newcommand\ep{\varepsilon}\newcommand\dom{\operatorname{dom}}$This is a detalization of Fedor Petrov's answer.

Let $n=2$. Take any real $k>0$. Let $$C:=\{x=(x_1,x_2)\in\R^2\colon|x_2|\le kx_1\}.$$ Let $f(x):=-\|x\|$ for $x\in C$ and $f(x):=\infty$ for $x\in\R^2\setminus C$. Then $\dom f=C$ and $f$ is $L$-Lipschitz with $L=1$ on $\dom f$.

Let $V$ denote the Fréchet subdifferential of $f$ at $(0,0)$. Take any $v=(v_1,v_2)\in\R^2$.

Then, letting $\cdot$ denote the dot product and letting $B_\de:=\{x\in\R^2\colon\|x\|\le\de\}$, we have
\begin{align} &v=(v_1,v_2)\in V \\ &\iff\forall\ep\in(0,1)\ \exists\de>0\ \forall x\in C\cap B_\de \\ &\qquad\qquad\qquad\qquad\qquad-\|x\|\ge v\cdot x-\ep\|x\| \\ &\iff\forall\ep\in(0,1)\ \forall x\in C\ \ -\|x\|\ge v\cdot x-\ep\|x\| \\ &\iff\forall x\in C\ \|x\|+v\cdot x\le0 \\ &\iff\text{for all points $x$ on the extreme rays} \\ &\qquad\quad\text{of the convex cone $C$ we have $\|x\|+v\cdot x\le 0$} \\ &\iff \sqrt{1+k^2}+v_1+k|v_2|\le0. \end{align}

So, $(-\sqrt{1+k^2},0)\in V$ and hence $V\ne\emptyset$. On the other hand, for any $v=(v_1,v_2)\in V$ we have $v_1\le-\sqrt{1+k^2}$ and hence $\|v\|\ge|v_1|\ge\sqrt{1+k^2}>1=L$. $\quad\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.