Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Approximating amoebas and coamoebas by sums of squares

Authors: Thorsten Theobald and Timo de Wolff
Journal: Math. Comp. 84 (2015), 455-473
MSC (2010): Primary 14P10, 14Q10, 90C22
Published electronically: March 6, 2014
MathSciNet review: 3266970
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2000a:14067)
  • [2] Mikael Forsberg, Mikael Passare, and August Tsikh, Laurent determinants and arrangements of hyperplane amoebas, Adv. Math. 151 (2000), no. 1, 45-70. MR 1752241 (2001m:32060),
  • [3] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston Inc., Boston, MA, 1994. MR 1264417 (95e:14045)
  • [4] Jean B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2000/01), no. 3, 796-817. MR 1814045 (2002b:90054),
  • [5] 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 (2010j:13054),
  • [6] 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.
  • [7] 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.
  • [8] D. Maclagan and B. Sturmfels, Introduction to Tropical Geometry, Manuscript, 2010.
  • [9] 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 (2005m:14110),
  • [10] 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,
  • [11] L. Nilsson, Amoebas, discriminants, and hypergeometric functions, Ph.D. thesis, Stockholm University, 2009.
  • [12] Lisa Nilsson and Mikael Passare, Discriminant coamoebas in dimension two, J. Commut. Algebra 2 (2010), no. 4, 447-471. MR 2753718 (2011k:14033),
  • [13] Lisa Nilsson and Mikael Passare, Mellin transforms of multivariate rational functions, J. Geom. Anal. 23 (2013), no. 1, 24-46. MR 3010271,
  • [14] M. Nisse, Geometric and combinatorial structure of hypersurface coamoebas, Preprint, arXiv:0906.2729, 2009.
  • [15] 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 (2004g:90075),
  • [16] Pablo A. Parrilo, Exploiting algebraic structure in sum of squares programs, Positive polynomials in control, Lecture Notes in Control and Inform. Sci., vol. 312, Springer, Berlin, 2005, pp. 181-194. MR 2123524 (2005i:93038)
  • [17] 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 (2006d:32005),
  • [18] Stephen Prajna, Antonis Papachristodoulou, Peter Seiler, and Pablo A. Parrilo, SOSTOOLS and its control applications, Positive polynomials in control, Lecture Notes in Control and Inform. Sci., vol. 312, Springer, Berlin, 2005, pp. 273-292. MR 2123527 (2005j:93004)
  • [19] 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 (2002k:13044)
  • [20] Kevin Purbhoo, A Nullstellensatz for amoebas, Duke Math. J. 141 (2008), no. 3, 407-445. MR 2387427 (2009b:14114),
  • [21] Mihai Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), no. 3, 969-984. MR 1254128 (95h:47014),
  • [22] 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 (2006d:14073),
  • [23] 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,
  • [24] 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, 2002. MR 1925796 (2003i:13037)
  • [25] J.L. Sun, Low rank decompositions for sum of squares optimization, M.Sc. thesis, M.I.T., 2006.
  • [26] Thorsten Theobald, Computing amoebas, Experiment. Math. 11 (2002), no. 4, 513-526 (2003). MR 1969643 (2004b:14100)
  • [27] Thorsten Theobald and Timo de Wolff, Amoebas of genus at most one, Adv. Math. 239 (2013), 190-213. MR 3045147,
  • [28] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223 (2001k:90001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14P10, 14Q10, 90C22

Retrieve articles in all journals with MSC (2010): 14P10, 14Q10, 90C22

Additional Information

Thorsten Theobald
Affiliation: Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany

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

Keywords: Amoebas, sums of squares, real Nullstellensatz, coamoebas, semidefinite programming
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.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society