7

When one writes

$$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$$

for $x,y\in \mathbb{R}^n$, $\lambda\in(0,1)$ what does this mean?

1) Does it mean that the function is jointly convex in $x = (x_1,\ldots,x_n)$ or convex in each argument $x_i$, $i=1,2,\ldots,n$?

2) Furthermore, what is the difference between joint convexity and element-wise convexity?

3) Is showing the above inequality the same as showing the Hessian is positive semi-definite?

jonem
  • 383
  • 3
    Joint convexity means that the restriction of the function to any segment is a convex function of a single variable. Element-wise convexity means that only vertical and horizontal segments are considered (in 2d - in higher dimensions there are more directions but the idea is the same) – Giuseppe Negro Apr 03 '14 at 20:15

1 Answers1

13

1) Jointly convex.

2) Element-wise convexity works for one variable only, other variables are supposed to be constant; joint convexity implies element-wise convexity, but the other implication is false. Consider a function $x^2+y^2-4xy$.

3) If the function is twice differentiable. For example, $f(x)=\|x\|$ is convex, but has troubles with Hessian in zero.

TZakrevskiy
  • 22,980