Project to nearest point in convex polytope

Question

Is there a reasonably efficient algorithm for the following task?

Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$
Find: a point $y \in \mathcal{C}$ that is as close to $x$ as possible

Assume that $\mathcal{C}$ is specified by a collection of linear inequalities, that the dimension $d$ is fairly high, and "close" is measured using $L_2$ distance, i.e., we want to minimize $||x-y||_2$. is there an efficient algorithm for this problem?

---

I can see how to solve this in polynomial time using linear programming if "close" were measured using $L_1$ or $L_\infty$ distance, but I'm more interested in the $L_2$ distance metric. I keep thinking there might be some algorithm based on identifying the set of inequalities that are violated by $x$ and then doing something, but I can't quite put together a working algorithm.

I found the following paper which describes an algorithm (exponential-time in the worst case but often efficient, like the simplex method):

Philip Wolfe. Finding the Nearest Point in a Polytope. Mathematical Programming, vol 11, 1976, pp.128--149.

However, that paper requires $\mathcal{C}$ to be presented as a list of vertices rather than a list of inequalities, so it can't be used for my problem. (Converting from inequalities to a set of vertices will cause an exponential blowup; typically the number of vertices is exponential in the number of inequalities.)

Answer 1

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can solve this problem in polynomial time using several methods, one being the ellipsoid method (originally due to Kozlov, Tarasov and Khachiyan [1]).

We can write $\|y - x\|_2^2$ as $y^Ty - 2x^Ty + x^Tx$. Thus an equivalent problem is $$ \min_y\ (y^Ty - 2x^Ty) \text{ such that } A y\leq b. $$ This is a convex quadratic program, since in this case $Q$ is the identity matrix, which is positive definite.

[1] The polynomial solvability of quadratic programming, USSR Computational Mathematics and Mathematical Physics, 20(5):223–228, 1980; Science Direct