Nonlinear thinker: Making sense of previously insoluble problems

January 29, 2010 by Larry Hardesty
Pablo Parrilo, the Finmeccanica Career Development Professor at MIT’s Laboratory for Information and Decision Systems. Photo: Patrick Gillooly

If an airplane is cruising along and raises the flaps on its wings a degree or two, it will tilt upward. If it raises the flaps twice as much, it will tilt upward about twice as much. But if it tilts upward too far — generally more than 15 degrees — the airflow over the wings becomes chaotic, and anything can happen: the nose might jerk up, or it might jerk down; one wing could dip, or the plane could start to spin. In technical terms, within the normal operational range, airplane control is linear; outside that range, it’s nonlinear.

Engineers prefer linear systems because they’re much easier to work with mathematically, but unfortunately, we live in a largely nonlinear world. So a lot of research is aimed at finding linear characterizations of the behavior of nonlinear systems. That research usually requires a great deal of mathematical insight and trial and error, and even when it’s successful, the results may be impossible to generalize to other cases.

Pablo Parrilo, the Finmeccanica Career Development Professor at MIT’s Laboratory for Information and Decision Systems, has developed a new set of techniques that make it easier to get a handle on nonlinear systems. Moreover, in many cases, his techniques provide algorithms — step-by-step instructions — for analyzing those systems, taking away much of the guesswork. “The impact he’s had has been huge. Huge,” says Russ Tedrake, a robotics researcher at MIT’s Computer Science and Artificial Intelligence Lab. Tedrake has adapted Parrilo’s techniques to create novel control systems for walking and flying robots, and major engineering companies have used them in the design of aircraft and engines. theorists have used them to describe the mysterious property known as — in which the states of become dependent on each other — and biologists have used them to make sense of the complicated chemical signaling pathways found in cells.

“It’s a great step forward,” says John Harrison, a principal engineer at Intel who has used Parrilo’s techniques to verify that Intel’s chips will do what they’re supposed to. “It’s really a whole new weapon in the arsenal of nonlinear reasoning.”

Connecting the dots

The set of linear problems is relatively narrow and well-characterized, while the set of nonlinear ones is huge and varied. Most people were exposed to both types in algebra class. A mathematical function with two variables is linear if its graph is a straight line; it’s nonlinear if its graph is a curve. The equation y = x, for instance, is linear; the equation y = x2 — whose graph is a parabola centered at the origin — is not.

With more than two variables, nonlinear equations can get immensely complicated. The three-dimensional graph of a three-variable nonlinear equation could look like a mountain range, with erratic undulations and depressions. And the nonlinear equations that arise in engineering and physics might be more complex still, with 10 or 15 variables.

Sometimes, however, it’s enough to know something about the broad topographical features of a nonlinear function without getting too bogged down in the details. In the case of a three-dimensional graph, a depression — a part of the graph that looks like a bowl — could have important real-world implications. The point at the bottom of the bowl might represent the state of some physical system, and the slope of the bowl’s sides would indicate that the system tends to move toward that state.

Suppose, for instance, that a plane flying in direction A at altitude B and velocity C needs to change course so that it’s flying in direction X at altitude Y and velocity Z. The first state of the plane can be thought of as a point in three-dimensional space — A, B, C — and the desired course correction — X, Y, Z — as a second point. If you have a nonlinear equation that describes the behavior of planes in flight, the question becomes, Does the second point lie at the bottom of a bowl?

Square one

Parrilo provides a way to answer that type of question without actually solving nonlinear equations. To see how his approach works, consider the equation x2 - 2xy + y2 < 0. Can you find values of x and y that make that true? You can’t. You may remember from algebra class that x2 - 2xy + y2 is another way of writing (x - y)2. Since the square of a negative number is positive, and the square of a positive number is positive, (x - y)2 is always positive.

Parrilo has developed a battery of techniques for rewriting complicated nonlinear equations — much more complicated than x2 - 2xy + y2 < 0 — as “sums of squares” — where a “square” is an expression like (x - y)2. A sum of squares is always greater than or equal to zero. But that means that wherever it equals zero, it has reached a “global minimum” — the bottom of a bowl.

Parrilo’s approach works only with particular types of equations. But generally, the properties that make equations susceptible to his approach are properties common to mathematical models of physical systems. “He’s very much a theorist,” says Tedrake, “but he’s thought a lot about the details that make that theory work.”

Harrison agrees. In 1994, he explains, Intel released a Pentium chip whose circuit design was slightly incorrect: under certain circumstances, it actually gave the wrong answers to some calculations. Since then, Harrison says, Intel has performed “formal verification” of some of its designs. “We create a formal model of the design and really prove as a mathematical theorem that it satisfies some property." Using Parrilo’s techniques, Harrison has developed software that proves those theorems automatically. “I spent some time before I discovered Pablo’s work casting around trying to find techniques,” Harrison says. “There’s a literature that goes back 50 years, and I spent a long time combing through this literature, trying to see if any of these so-called constructive results were useful as real algorithms. And generally the results were very disappointing.” Parrilo’s method, by contrast, “is really remarkably good,” Harrison says. “It’s really great.”

Explore further: Mathematician Receives Grant for Quantum Mechanics Research

Related Stories

Quantum computing may actually be useful, after all

October 9, 2009

( -- In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete problems ...

Solving big problems with new quantum algorithm

November 9, 2009

( -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster than conventional ...

Eureqa, the robot scientist (w/ Video)

December 7, 2009

( -- A new program, Eureqa, takes raw data and formulates scientific laws to suit, and it is available by free download to all scientists.

Recommended for you


Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (1) Jan 29, 2010
It is so nice to see true "genius" being both useful AND appreciated.
not rated yet Jan 29, 2010
Hopefully ill learn more about these techniques at some point in my physics education.
Jan 29, 2010
This comment has been removed by a moderator.
not rated yet Jan 29, 2010
Most number crunching and moving boundary conditions ask for numerical solutions with computer simulations, and many times you can come up with useful answers.
Sometimes or most of the time fitting complex physics in beautiful math is just a nice exercise.
Other times it is very rewarding.
It is good science to know when to go computer and when to go differential equations.
not rated yet Jan 31, 2010
I'm just sci-fi fan so pardon anything silly. Now,regarding (x-y)2. Metaphorically speaking, Suppose x represents the positive universe/charge (matter) and y represents the negative universe/charge (anti-matter) and the square represents the mirror image (mirror opposite: -antimatter +matter) of our whole universe (+matter -antimatter), then the overall tone of everything that exists is positive! YAY!!!

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.