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 be a proper, convex, continuous function; its epigraph is the nonemtpy convex closed set

For convenience, we define the projection of a pair onto the epigraph of as

Let ; if , then . Suppose . Let and so that ; this pair solves the optimization problem

The KKT conditions for are

Clearly, since . Then, because of the second condition, and, because of the fourth condition, , so the third condition yields

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

We compute the partial subdifferentials of with respect to the primal variables :

The *dual function* is defined as

The optimality conditions for the optimization problem which defines the dual function are and , therefore, with

and

Then, the Lagrangian dual function becomes

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

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

### Like this:

Like Loading...