1

The easy statement tells me that the conjugate of a strongly convex function has a lipschitz continuous gradient.

But I am thinking about the how could a conjugate of a function is strongly convex. I cannot figure this out.

For example.

For the optimization, min $H(x)+G(y)$ such that $Ax+By=b$. Then the Lagrange function is $L(x,y,\lambda)=H(x)+G(y)-\lambda^{T}(Ax+By-b)$. According to the duality of original problem could be $D(\lambda)=-H^{*}(A^{T}\lambda)-G^{*}(B^{T}\lambda)+\langle\lambda,b\rangle$. Here, $H$ and $G$ are all strongly convex. And $G$ is quadratic, $B$ has full row rank. Then could $-D$ is strongly convex?

Zim
  • 4,318
Sustcer_Shuai
  • 51
  • 4
  • To clarify: Are you asking "What conditions on $f$ guarantee that its conjugate $f^*$ is strongly convex?" – Zim Jun 21 '20 at 16:01
  • Yes, I cannot image an example. And a book gives a example that I mentioned in the question. I couldn't understand this example. – Sustcer_Shuai Jun 22 '20 at 09:59

1 Answers1

1

Proposition 14.2, Bauschke & Combettes' book, volume 2:

Let $\mathcal{H}$ be a real Hilbert space, let $f\colon\mathcal{H}\to\mathbb{R}$ be continuous and convex, and let $\gamma\in\mathbb{R}_{++}$. The following are equivalent:

\begin{equation} f^*\text{ is }\gamma^{-1}\text{ strongly convex} \quad \Leftrightarrow \quad \frac{\gamma}{2}\|x\|^2 - f(x) \text{ is convex}. \end{equation}

So it suffices to check if there exsits some constant such that the righthand side above is still convex.

A simple example is $f=\|\cdot\|^2$.

Zim
  • 4,318