Projection on Epigraph of a convex function

Question

Given a convex function $h:\mathbb{R}^n \rightarrow \mathbb{R}$, and a point $(x,\alpha) \in \mathbb{R}^n \times \mathbb{R}$, how can I find a closed formula to compute the projection of $(x,\alpha)$ in the epigraph of $h$?

Of course, I expect the formula to be given in terms of abstract entities such as $N_{epi h}((x,\alpha))$ or something like that...

If a closed formula can't be found, is there a way to express it on the form of an inclusion problem or at least a non-restricted optimization problem?

Any suggestions?

Answer 1

For any convex subset $H \subset \mathbb{R}^{n+1}$, the projection $P(x)$ of a point $x$ is characterized by \begin{equation*} \langle P(x) - x , z - P(x) \rangle \ge 0 \quad\forall z \in H. \end{equation*} This is, in turn, equivalent to $x - P(x) \in N_H(P(x))$. This gives your desired conclusion.

As pointed out by Michael Grant, you can write your projection problem as a constrained optimization problem. The optimization w.r.t.\ $\bar\alpha$ can be done explicitely. Indeed, the minimum is achieved for $\bar\alpha = \max(\alpha, h(\bar x))$. Hence, you obtain \begin{equation*} \min_{\bar x} \| x - \bar x\|^2 + \max(0, h(\bar x) - \alpha)^2. \end{equation*} This is a convex optimization problem.

Answer 2

Optimality Conditions

$\renewcommand{\Re}{\mathbb{R}}\newcommand{\barre}{\bar{\Re}}\newcommand{\epi}{\mathrm{epi}}\newcommand{\proj}{\mathrm{proj}}\newcommand{\minimize}{\mathrm{minimize}}$ Let $f:\Re^n\to\barre$ be a proper, convex, continuous function; its epigraph is the nonemtpy convex closed set

\begin{align} \epi f = \{(x,\alpha) \in \Re^n\times \Re {}\mid{} f(x) \leq \alpha \}.\tag{1} \end{align} For convenience, we define the projection of a pair $(z,\tau)\in\Re^n\times \Re$ onto the epigraph of $f$ as \begin{align} \Pi_f(z,\tau) = \proj_{\epi f}(z,\tau).\tag{2} \end{align}

Let $(z,\tau)\in\Re^n\times \Re$; if $(z,\tau)\in\epi f$, then $\Pi_f = I$. Suppose $(z,\tau)\notin\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{align} \minimize_{x,s:\ f(x)\leq s} \tfrac{1}{2}\|x-z\|^2 + \tfrac{1}{2}(s-\tau)^2.\label{OP}\tag{3} \end{align} The KKT conditions for $\bar{x},\bar{s}$ are

\begin{align} f(\bar{x}) &\leq \bar{s}\label{eq:kkt:1}\tag{4a}\\ \exists \bar{y}\geq 0: \bar{y} (f(\bar{x})-\bar{s}) &= 0\label{eq:kkt:2}\tag{4b}\\ z-\bar{x} &\in \bar{y} \partial f(\bar{x})\label{eq:kkt:3}\tag{4c}\\ \tau - \bar{s} &= -\bar{y}\label{eq:kkt:4}\tag{4d}. \end{align}

Clearly, $\bar{y}>0$ since $(z,\tau)\notin \epi f$. Then, because of \eqref{eq:kkt:2}, $\bar{s} = f(\bar{x})$ and, because of \eqref{eq:kkt:4}, $\bar{y}=f(\bar{x})-\tau$, so \eqref{eq:kkt:3} becomes

\begin{align} z-\bar{x} \in (f(\bar{x})-\tau) \partial f(\bar{x}).\label{eq:optcond}\tag{5} \end{align} It might be necessary to employ numerical methods to solve the optimality conditions. It is noteworthy that although there is a long list of functions with analytically and explicitly known formulas to compute their proximal operators, the computation of projections on epigraphs is more involved.

Dual epigraphical projection

Let us consider again problem \eqref{OP} and introduce the Lagrangian

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

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

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

The Lagrangian dual function $q$ is defined as $$ q(y) = \inf_{x,s}\mathcal{L}(x,s,y).\tag{8}\label{eq:8} $$ The optimality conditions for the optimization problem \eqref{eq:8} 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{align} &0 \in x-z+y\partial f(x^\star)\\ \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)\tag{9a} \end{align}

and

\begin{align} s^\star(y) = \tau + y.\tag{9b} \end{align}

Then, the Lagrangian dual function becomes

\begin{align} q(y) &= \mathcal{L}(x^\star(y), s^\star(y), y)\\ &= \tfrac{1}{2}\|\mathrm{prox}_{yf}(z)-z\|^2 + yf(\mathrm{prox}_{yf}(z)) + \tfrac{1}{2}y^2 -(\tau + y)y\\ &= y (f^y(z) - \tfrac{1}{2}y - \tau),\tag{10} \end{align} where $f^y$ is the Moreau envelope function of $f$ with parameter $y$. Then, the dual problem is

\begin{align} \mathrm{maximize}_{y\geq 0}\ q(y).\tag{11} \end{align}

Another approach

We take the infimum which corresponds to problem \eqref{OP} and we have

\begin{align} &\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{align}

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} = \operatorname{prox}_{h}(z), $$

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