Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Hi Igor, You can google for quickhull. Maybe that algorithm can be modified to compute the "conic hull"?. –  Alex Eskin Jul 12 '11 at 6:16
2  
Hi Igor. It looks like your question is really about taking the convex hull of n points in $R^{n−1}$.That is, if you can find a hyperplane $P$ for which all of the $v_i$ are on one side (presumably not difficult?) you can then consider the intersections $x_i$ with a translate $P$ of the lines parallel to the $v_i$ through $O$.The convex hull of the $x_i$ is the projectivization of the conic hull, right? So the "quickhull" algorithm mentioned by Alex Eskin should do what you want? –  Jean-Marc Schlenker Jul 12 '11 at 6:42
add comment

2 Answers

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

share|improve this answer
    
Welcome to MO! That is a very nice algorithm! Just a note--I can't figure out how to directly convert this to conic hulls, so it seems necessary to use a conic-to-convex reduction as remarked by Jean-Marc Schlenker in the comments above. (To be specific about the problem: it is possible that a non-extremal point has the largest projection onto the dual certificate, simply because it is "farthest down" that polyhedral face. I tried a couple quick fixes, but all failed. Anyway, the projection solution by Jean-Marc is fast and sufficient.) –  Matus Telgarsky Jul 13 '11 at 9:39
    
BTW I believe there is a typo in your description: primal certificates mean no extreme point, and dual certificates mean some extreme point amongst the remaining input points. –  Matus Telgarsky Jul 13 '11 at 9:42
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.