news

Science;|;DOI: 10.1145/1866739.1866745
Gary;Anthes
nonlinear systems
made easy
Pablo Parrilo has discovered a new approach to convex optimization
that creates order out of chaos in complex nonlinear systems.

ImaGINe YoU aRe hiking in a com- plex 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.

PHO TOGRAPH B Y PATRICK GILLOOLY

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

new algorithms devised by Pablo Parrilo, an mit professor of electrical engineering and computer science, have made working with nonlinear systems both easier and more efficient.

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