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

Question

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.

Answer 1

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.