Convex formulation of the smallest distance to a point outside of a polyhedron

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.

• However, you are given the vertices, not $Ax \leq b$. In other words, you have a $\mathcal V$-polytope, not an $\mathcal H$-polytope. Jun 6, 2020 at 8:46

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}$$