SumOfSquares.jl icon indicating copy to clipboard operation
SumOfSquares.jl copied to clipboard

[WIP] Add support for exact newton polytope #2

Open blegat opened this issue 9 years ago • 3 comments

Closes #2

  • [ ] Multipartite
  • [x] Exact Newton Polytope
  • [ ] Tests

blegat avatar Nov 25 '16 14:11 blegat

Note: motzkin polynomial is a nice test example

blegat avatar Aug 08 '18 17:08 blegat

This would be a great feature showing off different Julia packages/interfaces working together. Also useful. For most polynomial problems that would be feasible to solve, the size wouldn't be too large for a good polyhedral computation package like CDDLib to handle, right?

chriscoey avatar Mar 29 '19 03:03 chriscoey

Note that in YALMIP, this is done by default but it does not precompute the H-representation but rather get separating hyperplanes lazily by solving LP's in the V-representation. See section III.A of Pre- and Post-Processing Sum-of-Squares Programs in Practice.

We cannot really do this by default since it would require having an LP solver as a dependency but it would be nice to also have this feature. In the paper mentioned above the authors mention that there are sometimes issues with the H-representation methods.

blegat avatar Mar 29 '19 10:03 blegat