1
$\begingroup$

Show that the following function $f:\Re^{n}\rightarrow \Re$ is convex. \begin{equation} f(x)=-\exp(-g(x)) \end{equation} where $g:\Re^{n}\rightarrow \Re$ is a twice differentiable function with convex domain and satisfies \begin{eqnarray*} \left( \begin{array}{cc} \nabla^{2} g & \nabla g \\ \nabla^{T} g & 1 \\ \end{array} \right)\geq 0 \;(semidefinite\; positive\; matrix) \end{eqnarray*} for $x\in Dom$ $g$.\ My idea to prove that is to show that the Hessian of $f$ is a semidefinite positive matrix. So, I computed the Hessian of $f$ \begin{eqnarray*} \nabla^{2}f(x)&=&-\exp(-g(x))\left( \begin{array}{cccc} g_{x_{1}}^{2}-g_{x_{1}x_{1}} & g_{x_{2}}g_{x_{1}}-g_{x_{2}x_{1}} & \ldots & g_{x_{n}}g_{x_{1}}-g_{x_{n}x_{1}} \\ g_{x_{2}}g_{x_{1}}-g_{x_{2}x_{1}} & g_{x_{2}}^{2}-g_{x_{2}x_{2}} & \ldots & g_{x_{n}}g_{x_{2}}-g_{x_{n}x_{2}} \\ \vdots & \vdots & \ddots & \vdots \\ g_{x_{n}}g_{x_{1}}-g_{x_{n}x_{1}} & g_{x_{2}}g_{x_{n}}-g_{x_{2}x_{n}} & \ldots & g_{x_{n}}^{2}-g_{x_{n}x_{n}} \end{array} \right)\\ &=&\exp(-g(x))\left( \nabla^{2}g-\nabla g \nabla^{T}g\right) . \end{eqnarray*} Until now I havent been able to use the hipotesis to prove what I want, just that $\nabla^{2}g$ is a semidefinite positive matrix. Also, I know that $\nabla g \nabla^{T}g$ is a semidefinite positive matrix (but I dont know if this result is useful). Thanks for the help.

$\endgroup$
  • 1
    $\begingroup$ Your notation is strange. $\nabla^2$ is the Laplacian, not the Hessian. $\endgroup$ – Robert Israel Mar 1 '17 at 0:33
  • $\begingroup$ @RobertIsrael the notation $\nabla^{2}$ for the Hessian is quite common in optimization despite the conflict with it's use for the Laplacian operator. $\endgroup$ – Brian Borchers Mar 1 '17 at 2:22
  • $\begingroup$ If "$g$ convex" is part of your hypotheses, then you don't need all those derivatives (i.e you don't need to assume differentiability of $g$). The title of your question and it's body don't quite match. Please clarify. $\endgroup$ – dohmatob Mar 1 '17 at 7:36
  • $\begingroup$ @dohmatob It is not literally part of the hipotesis. But, from the hipotesis I proved that $\nabla^{2}g$ is a semidefinite positive matrix which implies that $g$ is convex. $\endgroup$ – F. Saldaña Mar 1 '17 at 21:14
  • $\begingroup$ 'm lost. How do you go about proving that a hessian is p.s.d if you don't assume that the function in question is differentiable (in fact twice!), so that you can even form the hessian, to begin with ? $\endgroup$ – dohmatob Mar 2 '17 at 8:15
1
$\begingroup$

In the one-variable case, what you need for a function $-\exp(-g(x))$ (where $g$ is twice differentiable) to be convex is $g''(x) \ge g'(x)^2$. Thus in the many-variable case, you need $$ \dfrac{d^2}{dt^2} g(x_t) \ge \left(\frac{d}{dt} g(x_t)\right)^2 $$ on every line $x_t = a + b t$ in the domain. This translates to

$$ b^T H b \ge (b \cdot \nabla g)^2 = b^T (\nabla g) (\nabla g)^T b \ \text{for all } b$$ where $H$ is the Hessian of $g$, and that is equivalent to positive semidefiniteness of $H - (\nabla g) (\nabla g)^T$.

$\endgroup$
1
$\begingroup$

You don't need differentiability of $g$...

Lemma: If $g: \mathbb R^n \rightarrow (-\infty, +\infty]$ is convex and $h: \mathbb R \rightarrow \mathbb R$ is convex non-decreasing, then $h \circ g$ is convex.

Proof: Let $x, y \in \mathbb R^n$ and $t \in [0, 1]$. Then

$$ \begin{split} (h \circ g)(tx + (1-t)y) &:= h(g(tx + (1-t)y)) \\ &\le h(t g(x) + (1-t)g(y))\text{ ($g$ convex, $h$ non-decreasing)}\\ &\le t h(g(x)) + (1-t)h(g(y))\text{ ($h$ convex)} \\ &=: t(h \circ g)(x) + (1-t)(h \circ g)(y), \end{split} $$ showing that $h \circ g$ is convex.$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \Box$


Now apply the lemma with $h(a) := -\exp(-a)$.

$\endgroup$
  • 1
    $\begingroup$ I never said you should use $h(a) \equiv \exp(-a)$. I said $h(a) = -\exp(-a)$. Mind the outermost minus (-) sign... $\endgroup$ – dohmatob Mar 2 '17 at 19:08
  • $\begingroup$ I realize that $h(a)=-exp(−a)h(a)=exp⁡(−a)$ is concave, so I cannot applied the Lemma $\endgroup$ – F. Saldaña Mar 2 '17 at 21:14
  • $\begingroup$ What do you mean by "$h(a) = -\exp(-a)h(a)$" ? $h(a):= -\exp(-a)$ defines a convex function, definitely. What's your critique about precisely ? $\endgroup$ – dohmatob Mar 10 '17 at 23:18
0
$\begingroup$

Let $x\in \Re^{n}$ then by the hipotesis \begin{eqnarray*} (x^{T},-x^{T}\nabla g) \left( \begin{array}{cc} \nabla^{2} g & \nabla g \\ (\nabla g)^{T} & 1 \\ \end{array} \right) \left( \begin{array}{c} x \\ -(\nabla g)^{T} x \\ \end{array} \right)=x^{T}\nabla^{2}gx-x\nabla g(\nabla g)^{T}x\geq 0 \end{eqnarray*} since $x\in \Re^{n}$ is arbitrary, then the Hessian of $f$ is positive-semidefinite which implies that $f$ is convex.

$\endgroup$

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.