Approximating amoebas and coamoebas by sums of squares

Theobald, Thorsten; de Wolff, Timo

doi:10.1090/S0025-5718-2014-02828-7

Approximating amoebas and coamoebas by sums of squares
HTML articles powered by AMS MathViewer

by Thorsten Theobald and Timo de Wolff PDF

Math. Comp. 84 (2015), 455-473 Request permission

Abstract:

Amoebas and coamoebas are the logarithmic images of algebraic varieties and the images of algebraic varieties under the arg-map, respectively. We present new techniques for computational problems on amoebas and coamoebas, thus establishing new connections between (co-)amoebas, semialgebraic and convex algebraic geometry and semidefinite programming.

Our approach is based on formulating the membership problem in amoebas (respectively coamoebas) as a suitable real algebraic feasibility problem. Using the real Nullstellensatz, this allows us to tackle the problem by sums of squares techniques and semidefinite programming. Our method yields polynomial identities as certificates of non-containment of a point in an amoeba or coamoeba. As the main theoretical result, we establish some degree bounds on the polynomial certificates. Moreover, we provide some actual computations of amoebas based on the sums of squares approach.

References

Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
Mikael Forsberg, Mikael Passare, and August Tsikh, Laurent determinants and arrangements of hyperplane amoebas, Adv. Math. 151 (2000), no. 1, 45–70. MR 1752241, DOI 10.1006/aima.1999.1856
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796–817. MR 1814045, DOI 10.1137/S1052623400366802
Monique Laurent, Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, 2009, pp. 157–270. MR 2500468, DOI 10.1007/978-0-387-09686-5_{7}
J.A. De Loera, J. Lee, P.N. Malkin, and S. Margulies, Hilbert’s Nullstellensatz and an algorithm for proving combinatorial infeasibility, Proc. ISSAC 2008, ACM, New York, 2008, pp. 197–206.
J. Löfberg and P. Parrilo, From coefficients to samples: a new approach to SOS optimization, 43rd IEEE Conference on Decision and Control, Atlantis, vol. 3, 2004, pp. 3154–3159.
D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Manuscript, 2010.
Grigory Mikhalkin, Amoebas of algebraic varieties and tropical geometry, Different faces of geometry, Int. Math. Ser. (N. Y.), vol. 3, Kluwer/Plenum, New York, 2004, pp. 257–300. MR 2102998, DOI 10.1007/0-306-48658-X_{6}
Silviu-Iulian Niculescu and Mihai Putinar, A toric Positivstellensatz with applications to delay systems, C. R. Math. Acad. Sci. Paris 349 (2011), no. 5-6, 327–329 (English, with English and French summaries). MR 2783329, DOI 10.1016/j.crma.2010.11.018
L. Nilsson, Amoebas, discriminants, and hypergeometric functions, Ph.D. thesis, Stockholm University, 2009.
Lisa Nilsson and Mikael Passare, Discriminant coamoebas in dimension two, J. Commut. Algebra 2 (2010), no. 4, 447–471. MR 2753718, DOI 10.1216/JCA-2010-2-4-447
Lisa Nilsson and Mikael Passare, Mellin transforms of multivariate rational functions, J. Geom. Anal. 23 (2013), no. 1, 24–46. MR 3010271, DOI 10.1007/s12220-011-9235-7
M. Nisse, Geometric and combinatorial structure of hypersurface coamoebas, Preprint, arXiv:0906.2729, 2009.
Pablo A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. 96 (2003), no. 2, Ser. B, 293–320. Algebraic and geometric methods in discrete optimization. MR 1993050, DOI 10.1007/s10107-003-0387-5
Pablo A. Parrilo, Exploiting algebraic structure in sum of squares programs, Positive polynomials in control, Lect. Notes Control Inf. Sci., vol. 312, Springer, Berlin, 2005, pp. 181–194. MR 2123524, DOI 10.1007/10997703_{1}1
Mikael Passare and August Tsikh, Amoebas: their spines and their contours, Idempotent mathematics and mathematical physics, Contemp. Math., vol. 377, Amer. Math. Soc., Providence, RI, 2005, pp. 275–288. MR 2149010, DOI 10.1090/conm/377/06997
Stephen Prajna, Antonis Papachristodoulou, Peter Seiler, and Pablo A. Parrilo, SOSTOOLS and its control applications, Positive polynomials in control, Lect. Notes Control Inf. Sci., vol. 312, Springer, Berlin, 2005, pp. 273–292. MR 2123527, DOI 10.1007/10997703_{1}4
Alexander Prestel and Charles N. Delzell, Positive polynomials, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2001. From Hilbert’s 17th problem to real algebra. MR 1829790, DOI 10.1007/978-3-662-04648-7
Kevin Purbhoo, A Nullstellensatz for amoebas, Duke Math. J. 141 (2008), no. 3, 407–445. MR 2387427, DOI 10.1215/00127094-2007-001
Mihai Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. MR 1254128, DOI 10.1512/iumj.1993.42.42045
Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald, First steps in tropical geometry, Idempotent mathematics and mathematical physics, Contemp. Math., vol. 377, Amer. Math. Soc., Providence, RI, 2005, pp. 289–317. MR 2149011, DOI 10.1090/conm/377/06998
Jos F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw. 11/12 (1999), no. 1-4, 625–653. Interior point methods. MR 1778433, DOI 10.1080/10556789908805766
Bernd Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2002. MR 1925796, DOI 10.1090/cbms/097
J.L. Sun, Low rank decompositions for sum of squares optimization, M.Sc. thesis, M.I.T., 2006.
Thorsten Theobald, Computing amoebas, Experiment. Math. 11 (2002), no. 4, 513–526 (2003). MR 1969643, DOI 10.1080/10586458.2002.10504703
Thorsten Theobald and Timo de Wolff, Amoebas of genus at most one, Adv. Math. 239 (2013), 190–213. MR 3045147, DOI 10.1016/j.aim.2013.03.001
Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223, DOI 10.1007/978-1-4615-4381-7