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 possibleAssume 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.)
Project to nearest point in convex polytope
algorithms;optimization;linear programming;numerical algorithms
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