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