Suppose I'm given the set of vertices, $\{v_i \} $, of a convex polytope. Suppose that I'm also given a point $p$ in terms of its coordinates, and I'm promised that $p \in \mbox{conv} \{v_i \}$.
How can I find a convex decomposition of this point in terms of the vertices? How can I find a minimal decomposition in terms of $d+1$ vertices, as Caratheodory's theorem guarantees?
Suppose now that I also have the facet description of the polytope, can that simplify the task?
If we are given a set of $n$ (distinct) vertices $\{\mathrm{v}_i\}_{i=1}^n \subset \mathbb R^d$ of a convex polytope and a point $\mathrm{p} \in \mathbb R^d$, then $\mathrm{p}$ is a linear combination of the vertices if the following linear system has at least one solution
$$\begin{bmatrix} | & | & & |\\ \mathrm{v}_1 & \mathrm{v}_2 & \dots & \mathrm{v}_n\\ | & | & & |\end{bmatrix} \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n\end{bmatrix} = \begin{bmatrix} | \\ \mathrm{p}\\ |\end{bmatrix}$$
We write this linear system more succinctly as $\mathrm{V} \mathrm{c} = \mathrm{p}$.
If we impose the equality constraint $1_n^T \mathrm{c} = 1$, we have an affine combination of the vertices. Hence, we have an augmented linear system of $d+1$ equations in $n$ unknowns
$$\begin{bmatrix} \mathrm{V}\\ 1_n^T\end{bmatrix} \mathrm{c} = \begin{bmatrix} \mathrm{p}\\ 1\end{bmatrix}$$
which has a unique solution if $n = d+1$. This system is underdetermined if $n > d+1$.
If we also impose nonnegativity constraints, $\mathrm{c} \geq 0_n$, then we have a convex combination of the vertices. If we find a nonnegative solution $\mathrm{c} \geq 0_n$ to the augmented linear system, then the affine combination is also a convex combination and $\mathrm{p}$ is in the convex hull of the given vertices.