A century ago, the great mathematician David Hilbert posed a probing question in pure mathematics. A recent advance in optimization theory is bringing Hilbert’s work into a world of self-driving cars.

Long before robots could run or cars could drive themselves, mathematicians contemplated a simple mathematical question. They figured it out, then laid it to rest — with no way of knowing that the object of their mathematical curiosity would feature in machines of the far-off future.

The future is here now. As a result of new work by Amir Ali Ahmadi and Anirudha Majumdar of Princeton University, a classical problem from pure mathematics is poised to provide iron-clad proof that drone aircraft and autonomous cars won’t crash into trees or veer into oncoming traffic.

“You get a complete 100-percent-provable guarantee that your system” will be collision-avoidant, said Georgina Hall. a final-year graduate student at Princeton who has collaborated with Ahmadi on the work.

The guarantee comes from an unlikely place - a mathematical problem known as "sum of squares." The problem was posed in 1900 by the great mathematician David Hilbert. He asked whether certain types of equations could always be expressed as a sum of two separate terms, each raised to the power of 2.

Mathematicians settled Hilbert's question within a few decades. Then, almost 90 years later, computer scientists and engineers discovered that this mathematical property - whether an equation can be expressed as a sum of squares - helps answer many real-world problems they'd like to solve.

"What I do uses a lot of classical math from the 19th century combined with very new computational math," said Ahmadi.

Yet even as researchers realized that the sum of squares could help answer many kinds of questions, they faced challenges in implementing the approach. The new work by Ahmadi and Majumdar clears away one of the biggest of those challenges - bringing an old math question squarely to bear on some of the most important technological questions of the day.

Positivity Guaranteed

What does it mean for something to be a sum of squares? Take the number 13. It's the sum of two squares: 22 and 32. The number 34 is the sum of 32 plus 52.

Instead of numbers, Hilbert’s question — the 17th of 23, he posed at the opening of the 20th century — has to do with polynomial expressions like 5x2 + 16x + 13. These kinds of polynomials can sometimes be expressed as sums of squares, too. For example, 5x2 + 16x + 13 can be rewritten as (x + 2)2 + (2x + 3)2.

When an expression is a sum of squares, you know that it’s always nonnegative. (Because anything squared is positive or zero, and the sum of positive numbers is a positive number.) Hilbert wanted to know if it works the other way around: if all nonnegative polynomials can be expressed as a sum of squares of rational functions. In 1927 the mathematician Emil Artin proved that Hilbert’s conjecture is true.

This relationship turns out to be quite useful. If you’re handed a complicated polynomial — one with dozens of variables raised to high powers — it’s not easy to determine straight away whether it’s always nonnegative. “Some polynomials are obviously nonnegative, others are not. It’s hard to test whether they’re always nonnegative,” said Ahmadi.

But once you show that the same polynomial can be expressed as a sum of squares, then you know nonnegativity follows as a consequence. “Sum of squares gives you a nice certificate of positivity,” said Pablo Parrilo, a computer scientist and engineer at the Massachusetts Institute of Technology who was influential in bringing the sum of squares question into the applied realm.

Knowing whether a polynomial is always nonnegative might seem like a mathematical triviality. But a century after Hilbert asked his question, polynomial nonnegativity has turned out to answer applied problems that affect us all.

The Best Way

The sum of squares meets the real world in the field of optimization. Optimization theory is concerned with finding the best way to do something amid constraints — like finding the best route to work given the current traffic conditions and a stop you need to make along the way. Scenarios like these can often be distilled into polynomial equations. In such cases, you solve, or “optimize” the scenario, by finding the minimum value taken by the polynomial.

Finding the minimum value of a polynomial with many variables is hard: There’s no straightforward high-school-style algorithm for computing the minimum value of complicated polynomials, and these same polynomials are not easy to graph.

Because the minimum value of a polynomial is hard to compute directly, researchers infer it by other means. And this is where nonnegativity, and the question of whether a polynomial is a sum of squares, comes in. “Certifying nonnegativity is really the heart of all optimization problems,” said Rekha Thomas, a mathematician at the University of Washington.

One way to find the minimum value is to ask yourself: What’s the most I can subtract from a nonnegative polynomial before it turns negative somewhere? In answering this question you might test different values — can I subtract 3 from the polynomial such that it’s still nonnegative? What about 4? Or 5? As you repeat this procedure, you’re interested in knowing at each step whether the polynomial is still nonnegative. And the way you check that is by checking whether the polynomial can still be expressed as a sum of squares.

“The thing you want to ask is, ‘Is the polynomial nonnegative?’ The problem is, answering nonnegativity is hard with more variables,” said Ahmadi. “That’s why we use the sum of squares as a surrogate for nonnegativity.”

Once researchers know the minimum — which is, remember, the optimal value of the polynomial — they can use other methods to identify the inputs that lead to that value. Yet in order for nonnegativity to help solve optimization problems, you need a way of quickly computing whether a polynomial is equal to a sum of squares. And it took 100 years after Hilbert’s question for researchers to figure that out.

Source: Quanta Magazine