Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next question is: suppose I have a number of vectors $v_1, \dotsc, v_n,$ as before, and a convex cone $C.$ I want to find the conic hull of $\{v_1, \dotsc, v_n\} \cup C.$ In case it matters, in my application $C$ is the semidefinite cone. By "compute the conic hull", I mean: I want to find the subset of the $v_i$ on the boundary of the hull.
EDIT Thanks for all the comments. It is certainly true that the conic hull is equivalent to the intersection with a plane, and as @Will pointed out, the only problem is finding the plane. In the PSD case, we know that identity is PSD, so this gives us a choice of planes.
As for the algorithm, I had come up with @Matus' algorithm, but was not sure (and still am not) that this is the most efficient, since it looks like there is a lot of recomputation. The fact that the PSD cone is not a polyhedral cone is very true. Notice that you can still ask for the extremal points from the original set, and in fact, the same algorithm works, except that instead of solving a linear program at each step, we need to solve a semidefinite program, which hurts a bit, but is certainly tractable for small dimension.
If you ask for the full convex hull, I am not at all sure of how the answer should even look like, since one will need to describe the "exposed" pieces of the cone. Surely mankind has wondered about this is in the context of, eg, the convex hull of a collection of disks in the plane, or some such.
Best Answer
[Edited: previous version was flaky, sorry; also edited per Matus]
There is a variant of Matus's approach that takes $O(nT_A)$ work, where $A\le n$ is the size of the answer, that is, the number of extreme points, and $T_A$ is the work to solve an LP (or here an SDP) as Matus describes, but for $A+1$ points instead of $n$.
The algorithm is: (after converting from conic to convex hull) maintain an output set $S$, that starts empty, and test each point $v_i$ against $S$ one by one. Solve the LP (or SDP) as Matus describes. If $v_i$ is proven to be in the convex hull of $S$, discard it. Otherwise, the dual certificate gives a direction (at least in the LP case, and something similar should apply in the SDP case) perpendicular to that separating hyperplane, such that the input point that is extreme in that direction is not already in $S$. (While $v_i$ is not in the convex hull of $S$, it may not be extreme itself.) Find that input point and add it to $S$.
Testing each of the $n$ points costs $T_A$, and the $O(n)$ work for finding an extreme point in a given direction yields a new member of $S$, so such tasks need $O(nA)\le O(nT_A)$ work.
This trick and related ones appeared here ("More output-sensitive..."); the notes for the paper give pointers to some related work.