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. Quantum information theorists have used them to describe the mysterious property known as entanglement — in which the states of subatomic particles 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 equation 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.”
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. Quantum information theorists have used them to describe the mysterious property known as entanglement — in which the states of subatomic particles 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 equation 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.”
