Projection on an epigraph

Here we study the problem of projecting onto the epigraph of a convex continuous function. Unlike the computation of the proximal operator of a function or the projection on its sublevel sets, the projection onto epigraphs is more complex and there exist only a few functions for which semi-explicit formulas are available.

epiproj

Projection of a point onto the epigraph of a convex function.

KKT Optimality Conditions

Let f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} be a proper, convex, continuous function;  its epigraph is the nonemtpy convex closed set

\begin{aligned} \mathrm{epi} f := \{(x,\alpha) \in \mathbb{R}^n\times \mathbb{R} {}\mid{} f(x) \leq \alpha \}. \end{aligned}

For convenience, we define the projection of a pair (z,\tau)\in\mathbb{R}^n\times \Re onto the epigraph of f as

\begin{aligned} \Pi_f(z,\tau) := \mathrm{proj}_{\mathrm{epi} f}(z,\tau). \end{aligned}

Let (z,\tau)\in\mathbb{R}^n\times \mathbb{R}; if (z,\tau)\in\mathrm{epi} f, then \Pi_f = I. Suppose (z,\tau)\notin\mathrm{epi} f. Let \bar{x}=\bar{x}(z,\tau) and \bar{s}=\bar{s}(z,\tau) so that \Pi_f(z,\tau)=(\bar{x},\bar{s}); this pair solves the optimization problem

\begin{aligned} \mathrm{minimize}_{x,s:\ f(x)\leq s}\ \tfrac{1}{2}\|x-z\|^2 + \tfrac{1}{2}(s-\tau)^2. \end{aligned}

The KKT conditions for \bar{x},\bar{s} are

\begin{aligned} f(\bar{x}) &\leq \bar{s}\\ \exists \bar{y}\geq 0: \bar{y} (f(\bar{x})-\bar{s}) &= 0\\ z-\bar{x} &\in \bar{y} \partial f(\bar{x})\\ \tau - \bar{s} &= -\bar{y}. \end{aligned}

Clearly, \bar{y}>0 since (z,\tau)\notin \mathrm{epi} f. Then, because of the second condition, \bar{s} = f(\bar{x}) and, because of the fourth condition, \bar{y}=f(\bar{x})-\tau, so the third condition yields

\begin{aligned} z-\bar{x} \in (f(\bar{x})-\tau) \partial f(\bar{x}). \end{aligned}

It might be necessary to employ numerical methods to solve the optimality conditions.

Dual epigraphical projection

Consider again the optimization problem which defined the epigraphical projection. We introduce the Lagrangian

\begin{aligned} \mathcal{L}(x,s,y) = \tfrac{1}{2}\|x-z\|^2 + \tfrac{1}{2}(s-\tau)^2 + y(f(x)-s). \end{aligned}

We compute the partial subdifferentials of \mathcal{L} with respect to the primal variables (x,s):

\begin{aligned} \partial_x\mathcal{L}(x,s,y) &= x - z + y\partial f(x)\\ \partial_s\mathcal{L}(x,s,y) &= s - \tau - y. \end{aligned}

The dual function q  is defined as

q(y) = \inf_{x,s}\mathcal{L}(x,s,y).

The optimality conditions for the optimization problem which defines the dual function are 0\in \partial_x\mathcal{L}(x,s,y) and 0\in\partial_s\mathcal{L}(x,s,y), therefore, q(y)=\mathcal{L}(x^\star(y), s^\star(y), y) with

\begin{aligned} &0 \in x-z+y\partial f(x^\star)\notag\\ \Leftrightarrow\ &0 \in (I+y\partial f)(x^\star) - z\\ \Leftrightarrow\ &z \in (I+y\partial f)(x^\star)\\ \Leftrightarrow\ &x^\star(y) = (I+y\partial f)^{-1}(z)\\ \Leftrightarrow\ &x^\star(y) = \mathrm{prox}_{yf}(z), \end{aligned}

and

\begin{aligned} s^\star(y) = \tau + y. \end{aligned}

Then, the Lagrangian dual function becomes

\begin{aligned} q(y) &= \mathcal{L}(x^\star(y), s^\star(y), y)\\ &= \tfrac{1}{2}\|\mathrm{prox}_{yf}(z)-z\|^2 + y f(\mathrm{prox}_{yf}(z)) + \tfrac{y^2}{2} - sy\\ &= y f^y(z) + \tfrac{y^2}{2} -(\tau+y)y\\ &= y (f^y(z) - \tfrac{y}{2} -s) \end{aligned}

where f^y is the Moreau envelope function of f with parameter y.  Then, the dual problem is the following 1-dimensional optimization problem

\begin{aligned} \mathrm{maximize}_{y\geq 0}\ q(y). \end{aligned}

Up next: examples of epigraphical projections: the squared norm and norm cases.

Advertisements

2 responses

  1. […] a follow-up on the previous post titled Projection on an epigraph, we here discuss how we can project on the epigraph of the squared norm […]

    Like

  2. […] while ago I posted this article on how to project on the epigraph of a convex function where I derived the optimality conditions […]

    Like

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

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

%d bloggers like this: