Conic hulls and cones

Question

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.

Answer 1

[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.

Answer 2

Question 1.

Usually, finding the convex hull means finding the vertices on each face of the convex hull; in this case, there are algorithms with running time $\mathcal O(n^{d/2})$ (where $n$ is the number of points, each in $\mathbb{R}^d$), and polytopes providing a lower bound (some of this is in the qhull material mentioned in the comments; I also found it in matousek's book "lectures on discrete geometry", specifically in the bibliographic remarks of section 5.5).

For your scenario of just finding the list of vertices, It seems like you can take $d$ out of the exponent. I'm not finding references on this which makes me a little nervous, but I'll give the algorithm in a second and you can decide how you feel about it.

Question 2.

I'm not sure what you mean because your example of the PSD cone is not polyhedral; that is, it is not an intersection of finitely many halfspaces, equivalently (by what is sometimes called the Minkowski-Weyl theorem) there does not exist a finite set of points generating it. If your $C$ were finitely generated, then I'd say run the conic hull algorithm for the union of both point sets, but I'm hoping you'll comment to clarify..

Algorithm.

The algorithm is greedy. It starts with all points in the conic hull, and greedily removes points that can be represented as conic combinations of other points. Thus it attempts to remove points $n$ times, and each iteration must try to rewrite each of the $ < n$ points using the others; it terminates when passing over the remaining vertices finds no rewrites, meaning there are $\mathcal O(n^2)$ total iterations.

Each iteration solves a linear program of the following form. The goal is to rewrite some vertex $b$ using the other remaining vertices, collected as columns into the matrix $A$ (let $|A|$ denote the number of columns). This is a linear feasibility problem $$ \textrm{find } x \in \mathbb{R}^{|A|} \textrm{ such that } Ax = b, x \geq 0. $$ A standard linear programming solver can do this in time $\mathcal O(m^{3.5} \ln(1/\epsilon))$ (where $m:=\max\{n,d\}$), where $\epsilon > 0$ will depend on how close some points are to being vertices of the cone. These algorithms will either find a satisfactory $x$, or will terminate with a dual certificate. Actually the duality is strong here; by Farkas's lemma you either can write a point in the desired way (it is in the cone), or you can separate it from the cone by a hyperplane.

To see that this algorithm is correct. First note that it never terminates when there are points that are conic combinations of others. Next note that it never removes a vertex of the conic hull, because these points can not be written as conic combinations of the other points.