Communications of the ACM

News

Nonlinear Systems Made Easy

By Gary Anthes
Communications of the ACM, January 2011, Vol. 54 No. 1, Pages 17-19
10.1145/1866739.1866745
Comments

Imagine you are hiking in a complex and rugged environment. You are surrounded by hills and valleys, mountains, shallow ditches, steep cliffs, and lakes. Nothing about the ground immediately around you, or your current direction, tells you much about where you will end up or what might lie in between.

Now imagine you are walking on the inside surface of a huge, smoothly shaped bowl. You can see the bottom of it, and even a few steps over the surface of the bowl tell you much about its shape and dimensions. There are no surprises.

Pablo Parrilo, a professor of electrical engineering and computer science at Massachusetts Institute of Technology (MIT), has found a way to remake the mathematical landscapes of complex, nonlinear systems into predictable smooth bowls. He has constructed a rare bridge between theoretical math and engineering that extends the frontiers of such diverse disciplines as chip design, robotics, biology, and economics.

Nonlinear dynamical systems are inherently difficult, especially when they involve many variables. Often they act in a linear fashion over some small region, then change radically in some other region. Water expands linearly as it warms, then explodes in volume at the boiling point. An airplane rises smoothly and ever more steeply—until it stalls. Understanding these systems often requires a great deal of prior knowledge, plus a painstaking combination of trial and error and modeling. Sometimes the models themselves are so complex their behavior can't be predicted or guaranteed, and running realistic models can be computationally intractable.

Parrilo developed algorithms that take the complex, nonlinear polynomials in models that describe these systems and—without actually solving them—rewrites them as much simpler mathematical expressions represented as sums of squares of other functions. Because squares can only be positive, his expressions are guaranteed to be greater than zero—the bottom of a "bowl"—and relatively straightforward to analyze via conventional mathematical tools such as optimization techniques.

Parrilo's transformed equations are "convex," like bowls. Convexity in mathematics essentially means that a function is free of undulations that form local minima and maxima. "It means that if you know something about two points, then you know what's going to happen in the middle," Parrilo says.

"The reason that the convexity property is so important is that it allows us to make global statements from local properties," Parrilo says. "You can sometimes give bounds on the quantity you are trying to find; essentially, you use the convexity of a function as a way of establishing whatever conclusion you want to make." In other words, one can deduce a great deal about a bowl from visiting just a few points on it.

Once Parrilo has derived the sums-of-squares equations, the equations are solved (a minimum is found) via an optimization technique called semidefinite programming, a relatively recent extension of linear programming that works on matrices representing convex functions. (The algorithms for both steps are contained in a MATLAB toolbox called Sostools, which is available at http://www.mit.edu/~parrilo/sostools/.)

While solving the original nonlinear equations is often NP-hard, Sostools can find useful bounds or even exact solutions from the convex sums-of-squares equations in polynomial time, Parrilo says. In fact, his techniques can improve efficiency so greatly—for researchers as well as their computers—that they enable fundamentally new ways of working and, in some cases, qualitatively better results.

Back to Top

Systems, Functions, Properties

Familiar systems—one describing energy, for example—are often defined by functions in which equilibrium exists at some minimum point, with the systems moving toward that point along smooth trajectories. "But with many systems, like a biological system, it is very different. We don't quite know what these functions are," Parrilo says. "So what [my] methods do, in a more or less automatic way, is find a function that has the properties of an energy function."

Because nonlinear systems are so difficult, system designers and researchers often take the easy but wrong way out, says Elizabeth Bradley, a professor of computer science at the University of Colorado at Boulder. "Linear systems dominate our education as engineers solely because they are easy," Bradley says. "But that leads to the lamppost problem. People look around the linear lamppost even though the answers aren't there." Parrilo's contribution is important, she says, because it makes dealing with nonlinear systems much easier.

John Harrison, a principal engineer at Intel, knows what it's like to wrestle with nonlinear systems. He develops formal proofs for the correctness of designs for floating-point arithmetic circuits. The idea is to prevent a recurrence of the floating-point division bug in the Pentium chip that cost Intel nearly $500 million in the mid-1990s. The tools he had used to do that, before discovering Parrilo's sums of squares and semidefinite programming, were complex, time consuming, and required huge amounts of computer time, he says. Now his formal verifications typically run in "tens of seconds" rather than "many minutes or even hours," Harrison says.

Harrison doesn't have to find exact solutions to his equations, but can work with proofs that a polynomial will remain within certain acceptable bounds over a specified range. That's exactly what Parrilo's method does, he says. "The key," he adds, "is the ability to certify the result formally, otherwise various less rigorous methods could be used."

The broad scope of Parrilo's concepts may mean that formal methods, which can mathematically prove or verify the correctness of designs, but usually with some difficulty, will propagate more widely, Harrison predicts.

Back to Top

Specifying a Robot's Bounds

A robot walking slowly can be controlled by a relatively simple system that works linearly, says Russ Tedrake, associate professor of electrical engineering and computer science at MIT. But if the robot walks too fast or encounters some kind of disturbance, nonlinear factors kick in and the robot's behavior becomes much more difficult to predict and control. Tedrake is using Parrilo's sums-of-squares and semidefinite programming techniques to rigorously specify the bounds within which the robot won't fall. He has done the same to specify when a linear control system for a flying robot will become unable to keep the machine on its desired flight path.

Tedrake builds models of his robots' flight consisting of very complex differential equations. From those, there are well-established tools for defining workable flight paths, and given those trajectories, there are good linear systems for controlling the robot even when it deviates from the desired trajectory. But if it veers too far off, nonlinear terms can take over and the robot may crash. But now, using Parrilo's tools, Tedrake can generate "proofs of stability" for these nonlinear terms that in essence define an envelope within which the robot will converge back to its nominal trajectory. "Proving stability in this way is important for the techniques to be accepted in many applications," he says.

"This opens up a rigorous way of thinking of nonlinear systems in ways not possible a few years ago," Tedrake says. "It used to be you had to be very innovative and creative to come up with a proof of stability for nonlinear systems." Now, he says, his results are more reliable and rigorous, and he can more easily devise and evaluate alternate flight paths and control systems.

Like Harrison, Tedrake hails an efficiency breakthrough in Parrilo's methods. Instead of laboriously verifying the stability of thousands of isolated trajectories, he can now work with just a few "regions of stability," he says.

Parrilo's work is noteworthy for the specific techniques and algorithms he has developed, but, at a higher level, it is impressive for its reach, says John Doyle, a professor of control and dynamical systems at the California Institute of Technology. Doyle points out that researchers have labored for decades to understand and control complex nonlinear systems, such as those that run computers, manage networks, and guide airplanes. Many useful tools—such as formal verification of software and hardware—and disciplines—such as robust control—have emerged from this work. But, Doyle says, there has not been a "unified approach" to the problem of anticipating and preventing unintended consequences in systems that are "dynamic, nonlinear, distributed and complex."

Now, Parrilo has made a giant step toward developing just such a unified approach, Doyle says. "What Pablo said was, 'Here is a systematic way to pursue these problems and, oh, by the way, a lot of these tricks that you guys have come up with over 30 years—in a whole bunch of fields that we didn't see as related—are all special cases of this strategy.' What he did is connect the dots."

Parrilo enables one to "automate the search for proofs," Doyle says. He explains it this way: "You have a set of bad behaviors that you don't want the system to have, and you have a model of the system. You want to prove that the two sets don't intersect. Pablo recognized that there was a sort of universal way to attack this set non-intersection problem."

---

Pablo Parrilo has constructed a bridge between theoretical math and engineering that extends the frontiers of chip design, robotics, biology, and economics.

---

As for the breadth of Parrilo's thinking, Doyle says, "The mathematicians think of Pablo as one of their own, and so do the engineers."

 Further Reading

Boyd, S. and Vandenberghe, L.
Convex Optimization, Cambridge University Press, Cambridge, U.K, 2004.

Dekker, S.
Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization (Ph.D. dissertation), California Institute of Technology, Pasadena, CA, May 2000.

Parrilo, P.A.
Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming Ser. B 96, 2, 2003.

Parrilo, P.A.
Sum of squares optimization in the analysis and synthesis of control systems, 2006 American Control Conference, Minneapolis, MN, June 14–16 2006.

Parrilo, P.A. and Sturmfels, B.
Minimizing polynomial functions, Cornell University Library, March 26, 2001, http://arxiv.org/abs/math.OC/0103170.

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.

---

No entries found