4

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?

Saeed
  • 175
  • 1
    Do you mean: 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), \ 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)? \end{align} – River Li Sep 10 '21 at 10:19
  • @River Li: Yes. You are absolutely right so far. – Saeed Sep 12 '21 at 02:42
  • If so, I think it is not difficult to construct a counterexample of the form $f(x, y) = g(x) + g(y)$ for some non-convex function $g: \mathbb{R} \to \mathbb{R}$. – River Li Sep 12 '21 at 03:00
  • @River Li: what do you mean by a counter example? – Saeed Sep 12 '21 at 04:12
  • oh, example. Counterexample is for something like "f must be convex". – River Li Sep 12 '21 at 04:21
  • 1
    I think that you need to clarify: in the title, you said "strongly convex in 1-D", it might be prone to be understood as that $f$ is strongly convex in $x$ (fixed $y$), and strongly convex in $y$ (fixed $x$), respectively. But if you agree with my comment in #1, you don't mean that. – River Li Sep 16 '21 at 01:51
  • @River Li: thank you for your comment. I edited the title of the question. – Saeed Sep 16 '21 at 04:26

2 Answers2

1

$$f(x)=\frac m4(|x_1|-|x_2|)^2$$

enter image description here

Surb
  • 55,662
Rahul
  • 37
1

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

River Li
  • 37,323