4
$\begingroup$

Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the vectors in $V$.

I know this is a quadratic program, to find $\mathbf{z}^*$ that minimizes $\frac{1}{2}\|\mathbf{x}_0 - \mathbf{z}\|^2$ subject to $\mathbf{z} \in \text{conv}(V)$.

I also know that $\text{conv}(V)$ is a polytope and expressible as a set $S = \{ \mathbf{x} : A\mathbf{x} \le \mathbf{b} \}$.

However, I don't know how to derive the constraint matrix and constraint vector $(A,\mathbf{b})$ from the vectors in $V$.

Secondarily, I'm wondering if there are simple and fast algorithms to solve this problem. The number of vectors in $V$ will be less than 250 and the dimensionality will be less than 50.

And finally, I am hoping to express the solution $\mathbf{z}^* = \text{Proj}(\mathbf{x}_0)$ in something like barycentric coordinates with respect to the vectors in $V$. In other words, I'd like to express $\mathbf{z}^*$ as the vector $(\alpha_1, \ldots, \alpha_n)$ such that $\mathbf{z}^* = \sum_i \alpha_i \mathbf{v}_i$ with $\alpha_i \ge 0$ and $\sum_i \alpha_i = 1$. Given that the set $V$ won't be linearly independent (because $n > d$), I know that such barycentric coordinates are not well defined. I'm hoping to use something akin to a least norm solution $\|\alpha\|^2$ here.

$\endgroup$
  • 1
    $\begingroup$ Perhaps: Find all simplex faces of the hull, and then project to each. Chen, Yunmei, and Xiaojing Ye. "Projection onto a simplex." arXiv preprint arXiv:1101.6081 (2011). $\endgroup$ – Joseph O'Rourke Feb 12 at 12:03
  • 1
    $\begingroup$ What's wrong with the quadratic program you are suggesting? There are solvers available. The most natural formulation will also output barycentric coordinates. I think a translation into H-represenation (i.e. via $(A,\mathbf b)$) is a bad idea, as the size of $A$ and $\mathbf b$ can depend exponentially on $n$. $\endgroup$ – M. Winter Feb 12 at 13:42
  • $\begingroup$ Thanks @M.Winter - How do I specify the constraint set of the QP in terms of the vector set $V$? $\endgroup$ – ted Feb 12 at 18:27
  • 1
    $\begingroup$ @DimaPasechnik I doubt that the closest points define the facet. Imagine $x_0$ close to some facet which is quite wide so that it's vertices are far away. There may be points right behind the facet that are closer to $x_0$. $\endgroup$ – Dirk Feb 13 at 5:34
3
$\begingroup$

As you suggested, your problem can be formulated as a quadratic program:

$$\boxed{\begin{array}{rl} \min & \|\mathbf x_0-(\alpha_1\mathbf v_1+\cdots +\alpha_n\mathbf v_n)\|^2\\ \text{s.t.} & \alpha_1+\cdots+\alpha_n=1\\ & \alpha\ge 0 \end{array}}$$

The optimal solution to this program gives you the projection $\mathbf v:=\alpha_1 \mathbf v_1+\cdots \alpha_n\mathbf v_n$ in barycentric coordinates.

You can express above program in a more "standard" way, by setting $V := (\mathbf v_1,...,\mathbf v_n)\in\Bbb R^{d\times n}$ to be the matrix with the $\mathbf v_i$ as columns, and optimize $\mathbf v\in\Bbb R^d,\alpha\in\Bbb R^n$ via

$$\boxed{\begin{array}{rl} \min & \|\mathbf x_0-\mathbf v\|^2\\ \text{s.t.} & V\alpha = \mathbf v\\ & \alpha\ge 0\\ & \sum_i \alpha_i = 1 \end{array}}$$

In the optimal point, $\mathbf v$ is the desired projection and $\alpha$ contains the barycentric coordintes. There exist standard solvers for quandratic problems like this.

$\endgroup$
  • $\begingroup$ Aside from handing the program off to a solver, do you know of fast & cheap proximal descent algorithms to solve this problem? (And good tutorials?) $\endgroup$ – ted Feb 13 at 2:55
  • $\begingroup$ Also, @M.Winter - what "standard solvers" were you thinking of? $\endgroup$ – ted Feb 13 at 6:16
  • $\begingroup$ @ted Cplex seems to be an appropriate free solver for this. I personally used SeDuMi in MATLAB. On top of that, I unfortunately cannot help you a lot, as my expertise is not in applied otimization. $\endgroup$ – M. Winter Feb 13 at 10:24

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.