Projection on epigraph via a proximal operator

A while ago I posted this article on how to project on the epigraph of a convex function where I derived the optimality conditions and the KKT conditions. This post comes as an addendum proving a third way to project on an epigraph. Do read the previous article first because I use the same notation here.

We take the infimum which corresponds to the optimization problem that defines the projection on the epigraph and we have

\begin{aligned} &\inf_{x,s: f(x) \leq s} \left\{ \tfrac{1}{2}\|z-x\|^2 + \tfrac{1}{2}(s-\tau)^2\right\}\\ =&\inf_{x,\xi\geq 0: f(x) \leq \tau + \xi} \left\{ \tfrac{1}{2}\|z-x\|^2 + \tfrac{1}{2}\xi^2\right\}\\ =&\inf_{x,\xi\geq 0: f(x) - \tau \leq \xi} \left\{ \tfrac{1}{2}\|z-x\|^2 + \tfrac{1}{2}\xi^2\right\}\\ =&\inf_{x} \left\{ \tfrac{1}{2}\|z-x\|^2 + \tfrac{1}{2}\max\{0, f(x) - \tau\}^2\right\}, \end{aligned}

where we have done the converse of an epigraphical relaxation; we define the function $h(x) = \max\{0, f(x) - \tau\}^2$ and notice that this is minimized at

$\bar{x} = \mathrm{prox}_{h}(z),$

and $\bar{s} = \max\{\tau, f(\bar{x})\}$. This is of course only useful to the extent that $\mathrm{prox}_{h}$ is computable.

mathbabe

Exploring and venting about quantitative issues

Look at the corners!

The math blog of Dmitry Ostrovsky

The Unapologetic Mathematician

Mathematics for the interested outsider

Almost Sure

A random mathematical blog

Mathematix

Mathematix is the mathematician of the village of Asterix