If $f(x,y)$ is convex in $x$ (for any fixed $y$) and convex in $y$ (for any fixed $x$), is it convex?

Question

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}$$

Answer 1

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

Answer 2

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?

Answer 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$.