New general-purpose optimization algorithm promises order-of-magnitude speedups on some problems

October 23, 2015 by Larry Hardesty, Massachusetts Institute of Technology
"Cutting plane" methods converge on the optimal values of a mathematical function by repeatedly cutting out regions of a much larger set of possibilities (gold sphere). Credit: Jose-Luis Olivares/MIT

Optimization problems are everywhere in engineering: Balancing design tradeoffs is an optimization problem, as are scheduling and logistical planning. The theory—and sometimes the implementation—of control systems relies heavily on optimization, and so does machine learning, which has been the basis of most recent advances in artificial intelligence.

This week, 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 "cutting-plane" algorithm, a general-purpose algorithm for solving . The 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.

But they also present a new method for applying their general algorithm to specific problems, which yields huge efficiency gains—several orders of magnitude.

"What we are trying to do is revive people's interest in the general problem the algorithm solves," says Yin-Tat Lee, an MIT graduate student in mathematics and one of the paper's co-authors. "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."

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.

Inner circle

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 for the technique: the cutting-plane method.

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.

A matter of 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, with names like submodular minimization, submodular flow, matroid intersection, and semidefinite programming. And in many of those cases, they report dramatic improvements in efficiency, from running times that scale with the fifth or sixth power of the number of variables (n5 or n6, in parlance) down to the second or third power (n2 or n3).

"This is indeed an astonishing paper," says Satoru Iwata, a professor of mathematical informatics at the University of Tokyo, who has published widely on the problem of submodular minimization. "For this problem," he says, "the running time bounds derived with the aid of discrete geometry and combinatorial techniques are by far better than what I could imagine."

Explore further: Analysis yields better optimization algorithms for engineering problems

More information: A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.

Related Stories

D-Wave and predecessors: From simulated to quantum annealing

June 23, 2014

The D-Wave computer is currently the latest link of a long chain of computers designed for the solution of optimization problems. In what sense does it realize quantum computation? We describe the evolution of such computers ...

Recommended for you

The powerful meteor that no one saw (except satellites)

March 19, 2019

At precisely 11:48 am on December 18, 2018, a large space rock heading straight for Earth at a speed of 19 miles per second exploded into a vast ball of fire as it entered the atmosphere, 15.9 miles above the Bering Sea.

Revealing the rules behind virus scaffold construction

March 19, 2019

A team of researchers including Northwestern Engineering faculty has expanded the understanding of how virus shells self-assemble, an important step toward developing techniques that use viruses as vehicles to deliver targeted ...

OSIRIS-REx reveals asteroid Bennu has big surprises

March 19, 2019

A NASA spacecraft that will return a sample of a near-Earth asteroid named Bennu to Earth in 2023 made the first-ever close-up observations of particle plumes erupting from an asteroid's surface. Bennu also revealed itself ...

Nanoscale Lamb wave-driven motors in nonliquid environments

March 19, 2019

Light driven movement is challenging in nonliquid environments as micro-sized objects can experience strong dry adhesion to contact surfaces and resist movement. In a recent study, Jinsheng Lu and co-workers at the College ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.