2

Let $f(x,y)$ be a function $X\times Y\rightarrow\mathbb R$, where $X\subset \mathbb R^n$ and $Y\subset \mathbb R^m$, and $x\in X,y\in Y$.

Suppose that $f(x,y)$ is convex in $x$ for any fixed $y$, and convex in $y$ for any fixed $x$. Does it follow that $f$ is convex?

I have the feeling that it does not. But I cannot find a simple counterexample.

The assumptions of the question imply that:

$$f\left(\lambda x_{1}+\left(1-\lambda\right)x_{2},y\right)\le\lambda f\left(x_{1},y\right)+\left(1-\lambda\right)f\left(x_{2},y\right)$$

$$f\left(x,\lambda y_{1}+\left(1-\lambda\right)y_{2}\right)\le\lambda f\left(x,y_{1}\right)+\left(1-\lambda\right)f\left(x,y_{2}\right)$$

for any $0\le\lambda\le1$.

On the other hand, if $f(x,y)$ is convex, the following (stronger) inequality must hold:

$$f\left(\lambda x_{1}+\left(1-\lambda\right)x_{2},\lambda y_{1}+\left(1-\lambda\right)y_{2}\right)\le\lambda f\left(x_{1},y_{1}\right)+\left(1-\lambda\right)f\left(x_{2},y_{2}\right)$$

I tried to derive this inequality, without success:

$$\begin{aligned} f\left(\lambda x_{1}+\left(1-\lambda\right)x_{2},\lambda y_{1}+\left(1-\lambda\right)y_{2}\right) & \le\lambda f\left(\lambda x_{1}+\left(1-\lambda\right)x_{2},y_{1}\right)\\ & \qquad+\left(1-\lambda\right)f\left(\lambda x_{1}+\left(1-\lambda\right)x_{2},y_{2}\right)\\ & \le\lambda\left(\lambda f\left(x_{1},y_{1}\right)+\left(1-\lambda\right)f\left(x_{2},y_{1}\right)\right)\\ & \qquad+\left(1-\lambda\right)\left(\lambda f\left(x_{1},y_{2}\right)+\left(1-\lambda\right)f\left(x_{2},y_{2}\right)\right)\\ & =\lambda^{2}f\left(x_{1},y_{1}\right)+\left(1-\lambda\right)^{2}f\left(x_{2},y_{2}\right)\\ & \qquad+\lambda\left(1-\lambda\right)f\left(x_{2},y_{1}\right)+\left(1-\lambda\right)\lambda f\left(x_{1},y_{2}\right) \end{aligned}$$

a06e
  • 6,665
  • This is called a biconvex function, https://en.wikipedia.org/wiki/Biconvex_optimization – a06e Oct 12 '18 at 19:11

3 Answers3

3

Take $f(x,y) = x^2 + x y^2$, on the set $A = \{ 1\leq x \leq 2, \ 10\leq y \leq 20 \}$ (for example).

Then $f$ is convex if we fix either of its arguments, since $f''_{xx} = 2 > 0$ and $f''_{yy} = 2x > 0$ .

However, the Hessian matrix of $f$, which equals $$ D^2 f = \left( \begin{matrix} 2 & 2y \\ 2y & 2x \end{matrix} \right), $$ is not positive definite, and hence $f$ is not convex on the set $A$.

Hayk
  • 3,595
  • 1
  • 10
  • 23
  • 2
    +1 And now that I think of it, $f(x, y) = xy$ works for $[0, \infty)^2$. – Theo Bendit Jul 01 '18 at 11:41
  • yes indeed, it's a better looking example. I just played with the Hessian, to build something which will violate the positive definiteness, but would have positive diagonal. – Hayk Jul 01 '18 at 11:54
  • @TheoBendit Thanks. That's indeed the simplest example. – a06e Jul 01 '18 at 19:15
2

In my opinion, the easiest counterexample is $$f(x,y) = x \, y.$$

gerw
  • 31,359
  • 2
    this example was already mentioned in the comments to my answer, and should be credited to @Theo Bendit – Hayk Jul 02 '18 at 03:51
  • @becko: No, this example works on all of $\mathbb{R}^2$, since the Hessian is constant. – gerw Jul 02 '18 at 11:41
0

I wonder if there's a finer counterexample, but you could take any convex function defined over $X \times Y$ and restrict its domain to a orthogonally convex, but not convex subset of $X \times Y$. For example, take the $0$ function, restricted to $$\mathbb{R} \times \lbrace 0 \rbrace \cup \lbrace 0 \rbrace \times \mathbb{R} \subseteq \mathbb{R} \times \mathbb{R}.$$ When you restrict to any horizontal or vertical line, the result is a convex function.

But I find this a little unsatisfying. I wonder if forcing the domain to be convex will make it true?

Theo Bendit
  • 50,900
  • Actually, in a similar vein of pettiness, even convexity of the domain is not quite sufficient. For example, define any non-convex function along the diagonal subset $\lbrace (x, x) : x \in \mathbb{R} \rbrace \subseteq \mathbb{R}^2$. I think it'll be similarly trivial to construct examples on convex sets with non-empty interiors, by exploiting boundary values. So, now I wonder, does this hold for functions defined on all of $X \times Y$? – Theo Bendit Jul 01 '18 at 11:22