# 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.

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.

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