4
$\begingroup$

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function. Denote $X^*$ as the set of minimizers of $f$ and assume $X^*$ is unbounded. Is it possible that $\|g_x\|$ is unbounded when $d(x,X^*)$ is bounded where $g_x\in\partial f(x)$. Here $\partial f(x)$ denotes the set of subgradient vectors of $f$ at $x$ and $d(x,X^*)$ denotes the distance between point $x$ and set $X^*$.


I know $X^*$ is a closed convex set and I am thinking whether it is true that $\|g_x\|$ is bounded given $d(x,X^*)=1$. It must be true if $X^*$ is bounded, but not sure when it is unbounded. Also, does it help if we further assume $f$ is differentiable, so that $\partial f(x)=\{\nabla f(x)\}$?


Edit: I realized that what I really want to ask is whether it is possible that $\|g_x\|$ is unbounded but $d(x,X^*)$ is bounded. It is not equivalent to the boundedness of the ratio of $\|g_x\|$ and $d(x,X^*)$.

$\endgroup$

2 Answers 2

3
$\begingroup$

The function $q$ might be unbounded even in 1-neighborhood of $X^*$; here is an example of such function $f$ on the $(x,y)$-plane.

Let $\phi(t)=|t|-t$. Choose a sequence $x_n\to \infty$. For each $n$ consider function $f_n(x,y)=\phi[-2\cdot x_n\cdot(x-x_n)+ (y-x_n^2)]$. Let $f=\max_n\{f_n\}$.

$\endgroup$
3
  • $\begingroup$ So by saying "the answer is no", you mean for your example, it is possible that $d(x,X^*)=1$ but $\|g_x\|$ is unbounded? or you mean it is not possible that $q(x)$ is unbounded? If it is the second case, then you need to prove $q(x)$ is bounded for any example $f$ right? $\endgroup$ Commented Apr 16, 2023 at 13:09
  • $\begingroup$ By the way, is It possible to also have a counterexample when subgradient reduces to gradient? $\endgroup$ Commented Apr 16, 2023 at 13:41
  • $\begingroup$ @JeanLegall, in the constructed example, $q$ is unbounded, and "yes" you can make such example smooth with unbounded $q$ in $1$-nbhd from $X^*$. (Use a smoothed version of $\phi$ and sum instead of max.) $\endgroup$ Commented Apr 16, 2023 at 13:50
2
$\begingroup$

Take the function $f:\mathbb{R}^2\to\mathbb{R}$, $f(x,y)=y^4$. Then $X^*$ is the $x$ axis, $dist(\;(x,y), X^*)= |y|$, $\Vert \nabla f(x,y)\Vert =4|y|^3$. $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\ve}{{\varepsilon}}$

$\endgroup$
2
  • $\begingroup$ Thanks for your answer. What I actually want is the case when $dist(x,X^*)$ is bounded but $\nabla f(x)$ unbounded. However, for the current statement of the question, your example also works. $\endgroup$ Commented Apr 16, 2023 at 13:55
  • $\begingroup$ I will try to sketch a plausibility argument in favor of your guess. $\endgroup$ Commented Apr 16, 2023 at 14:19

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.