2
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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$: enter image description here

$\endgroup$
2
  • $\begingroup$ So actually no function $f(x,y)=x g(y)$ may be convex (given $g'(y) \neq 0$). Interesting. Thank you for the plot! $\endgroup$ – Jean-Claude Arbaut May 2 '14 at 14:42
  • $\begingroup$ Thanks a lot for the plot and the procedure to graphically demonstrate the non convexity. $\endgroup$ – user147050 May 3 '14 at 5:15
-1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the response, but I am not sure what you mean by all the quadrants. The domain of the function is $x,y \in (o,1]$, which is the first quadrant. $\endgroup$ – user147050 May 1 '14 at 8:10
-1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ The Hessian is not conditional positive semi-definite. The determinant of the Hessian is $\frac{-1}{y^4}$. $\endgroup$ – user147050 May 2 '14 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.