$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$

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?


This is not just strictly convex, it's strongly convex.

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

  • $\begingroup$ Do we know that $\langle x - y, \nabla f(y) \rangle$ is a convex function of $(x,y)$? I'm missing that part. $\endgroup$ – littleO Aug 8 '14 at 19:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Aug 9 '14 at 3:32
  • $\begingroup$ y is indeed a constant. $\endgroup$ – trembik Aug 9 '14 at 16:35
  • $\begingroup$ Thank you for your answer :) and my apologies for 'strict convexity' - I did mean 'strong convexity', my bad. $\endgroup$ – trembik Aug 9 '14 at 16:37

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.