3 follow-up and comments

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.

2 fixed tags
1

# Conic hulls and cones

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.