2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.