Convexity and efficient algorithms.

Question

[Edit 21 July 2011: I edited the question to ask for more examples]

This question is asking for documented discussion of or more examples of a heuristic observation.

Some mathematical problems that admit efficient algorithms appear to be convex in nature. I'm thinking of linear and semi-definite programs and various combinatorial problems that reduce to these.

First, are there other families of problems that admit efficient algorithms for the convex/conjunctive case? (I would be particularly grateful for examples of decision procedures for logical theories) Second, I would appreciate pointers to articles or sections of articles that discuss an opinion such as "lurking under a lot of efficient algorithms is a convex structure."

[Edit, 21 July 2011: Added the following.]

I would like to add some clarifications. I'm sorry I didn't include them earlier. I am interested in logical decision problems. It appears to me that efficient decision procedures exist for the conjunctive fragment of several logical problems. Here are two examples.

Efficient solvers for quantifier-free first order theories (such as SMT solvers for equality, equality with uninterpreted functions, difference arithmetic, etc.) typically have an efficient solver for the conjunctive fragment and use various techniques to cope with disjunction and negation. In static analysis of programs, the commonly used (and efficient) abstractions are based on integer intervals, affine equalities, octagons or polyhedra. In predicate-based abstraction and program verification, there is something called the Cartesian abstraction, which is intuitively about having conjunctions of predicates rather than arbitrary Boolean combinations. All these cases appear to me to be about gaining efficiency by exploiting the conjunctive fragment of the problem.

The conjunctive fragment of the first order theory of linear, real arithmetic can express convex polyhedra. This is why I originally asked about convex programming.

I am interested to know of other problems or examples where efficient solutions (in the theoretical or practical sense) are based on a convex or conjunctive sub-problem. If there is another general condition (Suresh mentioned sub-modularity) please mention it and problems whose solutions exploit that condition.

Answer 1

Regarding Question 1.

The examples you gave, linear programs and SDPs (both of which are linear programs over convex cones), can be generalized to convex programs: minimization of a convex function over a convex feasible set. Since you are looking for 'other families of problems' that are efficient thanks to the presence of convexity, the natural thing to drop is the convex function part, and just look at convex sets. This is the realm of convex geometry, and here there are lots of algorithms.

One of the standard favorites is:

Martin Dyer, Alan Frieze, Ravi Kannan. A Random Polynomial Time Algorithm For Approximating The Volume Of Convex Bodies.

The difficulty here is that the dimension is (at it should be) a part of the input; on the other hand, a naive algorithm samples points on the grid, which sticks the dimension in the exponent of the running time. The reason why convexity helps is intuitive: convexity gives separation results, things like Farkas's lemma which say that a point is either in a closed convex cone, or you can separate them with a hyperplane. The relevance here is say that you know some point is in the convex body, whereas some constellation of points around it is not in the body: from here you can lop off a huge piece of the input and never bother sampling from it. Perhaps I should clarify that the above paper does the estimation by producing a nice sampling algorithm within the body (both of which are useful). Last I checked, there is still no deterministic analog to this; I just googled to see if the status has changed (seems not), and was fed these notes that have a few references which may interest you: http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf . I never took this class and only looked briefly, so my apologies if there are some problems, but the references there at least seem to have value to you.

For more examples of algorithms exploiting convex geometry, one place to look is the 'Bibliography and Remarks' subsections concluding each section (of each chapter!) of Jiri Matousek's book "Lectures on Discrete Geometry".

Another thing that gets cited a lot, and which seems to have topics for you (but I've never looked beyond the table of contents myself; Matousek on the other hand is .. in my other hand), is "Geometric algorithms and combinatorial optimization" by Grotschel, Lovasz, and Schrijver. (Yes, that Lovasz.)

I think these references have a lot for you so I'll move onto the next question.

Regarding Question 2.

While it is definitely true that convexity is powerful, I have not seen a comment like the one you seek, and I think people are very careful to communicate such a sentiment.

I have an anecdote on this. One way people 'inject' convexity into problems is to simply.. approximate/model them with something convex. (For example: replacing rank constraints with norms on the matrix, replacing integers (nonconvex and not even connected) with convex sets of reals.) A go-to text for this stuff is Boyd & Vandenberghe's "Convex Optimization". But once I was watching Boyd's videos, and someone gave him the "is convex = efficient" question, and he immediately said SVD. Note that SVD can be written as a rank constrained minimization problem. Anyway, my point is that even Boyd is very quick to correct a comment like this.

That said, I have a desire to share two places where I was personally surprised by convex structures (experts can roll their eyes and doze here). The first are so called 'sum of squares' problems, which are minimization problems over nonconvex polynomials. Thanks to the interpolation properties of polynomials, you can rewrite these as SDPs. There are some beautiful course notes on this topic by Pablo Parrilo; you can find that and more info on his web page and some other info in this MO post by Noah Stein: https://mathoverflow.net/questions/32533/is-all-non-convex-optimization-heuristic/32634#32634 .

Another beautiful place is in exponential families. Now, this is all "obvious" once you realize these are solutions to max entropy (a convex optimization problem), but it's amazing how much convex structure informs the behavior of exponential families (a reference I like here is Wainwright and Jordan's book on graphical models). This in turn gives one justification for some of the things people do with this sort of modeling.