Solving convex programs defined by separation oracles?

Question

General question: What software can solve convex programs defined by a separation oracle?

The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I would program a function that, on input a point, would return whether or not that point is in the feasible set and, if the point is not, also produce an inequality separating the given point from the feasible set. I'd love to be able to feed this function into something like cvxopt or mosek and maximize a concave function.

More specifically, the polytope I'm interested in is the convex hull of the indicators of basis of a matroid. We assume that we have an efficient independence oracle for the matroid, meaning that we obtain a separation oracle for the polytope via the techniques in Testing Membership in Matroid Polyhedra by Cunningham.

I would be interested in the following special case:

Specific Question: What software / algorithms are practically useful for maximizing a concave function over the spanning tree polytope?

Edit: It appears that the correct word to use for OR is "cutting plane," rather than "separation oracle." These notes overview some cutting plane methods.

Background: I am interested in implementing the algorithm in this paper.

I am aware that the ellipsoid method can be in theory used for this, but as I understand it that algorithm is not practically useful. I know that the number of spanning trees can be calculated efficiently without this; I'm just curious about the effectiveness of this particular algorithm, and would like to compare it to this case where the correct answer can be calculated.

Update: We reached out to Nima Anari, and he suggested using something like Frank-Wolfe since the specific polytopes I was interested in had efficient linear optimization oracles. There is a little bit of funny business guaranteeing convergence, since the curvature of the entropy function blows up near parts of the boundary, but initializing with a "random" point in the interior worked well in practice. The code is here: https://github.com/LorenzoNajt/EntropyCounting/blob/master/README.md

Answer 1

The algorithm you are describing is Kelley's Cutting-Plane Method. Wikipedia gives a good description, and the original paper can be found here.

Note that this differs from the cutting plane methods described in the note that you link. These 'ellipsoid method like methods' are also called cutting planes methods.

The difference is that with Kelley's method, you build an outer approximation of the feasible set, while with the ellipsoid method, you cut of sub-optimal regions of the feasible set. As a rule of thumb, the first one is only efficient in practice, and the second one is only efficient in theory.

Your problem is of the general form \begin{align} \max &~f(x)\\ Ax &= b\\ x &\ge 0. \end{align}

You can rewrite this to \begin{align} \max &~t\\ g(x,t) &\le 0 \\ Ax &= b\\ x &\ge 0\\ t &\in \mathbb{R}, \end{align} with $g(x,t) = t-f(x)$, which is a joint convex function in $(x,t)$.

Kelley's method would first remove $g(x,t) \le 0$ and solve the remaining linear program. Then, you find a cutting plane for $g(x,t)$, add it, and solve again. Repeat until the point that you find is (almost) feasible for the original problem. Because you are building an outer approximation, this point must be optimal.

Solving the linear programs can be done with software such as CPLEX and Gurobi. Kelley's method is easily implemented as a simple loop, or as a callback in CPLEX or Gurobi. In his blog, Paul Rubin describes how you can do this.