## New, faster cutting-plane optimization algorithm

##### 23 October 2015

The theory—and sometimes the implementation—of control systems relies heavily on optimization (e.g., earlier post)—as do many other aspects of engineering and design (e.g., earlier post). At the IEEE Symposium on Foundations of Computer Science, a trio of present and past MIT graduate students won a best-student-paper award for a new general-purpose algorithm for solving optimization problems.

The new “cutting-plane” method algorithm improves on the running time of its most efficient predecessor, and the researchers offer some reason to think that they may have reached the theoretical limit. They also present a new method for applying their general algorithm to specific problems, which efficiency gains of several orders of magnitude.

What we are trying to do is revive people’s interest in the general problem the algorithm solves. Previously, people needed to devise different algorithms for each problem, and then they needed to optimize them for a long time. Now we are saying, if for many problems, you have one algorithm, then, in practice, we can try to optimize over one algorithm instead of many algorithms, and we may have a better chance to get faster algorithms for many problems.

—Yin-Tat Lee, co-author

Lee is joined on the paper by Aaron Sidford, who was an MIT graduate student in electrical engineering and computer science when the work was done but is now at Microsoft Research New England, and by Sam Wong, who earned bachelor’s and master’s degrees in math and electrical engineering and computer science at MIT before moving to the University of California at Berkeley for his PhD.

Cutting plane. Optimization problems are generally framed as trying to find the minimum value of a mathematical function, called a “cost function.” In car design, for example, the cost function might impose penalties for weight and drag but reward legroom and visibility; in an algorithm for object detection, the cost function would reward correct classification of various objects and penalize false positives.

At a very general level, finding the minimum of a cost function can be described as trying to find a small cluster of values amid a much larger set of possibilities. Suppose that the total range of possible values for a cost function is represented by the interior of a circle. In a standard optimization problem, the values clustered around the minimum value would then be represented by a much smaller circle inside of the first one—but you don’t know where it is.

Now pick a point at random inside the bigger circle. In standard optimization problems, it’s generally possible to determine whether that point lies within the smaller circle. If it doesn’t, it’s also possible to draw a line that falls between it and the smaller circle.

Drawing that line cuts off a chunk of the circle, eliminating a range of possibilities. With each new random point you pick, you chop off another section of the circle, until you converge on the solution.

If you represent the range of possibilities as a sphere rather than a circle, then you use a plane, rather than a line, to cut some of them off. Hence the name: cutting-plane.

In most real optimization problems, you need a higher-dimensional object than either a circle or a sphere: You need a hypersphere, which you cut with a hyperplane. But the principle remains the same.

Despite the key role that cutting plane methods have played historically in both combinatorial and convex optimization, over the past two decades progress on improving both the theoretical running time of cutting plane methods as well as the complexity of using cutting plane methods for combinatorial optimization has stagnated. The theoretical running time of cutting plane methods for convex optimization has not been improved since the breakthrough result by Vaidya in 1989. Moreover, for many of the key combinatorial applications of ellipsoid method, such as submodular minimization, matroid intersection and submodular flow, the running time improvements over the past two decades have been primarily combinatorial; that is they have been achieved by discrete algorithms that do not use numerical machinery such as cutting plane methods.

In this paper we make progress on these classic optimization problems on two fronts. First we show how to improve on the running time of cutting plane methods for a broad range of parameters that arise frequently in both combinatorial applications and convex programming (Part I). Second, we provide several frameworks for applying the cutting plane method and illustrate the efficacy of these frameworks by obtaining faster running times for semidefinite programming, matroid intersection, and submodular flow (Part II). Finally, we show how to couple our approach with the problem specific structure and obtain faster weakly and strongly polynomial running times for submodular function minimization, a problem of tremendous importance in combinatorial optimization (Part III). In both cases our algorithms are faster than previous best by a factor of roughly Ω(n2).

—Lee et al.

Time. Theoretical computer scientists measure algorithms’ running times not in seconds or hours, but in the number of operations required, relative to the number of elements being manipulated. With cutting-plane methods, the number of elements is the number of variables in the cost function—the weight of the car, the cost of its materials, drag, legroom, and so on. That’s also the dimension of the hypersphere.

With the best general-purpose cutting-plane method, the time required to select each new point to test was proportional to the number of elements raised to the power 3.373. Sidford, Lee, and Wong get that down to 3.

But they also describe a new way to adapt cutting-plane methods to particular types of optimization problems such as submodular minimization, submodular flow, matroid intersection, and semidefinite programming. And in many of those cases, they report significant improvements in efficiency, from running times that scale with the fifth or sixth power of the number of variables (n5 or n6) down to the second or third power (n2 or n3).

Our results demonstrate the power of cutting plane methods in theory and possibly pave the way for new cutting plane methods in practice. We show how cutting plane methods can continue to improve running times for classic optimization problems and we hope that these methods may find further use. As cutting plane methods such as analytic cutting plane method are frequently used in practice, these techniques may have further implications.

—Lee et al.

This is indeed an astonishing paper. For this problem, the running time bounds derived with the aid of discrete geometry and combinatorial techniques are by far better than what I could imagine.

—Professor Satoru Iwata, University of Tokyo, who has published widely on the problem of submodular minimization

Resources