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 solu-
tions 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 en-
able fundamentally new ways of work-
ing and, in some cases, qualitatively bet-
ter results.
systems, functions, Properties
Familiar systems—one describing en-
ergy, 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 differ-
ent. We don’t quite know what these
functions are,” Parrilo says. “So what
[my] methods do, in a more or less auto-
matic 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 Brad-
ley, a professor of computer science
at the University of Colorado at Boul-
der. “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.” Par-
rilo’s contribution is important, she
says, because it makes dealing with
nonlinear systems much easier.
Phase plot of a two-dimensional dynamical system, and estimate of the region of
attraction of the stable equilibrium at the origin. this estimate was obtained by solving
a sum of squares optimization problem.
3
2
1
y
0
− 1
− 2
− 4
− 3
− 3
− 2
− 1
0
x
1
2
3
4
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 devi-
