How to show $\phi^*$ is finite and differentiable?

94 Views Asked by At

I am studying Mirror descent and nonlinear projected subgradient methods. At page 170 proposition 3.1, part d, the author claims that $\phi^*$ is finite and differentiable if and only if the inverse map $(\partial \phi)^{-1}$ is everywhere single valued and Lipschitz continuous with $\sigma^{-1}$ where $\phi {}:{} \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}$ be a proper convex and Lipschitz function and $\sigma >0$.

Show $\phi^*$ is finite and differentiable if and only if the inverse map $(\partial \phi)^{-1}$ is everywhere single valued and Lipschitz continuous with $\sigma^{-1}$.

$\phi^*$ is conjugate function which is defined as below: $$ \phi^*(z) = \sup_x {}\{ \langle x,z\rangle - \phi(x)\}. $$

1

There are 1 best solutions below

3
On

Firstly, $\sigma$ is not the Lipschitz constant of $\phi$. It is the strong convexity modulus of $\phi$, if $\phi$ is assumed to be strongly convex.

If $\phi^*$ is finite everywhere and differentiable, its subdifferential,

$$ \partial \phi^*(x) = \{\nabla \phi^*(x)\} $$

for all $x$. But $v\in \partial \phi(x)$ is equivalent to $x \in \partial \phi^*(v)$ (since $\phi$ is assumed to be proper, convex and lsc). Therefore, $\partial \phi^* = (\partial \phi)^{-1}$, which is single-valued.

Conversely, we want to prove that if $(\partial \phi)^{-1}$ is everywhere single-valued, then $\phi^*$ is everywhere finite and differentiable. To that end we use the fact that $\phi = \phi^{**}$ (because $\phi$ is assumed to be proper and lsc) and we apply what we showed above.

The rest of your question has to do with the Lipschitz constant of $(\partial \phi)^{-1}$ being $1/\sigma$ when $\phi$ is $\sigma$-strongly convex. By definition, $\phi$ is $\sigma$-strongly convex if $\phi-\tfrac{\sigma}{2}\|{}\cdot{}\|^2$ is convex. It is easy to show that $\phi$ is strongly convex if and only if $\partial \phi$ is strongly monotone. Then, we apply Proposition 12.54 in the book of Rockafellar and Wets to complete the proof.