Multivariable function showing there is at most 1 local optima that is not in the edges - checking each variable on its own

Question

Apologies if this has been asked before or is trivial. I couldn't find the answer.

I am trying to find the global minimum of a function. Doing so analytically is difficult, so trying to prove that it's convex, or concave, or essentially that there is 1 local optimum. Then empirically find a point $x,x+\epsilon$ (and $y$ similarly for a two-variable function) where its derivative's sign is $\mp$. Note that since this is my proof technique, I don't really care if it is convex, concave, increasing, or decreasing. Essentially I want to show that there is 1 local optima (aside from the edges as they can easily be calculated).

Since the function is a two-variable function, and is fairly complicated (and its derivatives), I am looking for other techniques for proving convexity without Hessian or $f(\lambda x_1 + (1-\lambda) x_2)\leq \lambda f(x_1) + (1-\lambda)f(x_2)$

One technique I thought of is first proving that a function $f(x,y)$ is convex by $x$, and then moving to show that it is convex by $y$.

My intuition says first consider $y$ as a constant and derive $f$ twice and prove convexity for $x$. Then similarly consider $x$ as a constant and derive $f$ twice and prove convexity for $y$.

My intuition also says that something is missing here. Seems like $\frac{\partial^2 f}{\partial x^2}$ and $\frac{\partial^2 f}{\partial y^2}$ is not enough (after all, when calculating the Hessian we also use the other derivatives).

I would appreciate it if someone can explain why my proposed technique is wrong or fix it (explain why simply calculating $\frac{\partial^2 f}{\partial x^2}$ and $\frac{\partial^2 f}{\partial y^2}$ is not enough).

If someone could explain how they would go about proving that a multivariable function is convex by 1 variable, and then prove that it is convex by another variable (and thus has at most 1 optima that is not in the edges) that would be helpful.

Thank you

Answer 1

You need two conditions,

$$ \dfrac{d^2 f}{d x^2} \; \dfrac{d^2 f}{d y^2} > \left(\frac{d^2 f}{d x d y}\right)^2 $$

and

$$ \dfrac{d^2 f}{d x^2} + \dfrac{d^2 f}{d y^2} > 0 $$ (see proof below).

Your intuitive approach seems reasonable, but considers only the behaviour along the $x$ and $y$ axis of this surface in 3 dimensions. As stated by @MartinR, $f = x y$ is a good counterexample:

In visual terms, it is formed like a saddle which is rotated by 45 degrees around the origin. In $x$ or $y$ direction, you will only get linear functions, but in direction $(x,-y)$ it will quadratically go negative.

Proof

(the proof itself uses the Hessian)

For the function to be convex everywhere, both eigenvalues $\lambda$ of the Hessian $H$ should be larger than zero. This can be rephrased:

• $\lambda_1 \lambda_2 = \det H > 0$. This leads directly to the first condition above.
• either $\lambda_1 > 0$ or $\lambda_2 > 0$. This condition is checked in the following.

Characteristic polynomial of $H$ is $$ \lambda^2 + P \lambda + \det H = 0 \quad \text{with } P = - d^2 f / d x^2 - d^2 f / d y^2 $$ the roots of the polynomial can be written as $$ 2 \lambda_{1,2} = -P \pm \sqrt{P^2 - 4 \det H} $$ As the Hessian is a symmetrix matrix, the roots must be real, and therefore $\sqrt{\bullet} > 0$.

Furthermore, note that as we used the determinant alerady as condition one, only one of the roots needs to be positive. We replace the $\pm$ by $+$ as this is the larger $\lambda$ and will always be positive if one of the values is positive. It follows that $$ \sqrt{P^2 - 4 \det H} > P $$ Two cases remain:

• $P > 0$: in this case, $\det H < 0$, which violates the first condition.

• Therefore, $P < 0$ must hold. In this case, no further conditions apply, as $\sqrt{\bullet} > 0$.