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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


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 is the mathematician of the village of Asterix

%d bloggers like this: