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
Additional Information
- Thorsten Theobald
- Affiliation: Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany
- MR Author ID: 618735
- ORCID: 0000-0002-5769-0917
- Email: theobald@math.uni-frankfurt.de
- Timo de Wolff
- Affiliation: Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany
- Address at time of publication: Universität des Saarlandes, Fachrichtung Mathematik, Postfach 151150, 66041 Searbrücken, Germany
- MR Author ID: 1019872
- Email: dewolff@math.uni-sb.de
- Received by editor(s): April 13, 2011
- Received by editor(s) in revised form: February 14, 2013, and April 19, 2013
- Published electronically: March 6, 2014
- Additional Notes: This research was supported by DFG grant TH 1333/2-1.
The first author was supported by the Alexander von Humboldt-Foundation. - © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 84 (2015), 455-473
- MSC (2010): Primary 14P10, 14Q10, 90C22
- DOI: https://doi.org/10.1090/S0025-5718-2014-02828-7
- MathSciNet review: 3266970