How to find a counter example for non convexity?

Question

Consider a simple function $f(x,y)=\frac{x}{y}, x,y \in (0,1]$, the Hessian is not positive semi definite and hence it is a non convex function. However, when we plot the function using Matlab/Maxima, it "appears" convex. For the sake of clarity we want to find points which violate the definition of convexity, in other words identify the region (in the plot) where the function is non-convex. Can you suggest a procedure to do the same ?

Answer 1

The Hessian is $$\nabla^2 f(x) = \begin{bmatrix} 0 & -y^{-2} \\ -y^{-2} & 2xy^{-3} \end{bmatrix}=\frac{1}{y^3}\begin{bmatrix} 0 & -y \\ -y & 2x\end{bmatrix}.$$ For nonzero $y$, the determinant $-y^{-4}$ is strictly negative. This means that there must be exactly one positive eigenvalue and one negative eigenvalue. The function is nonconvex over the entire domain. Indeed, it is nonconvex at every point $(x,y)$, $y\neq 0$.

The function is affine for fixed $y$, and convex for fixed positive $x$. So it may be that when you look at the MATLAB plot you're seeing the convexity of these cross sections. At any given point, however, it is actually concave along the direction defined by the eigenvector corresponding to the negative eigenvalue.

I cannot tell you how many people I have encountered that insist that this function is convex for positive $y$! Good for you for not falling into that trap.

EDIT: That suggests a way to graphically demonstrate non-convexity, by the way. Pick a point, say $x$, and find the negative eigenvector, $v$, or at least a vector satisfying $v^T\nabla^2f(x) v<0$. Plot the function $g(t)=f(x+tv)$. It will be concave, probably visually so, at $t=0$.

EDIT 2: Here you go: $x=0.25+t$, $y=0.75\pm t$:

Answer 2

I think if you only look at one quadrant of $f(x)=\frac{x}{y}$ then it appears to be convex but if you look at all the quadrants then you should see that its non-convex.

Answer 3

If you write down the Hessian matrix you'll see that for $x,y\in (0,1]$ the Hessian is indeed positive semi-definite. This is call conditional positive semi-definiteness. You can see the Hessian as a matrix parametrized by $x$ and $y$: it is positive semi-definite depending on their values. Try to compute the eigen-values as a function of $x$ and $y$.