A Classical Math Problem Gets Pulled into the Modern World(quantamagazine.org)
quantamagazine.org
A Classical Math Problem Gets Pulled into the Modern World
https://www.quantamagazine.org/a-classical-math-problem-gets-pulled-into-the-modern-world-20180523/
18 comments
I first came across names of authors from Control Design along Trajectories with Sums of Squares Programming https://arxiv.org/abs/1210.0888 which mainly used SoS as a tool. It seems they are doing (probably as a necessity) research on SoS itself!
The article takes a while to get to the heart of the matter, so, even though I do work in this area, it took a solid three paragraphs to realize that this was talking about sum of squares (SoS) optimization.
The whole field is interesting because a lot of problems can be phrased as optimization over non-negative polynomials (e.g. finding Lyapunov functions for systems which gives you stability results). The problem? Optimizing over non-negative polynomials is NP hard and non-convex. On the other hand, we know SoS polynomials are (a) nonnegative and (b) easy to optimize over (this is equivalent to a semi-definite program, which is a convex program and therefore “easy” to solve), so we optimize over those instead.
The problem, of course, is that there are non-negative polynomials which are not SoS polynomials, but it turns out this latter class is large enough to be useful in many cases.
The authors of the current paper show that, in fact, you do not need to solve a semi-definite program (SDP), but instead can phrase the original problem as a sequence of linear programs. To give you an idea, the best known bounds right now for SDPs are roughly O(n^3) in practice (with large leading constants) where n is the number of variables (assuming a small number of constraints), while for linear programs these bounds are O(mn^2), where m is the number of constraints.
For large n, the blowup in computational time is spectacular. To give you an idea: solving a linear program with a thousand variables and roughly ten thousand constraints takes around 3 seconds on my 2015 MBP 13”. Solving an SDP with 10 variables and ten thousand constraints takes upwards of twenty minutes (these 10k constraints are really just one equality constraint, but the matrices in the constraint are 100x100).
Of course, having structure in your SDP can make life a lot easier (it turns out that sparse SDPs are extremely fast to solve, if the sparsity pattern is a special case called Chordal sparsity). For further fun, a lot of NP-hard problems can be phrased as simple nonnegative polynomial programs, and their respective SoS relaxations form what is called a “hierarchy” of relaxations. You can get whatever accuracy you want on these problems, except that you pay with an exponential blowup of variables or constraints.
———
Apologies in advance for the (likely many) typos since I’m walking and typing this on my phone.
EDIT: one of the professors I’ve taught for has a great set of slides on SoS and respective relaxation. If you have a little bit of background in optimization, I would highly recommend them [0]!
[0]: https://stanford.edu/class/ee364b/lectures/sos_slides.pdf
The whole field is interesting because a lot of problems can be phrased as optimization over non-negative polynomials (e.g. finding Lyapunov functions for systems which gives you stability results). The problem? Optimizing over non-negative polynomials is NP hard and non-convex. On the other hand, we know SoS polynomials are (a) nonnegative and (b) easy to optimize over (this is equivalent to a semi-definite program, which is a convex program and therefore “easy” to solve), so we optimize over those instead.
The problem, of course, is that there are non-negative polynomials which are not SoS polynomials, but it turns out this latter class is large enough to be useful in many cases.
The authors of the current paper show that, in fact, you do not need to solve a semi-definite program (SDP), but instead can phrase the original problem as a sequence of linear programs. To give you an idea, the best known bounds right now for SDPs are roughly O(n^3) in practice (with large leading constants) where n is the number of variables (assuming a small number of constraints), while for linear programs these bounds are O(mn^2), where m is the number of constraints.
For large n, the blowup in computational time is spectacular. To give you an idea: solving a linear program with a thousand variables and roughly ten thousand constraints takes around 3 seconds on my 2015 MBP 13”. Solving an SDP with 10 variables and ten thousand constraints takes upwards of twenty minutes (these 10k constraints are really just one equality constraint, but the matrices in the constraint are 100x100).
Of course, having structure in your SDP can make life a lot easier (it turns out that sparse SDPs are extremely fast to solve, if the sparsity pattern is a special case called Chordal sparsity). For further fun, a lot of NP-hard problems can be phrased as simple nonnegative polynomial programs, and their respective SoS relaxations form what is called a “hierarchy” of relaxations. You can get whatever accuracy you want on these problems, except that you pay with an exponential blowup of variables or constraints.
———
Apologies in advance for the (likely many) typos since I’m walking and typing this on my phone.
EDIT: one of the professors I’ve taught for has a great set of slides on SoS and respective relaxation. If you have a little bit of background in optimization, I would highly recommend them [0]!
[0]: https://stanford.edu/class/ee364b/lectures/sos_slides.pdf
Do you have any textbooks recommendations for learning about semidefinite programming targeted at the level of, say, a math grad student?
The usual good starting point is Boyd’s Convex Optimization, for a relatively rigorous but also quite practical book. The second usual, quite a bit more rigorous case is Rockafellar’s Convex Analysis, but this one deals only with general analysis as opposed to also including applications and algorithms. I highly recommend Boyd’s book, even for a mathematician ;) since it gives a lot of great motivation and is superbly written in a relatively casual yet clear style.
You can also find Ben-Tal & Nemirovski's lecture slides here:
https://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
Check BOAZ BARAK's Harvard class for a references list
Nice summary, thanks!
> iron-clad proof that drone aircraft and autonomous cars won’t crash into trees or veer into oncoming traffic
Utter bollocks.
Utter bollocks.
The example application is really dumb. The challenge for autonomous driving isn't so much planning a course through the world, it's creating a model of the world in the first place.
Agreed, the example presented in the article isn’t even an (actually useful) application of the original problem. SoS is useful for generating certificates of the stability of controls, rather than generating actual trajectories. That latter part is relatively easy via some simple heuristics.
Point being: it is possible to generate trajectories using SoS, but we have much better algorithms to do that. Rather, it’s hard to certify that controls which follow those trajectories are stable, esp. as they become more complicated than simple ones whose stability is easily proven (like PID, for example).
Point being: it is possible to generate trajectories using SoS, but we have much better algorithms to do that. Rather, it’s hard to certify that controls which follow those trajectories are stable, esp. as they become more complicated than simple ones whose stability is easily proven (like PID, for example).
I see, so there's no point in addressing any part of the problem, that isn't the most important part.
Interesting potential applications in Robust Optimization
The article did not seem clear to as to whether polynomial (non)negativity is needed to FIND THE BEST PATH, or to know if there IS a valid path.
Both are true. If there is such a path, then it can be found and is returned, otherwise a verifiable certificate that there is no such path is returned.