Consider a polyhedron $S$ whose set of extreme points (vertices) is $\{v_1, v_2,\dots,v_k\}$. Given a point $y \notin S$, we would like to find the point with the smallest distance to $y$. Provide a convex optimization formulation and justify why solving your formulation will lead to the correct answer.
I am thinking that for a convex polygon $P := \{x \in \mathbb{R}^2 \mid Ax \leq b \}$ we can formulate it as a quadratic program in the following way:
$$\begin{array}{ll} \underset{x \in \mathbb{R}^2}{\text{minimize}} & \|x – y\|^2\\ \text{subject to} & Ax \leq b\end{array}$$
But I am not sure if my formulation is general enough. I mean the objective function is clearly a convex function and the feasible set is a convex set. Hence, the optimization problem is a convex optimization
problem and if the minimum is zero, then $y$ is in the polygon.
Best Answer
Since you are given the vertices to represent the polytope, you want $x$ to be a convex combination of these.
$$\begin{array}{ll} \underset{x \in \mathbb{R}^2,\lambda \in \mathbb{R}^k}{\text{minimize}} & \|x - y\|^2\\ \text{subject to} & \sum_{i = 1}^k \lambda_i v_i = x, \lambda_i\geq 0, \sum_{i=1}^k \lambda_i = 1\end{array}$$