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$
3
  • $\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$ Jan 15, 2015 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, 2015 at 16:37
  • $\begingroup$ That is right. As stated, the theorem is false. $\endgroup$ Jan 16, 2015 at 22:58

1 Answer 1

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$
10
  • $\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, 2015 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, 2015 at 16:24
  • $\begingroup$ Well, then your $\lambda$ is not fixed. $\endgroup$
    – ZhuShY
    Jan 16, 2015 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, 2015 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, 2015 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .