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.



Algorithms for projecting a point onto the convex hull spanned by a set of vectors
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.


