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

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)\}.$$

• They cite the book of Rockafellar and Wets. Do you have access to that? – Pantelis Sopasakis May 14 at 16:38
• @Pantelis Sopasakis: I do but I wanted to have the proof in simple wording here. – Saeed May 14 at 23:36

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.

• Could you explain why $v \in \partial \phi(x)$ is equivalent to $x\in \partial \phi^*(v)$? What fact you are using to get this? I would appreciate if show me how you get this using the definition. – Saeed May 15 at 18:20
• @Saeed I will update my answer later tonight or tomorrow. If you have access to Rockafellar's "Convex Analysis" you can find this in Chapter 23. – Pantelis Sopasakis May 15 at 18:28
• I will appreciate if you update your answer. – Saeed May 15 at 18:59