Why am I getting a contradiction?

Question

Let $f(x,y) = xy$ and define $$C = \{ (x,y) : xy \geq 1 \}.$$

The Hessian of this function is indefinite and has positive and negative eigenvalues. But we know the set $C$ is convex since this is just the epigraph of $1/x$. So what is wrong?

Addendum: $$epi(f) = -C = \{(x,y): -xy \leq -1 \}$$

$$H(f) = \begin{bmatrix} 0 &-1 \\ -1&0 \end{bmatrix}$$

and $$Det(H) = -1 <0$$ so it is concave. But $xy \geq 1$ is convex in $\mathbb{R}^2.$

Answer 1

The sublevel sets of a function are convex if the function is convex. However, the reverse is not true. If the sublevels sets of a function are convex, then the function is called quasiconvex, but it need not be convex.

For example, on the domain $x,y \ge 0$, the function $f(x,y)=-xy$ is quasiconvex, but not convex. There is no contradiction; it is simply an example of why quasiconvex functions are strictly more general than convex functions.

To check that $f$ is quasiconvex, we just need to check the sets $S_a=\{(x,y) \ | \ -xy \le a, \ x,y\ge 0 \}$ are convex for all $a$. For $a\ge0$, $S_a$ is the entire positive quadrant. For $a <0$, this is equivalent to $-y-a/x \le 0$, a sublevel set of a convex function.

For more about quasiconvexity, see section 3.4 of Boyd Vandenberghe. It gives some general conditions you can use to check quasiconvexity.

Answer 2

What @p.s writes also work in one dimension: $f(x) = \tfrac{x^2}{1+x^2}$ is not convex, but all the sets $\{x\ :\ f(x) < c\}$ are convex (as they are intervals). I.e. $f$ is quasiconvex but not convex.