# $F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex


Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex function, possibly nonsmooth, $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a smooth convex function with Lipschitz continuous gradient.

Function $Q(x,y)$:

$Q(x,y) := f(y) + \langle x-y, \nabla f(y) \rangle + \frac{L}{2} \|x-y\|^2_2 + g(x)$

is said to admit a unique minimizer. Does it mean that $Q(x,y)$ is a strictly convex function? I.e. does strict convexity of $\|x-y\|^2_2$ implies that the whole sum is strictly convex? How can we show this?

A strictly convex function has at most one unique minimizer on any open interval. But that does not guarantee that a minimizer exists. For instance, $f(x)=e^x$ is strictly convex, but it does not have a minimizer on any open interval. Strong convexity is a stronger condition; it guarantees the existence of a unique minimizer.
Yes, adding a strictly convex function to another convex function does ensure that the sum is strictly convex; and the same can be said for strong convexity. This follows simply from the basic definitions of the terms, and the ability to "add" inequalities. Strict convexity: \begin{aligned} &g(tx_1+(1-t)x_2) \leq tg(x_1) + (1-t)g(x_2), \\ & h(tx_1+(1-t)x_2) \lt th(x_1) + (1-t)h(x_2) \\ &\Longrightarrow\quad g(tx_1+(1-t)x_2)+h(tx_1+(1-t)x_2)\lt \\ &\qquad\qquad\left(g(x_1)+th(x_1)\right)+(1-t)\left(g(x_2)+h(x_2)\right)\end{aligned} And strong convexity: \begin{aligned} &g(tx_1+(1-t)x_2) \leq tg(x_1) + (1-t)g(x_2), \\ & h(tx_1+(1-t)x_2) \leq th(x_1) + (1-t)h(x_2) - \tfrac{1}{2}mt(1-t)\|x_1-x_2\|^2 \\ &\Longrightarrow\quad g(tx_1+(1-t)x_2)+h(tx_1+(1-t)x_2)\leq \\ &\qquad\qquad\left(g(x_1)+th(x_1)\right)+(1-t)\left(g(x_2)+h(x_2)\right) - \tfrac{1}{2}mt(1-t)\|x_1-x_2\|^2\end{aligned}
• Do we know that $\langle x - y, \nabla f(y) \rangle$ is a convex function of $(x,y)$? I'm missing that part. – littleO Aug 8 '14 at 19:08
• I would like to see the context here. I'm going to guess $y$ is intended to be constant. That's certainly the case when studying, say, first-order methods for $f(x)+g(x)$ with $f$ smooth and $g$ nonsmooth. – Michael Grant Aug 9 '14 at 3:32