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

Have you analyzed separately the Hessian for $x>0$ and for $x<0$? — Andrés E. Caicedo, Jun 16 '14 at 01:33
The Hessian turned out to be the identity but the columns are swapped, so no cases to consider. — Lemon, Jun 16 '14 at 01:41
Of course there are cases to consider. The graph of $C$ does not cross the $y$-axis, so it is not convex. If you "know" that $C$ is convex, then you are restricting the domain of $C$, and the same restriction applies to the Hessian. — Andrés E. Caicedo, Jun 16 '14 at 01:43
What have you considered as the "contradiction"? You need the entire epigraph of $f$ to be convex, not just one slice of it. — S.B., Jun 16 '14 at 01:53
$C$ has two connected components, each of which is separately convex. However, the union is not convex. — Cheerful Parsnip, Jun 16 '14 at 02:35
Can you elaborate on the connected components please? I don't see it — Lemon, Jun 16 '14 at 02:47
@GrumpyParsnip, okay I know what you mean now. I missed the other branch, but it still doesn't explain the cases $x >0 $ and $x<0$ because the Hessian doesn't depend on that at all. — Lemon, Jun 16 '14 at 07:11

p.s. · Answer 1 · 2014-06-17T03:44:10.973

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.

edited Jun 17 '14 at 03:44

answered Jun 16 '14 at 19:56

p.s.

6,401

So what was my mistake? – Lemon Jun 16 '14 at 23:54
I guess you're assuming that the sublevel set of a nonconvex function can't be convex, which is wrong. (Incidentally, the determinant of the Hessian being negative does not imply that f is concave. In fact, f is neither convex nor concave.) – p.s. Jun 17 '14 at 00:02
Yes, the determinant part was red-herring. I meant to explain that the Hessian has positive and negative e-values and the conclusion is as you stated. How did you check the quasi convexity thing? I've never heard of it. I know hyperbolas are supposed to be convex. – Lemon Jun 17 '14 at 00:20
Added some more detail to address your questions. – p.s. Jun 17 '14 at 03:45

score 0 · Answer 2 · answered Jun 16 '14 at 20:33

0

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.

answered Jun 16 '14 at 20:33

Dirk

11,680

Why am I getting a contradiction?

2 Answers2