Check the function for convexity

Question

I am currently trying to complete my optimisation methods assignment.

I have a function $$f(x,y) = \left(y - x^2\right)^2 + (1-x)^2$$ and I need to check it for convexity.

I have found the Hessian matrix

$$ H = \begin{pmatrix} 12x^2 - 4y + 2 & -4x \\ -4x & 2 \end{pmatrix}$$

As far as I know, the function is convex if and only if its Hessian matrix is positive define. According to Sylvester's criterion, a matrix is positive define if its leading principal minors are positive. However, when I write down the Hessian matrix's minors, I get the following

$$ \begin{align} M_1 &= 12 x ^2 - 4y + 2 \\ M_2 &= 8x^2 - 4y + 2 \end{align}$$

From what I have written, I can't conclude about the minor sign and can't check for convexity. I am stuck on this and would really appreciate if somebody would recommend what to do.

If we take x=0 and y=1, the determinant of hessian is negative, hence it is not convex. — Cherryblossoms, Mar 08 '23 at 20:45
As far as I understand, this function is also not concave. So I can say that this function is neither concave, nor convex ? — zenitsu, Mar 08 '23 at 20:51
Please review your question. It is meaningless as written. The function $f$ depends on $x$ and $t$ and then suddenly a $y$ appears. — coudy, Mar 08 '23 at 21:02
@coudy, I apologise for that. Of course, $f$ depends on $(x,y)$. — zenitsu, Mar 08 '23 at 21:06

score 0 · Accepted Answer · answered Mar 09 '23 at 04:28

You're on a good track, but you're missing 2 ideas.

First: The condition for $f$ to be convex at a point is actually for the Hessian $\mathbf{H}$ to be positive semidefinite at that point. It's the difference between requiring $\mathbf{v}^T \mathbf{Hv} > 0$ vs $\mathbf{v}^T \mathbf{Hv} \ge 0$ for all nonzero $\mathbf{v}$. See sample reference on page 12 here. To test for positive semi-definiteness, you can use a similar version of Sylvester's criterion (wiki reference), but it's a little more involved. For a $2 \times 2$ matrix I would prefer to just write out $\mathbf{v}^T \mathbf{Hv}$ and see whether it's nonnegative.

Second: If someone says "Is $f$ a convex function?" then it means "Is $f$ convex at every point in its domain?" In other words, you would need $H$ to be positive semidefinite no matter what $x, y$ you use. For your function this clearly fails: it's easy to choose $x, y$ such that your first principal minor $M_1$ becomes negative.

Bonus: In the comments you asked a followup question about whether $f$ is concave. Saying $f$ is concave is the same as saying $-f$ is convex (wiki reference). This turns out to also fail, because the $M_1$ you computed is sometimes strictly positive, so the $M_1$ for $-f$ will sometimes be strictly negative. In other words, you're correct to say that $f$ is neither a convex function nor a concave function.

Of course, it can be convex/concave on certain subsets of its domain, which might be useful depending on your purposes. But if someone just says "is $f$ a convex/concave function?" then the answer is no.

I appreciate your answer! Thank you. – zenitsu Mar 09 '23 at 10:58 — zenitsu, Mar 09 '23 at 10:58

Check the function for convexity

1 Answers1