Does approximately null gradient imply approximately global minimum for convex functions?

Question

Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one approximately minimizes $f$ by quasi-Newton methods, it is obtained a sequence of points $\{x^{k}\}_{k \in \mathbb{N}}$ so that $\lim_{k \rightarrow \infty}\|\nabla f (x^{k})\| = 0.$ However, it does not seem obvious that $\lim_{k \rightarrow \infty} f (x^{k}) = 0$. Consequently, there might be a possibility of distancing from the solution set when searching for critical points of convex functions, which seems odd. So here comes the question:

For a non-negative and differentiable convex function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ which vanishes in a non-empty convex set $\Omega$, does $$\lim_{k \rightarrow \infty}\|\nabla f (x^{k})\| = 0 \implies \lim_{k \rightarrow \infty} f (x^{k}) = 0?$$

Answer 1

$\newcommand\Om\Omega\newcommand\R{\Bbb R}$The answer is no.

Indeed, for real $k>0$, let $$G_k:=\{(x,y)\in\Bbb R^2\colon x>1,|y|<k\sqrt x\}. $$ For $(x,y)\in G_2$, let $$f_0(x,y):=y^2/x-1.$$ For all $(x,y)\in\R^2$, let $$f(x,y):=\max\big(0,\sup_{(u,v)\in G_2\setminus G_1}[f_0(u,v)+(\nabla f_0)(u,v)\cdot(x-u,y-v)]\big) =\max\Big(0,-1+\sup_{(u,v)\in G_2\setminus G_1}\Big(-\frac{v^2}{u^2},\frac{2 v}{u}\Big)\cdot(x,y)\Big),$$ where $\cdot$ stands for the dot product. The function $f$ is convex, being the pointwise supremum of a family of affine functions. Moreover, $f$ is real valued, because $(-\frac{v^2}{u^2},\frac{2 v}{u})$ is bounded in $(u,v)\in G_2\setminus G_1$.

In fact, for all $(x,y)\in\R^2$, $$ f(x,y)=\begin{cases} 0 & \text{ if }x\geq h(y), \\ y^2/x-1 & \text{ if }\sqrt{x}<| y| \leq 2 x ,\\ -4 x+4 y-1 & \text{ if }y\geq \max \left(0,2 x,x+\frac{1}{4}\right) ,\\ -4 x-4 y-1 & \text{ if }-y\geq \max \left(0,2 x,x+\frac{1}{4}\right), \end{cases} \tag{1}\label{1} $$ where $$ h(y):=\begin{cases} y^2 &\text{ if } | y| \geq 1/2, \\ | y| -1/4 & \text{ if }| y| <1/2. \end{cases} $$ In particular, $f=0$ on the nonempty open set $\Om=G_1$. Moreover, it is easy to see that the function $f_0$ is convex on $G_2$. So, $f=f_0$ on $G_2\setminus G_1$ and hence for $y=\frac32\,\sqrt x$ and $x>1$ one has $$(\nabla f)(x,y)=(\nabla f_0)(x,y)=\Big(-\frac9{4x},\frac3{\sqrt x}\Big)\to(0,0)$$ as $x\to\infty$, whereas $f(x,y)=f_0(x,y)=9/4-1\not\to0$.

Remark 1: The main difficulty here was of course to make $f$ real valued -- a condition having little to do with the essence of the problem.

Remark 2: The function $f$ may be not differentiable at points $(x,y)\in\R^2$ at which at least one of the inequalities in\eqref{1} turns into the equality. However, clearly the differentiability of $f$ has hardly anything to do with the essence of this problem. In particular, one can smooth $f$ everywhere by (say) convolving it with a mollifier, while retaining the essential properties of $f$ noted above.

---

For an illustration, here is the graph $\{(x,y,f(x,y))\colon-1\le x\le10,|y|\le4\}$: