4
$\begingroup$

Let $g: E^{m} \rightarrow E^{1}$ be a convex function, and let $h: E^{n} \rightarrow E^{m} $ be an affine function of the form $h(x)=Ax+b$, where $A$ is an $m \times n$ matrix and $b$ is an $m \times 1 $ vector. Then, show that the composite function $f : E^n \rightarrow E^{1} $ defined as $f(x)=g(h(x))$ is a convex function.

Also, assuming twice differentiability of $g$, derive the expression for the hessian of $f$

$\endgroup$
10
$\begingroup$

Let $0 < \theta < 1$ and $x_1, x_2 \in E^m$. Note that $h(\theta x_1 + (1-\theta)x_2) = \theta h(x_1) + (1-\theta)h(x_2)$. It follows that \begin{align} f(\theta x_1 + (1-\theta) x_2) &= g(\theta h(x_1) + (1-\theta)h(x_2)) \\ &\leq \theta g(h(x_1)) + (1-\theta) g(h(x_2)) \\ &= \theta f(x_1) + (1-\theta) f(x_2) \end{align} so $f$ is convex.

From the chain rule, $f'(x) = g'(h(x)) h'(x) = g'(h(x))A$ so \begin{align} \nabla f(x) &= f'(x)^T \\ &= A^T g'(h(x))^T \\ &= A^T \nabla g(h(x)). \end{align} The chain rule again now tells us that $\nabla^2 f(x) = A^T \nabla^2 g(h(x)) h'(x) = A^T \nabla^2 g(h(x)) A$.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much. Can you explain why $$ \nabla f(x) &= f'(x)^T $$ $\endgroup$
    – user107723
    Jan 28 '14 at 11:35
  • 4
    $\begingroup$ If $f:\mathbb R^n \to \mathbb R^m$ is differentiable at $x$, then $f'(x)$ is an $m \times n$ matrix such that $f(x + \Delta x) \approx f(x) + f'(x) \Delta x$ when $\Delta x$ is small. So if $f:\mathbb R^n \to \mathbb R$, then $f'(x)$ is a $1 \times n$ matrix (row vector). In optimization, the convention is that $\nabla f(x)$ is a column vector, so $\nabla f(x) = f'(x)^T$. Also, $\nabla^2 f(x) = q'(x)$, where $q(x) = \nabla f(x)$. (So $q:\mathbb R^n \to \mathbb R^n$.) $\endgroup$
    – littleO
    Jan 28 '14 at 18:04
  • $\begingroup$ @littleO Is it possible to prove it from epigraphy point of view? $\endgroup$
    – Lei Hao
    Jan 16 '19 at 3:05

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.