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