5

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$

Rodrigo de Azevedo
  • 1
user107723
  • 548

2 Answers2

11

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$.

littleO
  • 51,938
  • 1
    Thank you very much. Can you explain why $$ \nabla f(x) &= f'(x)^T $$ – user107723 Jan 28 '14 at 11:35
  • 5
    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$.) – littleO Jan 28 '14 at 18:04
  • 1
    @littleO Is it possible to prove it from epigraphy point of view? – Lei Hao Jan 16 '19 at 03:05
0

Affine composition Suppose g is convex, then $f(x ) = g(Ax + b )$ is convex.

Proof: \begin{align*} epi f &= \{(x, t ): f(x ) \le t\}\\ & = \{(x, t ): g(Ax + b ) \le t\}\\ & = \{(x,t ) : (Ax + b,t ) \in epi(g)\}\\ & = \{(x,t ) : h(x,t) \in epi(g)\}\\ & = h^{-1} epi(g) \end{align*}

Define $h$ as a function(affine actually) that maps $(x,t )$ to $(Ax + b, t)$. It's affine because \begin{align*} h(\theta(x_1,t_1) + (1-\theta)(x_2,t_2)) &= \left( A(\theta x_1 + (1-\theta)x_2) + b, \theta t_1 + (1-\theta)t_2 \right) \\ &= \theta(Ax_1 + b, t_1) + (1-\theta)(Ax_2 + b, t_2)\\ &= \theta h(x_1,t_1) + (1-\theta)h(x_2,t_2) \end{align*}

Therefore, epi(f) is the inverse image of h. Since epi g is convex and h is affine, we obtain that epi f is a convex set and thus f is a convex function (Refer to 2.3.2 Affine functions in Boyd Convex-Optimization).

Drfiting Away
  • 1