Projection to sublevel sets of convex/strongly convex function

Question

Given a convex compact set $K\subset\mathbb{R}^D$ and convex function $f:K\rightarrow \mathbb{R}$, the sublevel set $$ X_\alpha = \{ x \in K : f(x) \leq \alpha \} $$ defines a convex closed set (assuming it is non-empty). I would like to compute the projection operator $\Pi_{X_\alpha}$ to $X_\alpha$ for any point in $K$. Are there known methods and iteration complexity results for computing $\Pi_{X_\alpha}$ when f is convex or strongly convex?

I couldn't find references on this, even though such projections could appear frequently in constrained convex optimisation. I'm especially curious if strong convexity could lead to linear convergence when computing such projections.

Answer 1

The projection can be written as a convex optimization problem \begin{align*} \Pi_{X_{\alpha}}(\bar{x}) \in \arg\min_{x} \quad & \| x - \bar{x} \|\\ \text{s.t.} \quad & f(x) \leq \alpha \end{align*}

where $\bar{x} \in K$ is the point you want to project, and $\|\cdot\|$ is the norm you use for the projection. Note that depending on the nature of $f$ and your norm (especially if they are polyhedral), the projection may not be unique.

You can solve this problem using any algorithm for convex optimization, e.g., an interior-point method which has polynomial complexity. This is the most general case.

There are special cases where you can have closed-form solutions, or more efficient algorithms. For instance, if $f$ is a quadratic function, and you use Euclidean distances, then you can compute the projection by solving a linear system. If $f$ is a polyhedral function, the above problem is a quadratic optimization problem, which you can also solve using simplex.