# Algorithms for projecting a point onto the convex hull spanned by a set of vectors

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.

• 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). – Joseph O'Rourke Feb 12 at 12:03
• 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$. – M. Winter Feb 12 at 13:42
• Thanks @M.Winter - How do I specify the constraint set of the QP in terms of the vector set $V$? – ted Feb 12 at 18:27
• @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$. – Dirk Feb 13 at 5:34

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.

• 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?) – ted Feb 13 at 2:55
• Also, @M.Winter - what "standard solvers" were you thinking of? – ted Feb 13 at 6:16
• @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. – M. Winter Feb 13 at 10:24