Non-convex function in 2D that is $m$-restricted strongly convex

convex-analysis

Assume that $f:\mathbb{R}^2\to \mathbb{R}$ is a differentiable restricted $m$-strongly convex function as follows:

$$ f(y) \geq f(x) + \left<\nabla f (x),y-x\right>+\frac{m}{2}\|y-x\|^2$$
for all $x,y \in \mathbb{R}^2$ such that ($x=[x_1,0]^{\top}$ and $y=[0,y_2]^{\top}$) or ($x=[0,x_2]^{\top}$ and $y=[y_1,0]^{\top}$). In other words for all $1$-sparse $x$ and $y$ the above holds.

Can we have a non-convex function in 2D which satisfies the above condition?

Best Answer

Problem: Is there a non-convex differentiable function $f \, : \, \mathbb{R}^2 \to \mathbb{R}$ such that, for some constant $m > 0$, for all $a, b, c, d\in \mathbb{R}$, \begin{align*} f(a, 0) &\ge f(0, d) + a \frac{\partial f}{\partial x}(0, d) - d \frac{\partial f}{\partial y}(0, d) + \frac{m}{2}(a^2 + d^2), \tag{1}\\ f(0, b) &\ge f(c, 0) - c \frac{\partial f}{\partial x}(c, 0) + b \frac{\partial f}{\partial y}(c, 0) + \frac{m}{2}(c^2 + b^2) \tag{2} ? \end{align*}

Yes, there is. Here is an example.

Let $f(x, y) = x^4 + 24x^3 + 200x^2 + y^4 + 24y^3 + 200y^2$. Let $m = 8$.

It is easy to prove that $f(x, y)$ is not convex on $\mathbb{R}^2$.

The conditions are: for all $a, b, c, d\in \mathbb{R}$, \begin{align*} a^4 + 24a^3 + 196a^2 + 3d^4 + 48d^3 + 196d^2 &\ge 0, \\ b^4 + 24b^3 + 196b^2 + 3c^4 + 48c^3 + 196c^2 &\ge 0 \end{align*} which are both true (easy).

Related Question