1
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .