2
$\begingroup$

My precise question is from an exercise;

Let $f : \mathbb{R}^2 → \mathbb{R}$ be a twice differentiable function. Prove that there exists a $λ ∈ R$ such that $g : \mathbb{R}^2 → \mathbb{R}$ defined as $g(x) := f (x) + (λ/2)||x||^2$ is convex.

Hint: compute the Hessian of $g$ and prove that for $λ$ large enough, this Hessian is positive definite.

I am trying to follow the hint but immediately running into errors when computing the hessian of g.

I am really not sure how to proceed given the $f(x)$ along with $||x||$. I mean we only still have the one variable $x$, so what possibility is there for double derivatives?

$$ \left[ \begin{array}{ c c } g_{ff} & g_{fx} \\ g_{fx} & g_{xx} \end{array} \right] $$

Which seems rather silly. Would anyone care point out my misinterpration/fundamentally flaw, and lead me on the right track?

$\endgroup$
  • $\begingroup$ The functions $f$ and $g$ are defined as functions that take a vector in $\mathbb{R}^2$ as input and return a single real number as output. So the $x$ is actually a vector containing two numbers. You can compute derivatives with respect to $x_1$ and $x_2$. $\endgroup$ – John von N. Jan 15 '15 at 19:09
  • $\begingroup$ I have edited my answer after a good remark from @SZhu. Actually, the second derivatives must be bounded to find a fixed $\lambda$. $\endgroup$ – Alex Silva Jan 16 '15 at 16:37
  • $\begingroup$ That is right. As stated, the theorem is false. $\endgroup$ – Michael Grant Jan 16 '15 at 22:58
2
$\begingroup$

By considering $\| \cdot\|$ the $2$-norm, the Hessian is given by

\begin{equation} H = \left [ \begin{array}{cc} \frac{\partial^2 f(x_1,x_2)}{\partial x_1^2} + \lambda & \frac{\partial^2 f(x_1,x_2)}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f(x_1,x_2)}{\partial x_2 \partial x_1}& \frac{\partial^2 f(x_1,x_2)}{\partial x_2^2} + \lambda\\ \end{array} \right], \end{equation} for $x = (x_1,x_2)$.

The matrix $H$ is positive definite if and only if all principal minors are positive. Thus,

$$ \frac{\partial^2 f(x_1,x_2)}{\partial x_1^2} + \lambda > 0,$$ and

$$\left( \frac{\partial^2 f(x_1,x_2)}{\partial x_1^2} + \lambda \right)\left( \frac{\partial^2 f(x_1,x_2)}{\partial x_2^2} + \lambda \right) - \left(\frac{\partial^2 f(x_1,x_2)}{\partial x_1 \partial x_2} \right)\left(\frac{\partial^2 f(x_1,x_2)}{\partial x_2 \partial x_1} \right) >0.$$

You have to assume other constraints for $f(x)$. Notice that you should have $$ \frac{\partial^2 f(x_1,x_2)}{\partial x_1^2} > -\infty,$$ for all $x_1$ and $x_2$, otherwise there is no $\lambda$ that guarantees the convexity of $g(x)$. I take the example given by @SZhu as follows.

If $\frac{\partial^2 f(x_1,x_2)}{\partial x_1^2}=-e^{x_1+x_2}$, then there is no fixed $\lambda$ such that the first principal minor is positive for all $x_1$ and $x_2$.

Yet, you also should have

$$ \frac{\partial^2 f(x_1,x_2)}{\partial x_2^2} > -\infty$$ and

$$\left(\frac{\partial^2 f(x_1,x_2)}{\partial x_1 \partial x_2} \right)\left(\frac{\partial^2 f(x_1,x_2)}{\partial x_2 \partial x_1} \right) < \infty,$$ for all $x_1$ and $x_2$.

If these conditions are satisfied then for $\lambda$ large enough, it is easy to see that the two principal minors are positive.

$\endgroup$
  • $\begingroup$ The only constraint on $f$ is twice differentiable, right? Consider $f(x) = -e^{x_1+x_2}$, which is good I think. However, $\frac{\partial^2 f(x_1,x_2)}{\partial x_1^2}=-e^{x_1+x_2}$ can tend to $-\infty$. So no fixed $\lambda$ can work for this function. Correct me if make errors here. $\endgroup$ – ZhuShY Jan 16 '15 at 16:11
  • $\begingroup$ Well, suppose you say a finite $\lambda$ work, but I can also find finite $x_1$ and $x_2$ such that $H$ is not positive definite thereby $g(x)$ is not strongly convex. This is basically from the definition of convergence to $\infty$. $\endgroup$ – ZhuShY Jan 16 '15 at 16:24
  • $\begingroup$ Well, then your $\lambda$ is not fixed. $\endgroup$ – ZhuShY Jan 16 '15 at 16:26
  • $\begingroup$ Ok, let me ask this. Do you want a fixed $\lambda$ that work for all $x$ or for a given $x$ you can find a $\lambda$ that make $g$ has positive definite hessian? $\endgroup$ – ZhuShY Jan 16 '15 at 16:27
  • $\begingroup$ I was directed here by @Michael Grant. You may also like to see my problem that is kind of related to this one. click here Thanks. $\endgroup$ – ZhuShY Jan 16 '15 at 16:31

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.