Computing the global optimum of a multivariate polynomial over the reals

ABSTRACT

Let f be a polynomial in Q[X₁, ..., X_n] of degree D. We provide an efficient algorithm in practice to compute the global supremum sup_{x∈ Rⁿ} f(x) of f (or its infimum inf_{{x∈ Rⁿ}}f(x)). The complexity of our method is bounded by D^O(n)}. In a probabilistic model, a more precise result yields a complexity bounded by O(n⁷D⁴ⁿ) arithmetic operations in Q. Our implementation is more efficient by several orders of magnitude than previous ones based on quantifier elimination. Sometimes, it can tackle problems that numerical techniques do not reach. Our algorithm is based on the computation of generalized critical values of the mapping x-> f(x), i.e. the set of points {c∈ C mid exists (x_ll)_ll∈ N}⊂ Cⁿ ;f(x_ll)-> c, ;||x_ll||||d_xll f||-> 0 { when }ll-> ∞}. We prove that the global optimum of f lies in its set of generalized critical values and provide an efficient way of deciding which value is the global optimum.

REFERENCES

• 1: Philippe Aubry , Fabrice Rouillier , Mohab Safey El Din, Real solving for positive dimensional systems, Journal of Symbolic Computation, v.34 n.6, p.543-560, December 2002 [doi>10.1006/jsco.2002.0563]
• 2: B. Bank , M. Giusti , J. Heintz , G. M. Mbakop, Polar varieties, real equation solving, and data structures: the hypersurface case, Journal of Complexity, v.13 n.1, p.5-27, March 1997 [doi>10.1006/jcom.1997.0432]
• 3: B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real elimination. Mathematische Zeitschrift, 238(1):115--144, 2001.
• 4: B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. Generalized polar varieties and efficient real elimination procedure. Kybernetika, 40(5):519--550, 2004.
• 5: B. Bank , M. Giusti , J. Heintz , L. M. Pardo, Generalized polar varieties: geometry and algorithms, Journal of Complexity, v.21 n.4, p.377-412, August 2005 [doi>10.1016/j.jco.2004.10.001]
• 6: Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
• 7: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 8: C. Brown and H. et al. Hong. Qepcad - quantifier elimination by partial cylindrical algebraic decomposition. available at http://www.cs.usna.edu/ qepcad/B/QEPCAD.html.
• 9: G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture notes in computer science, 33:515--532, 1975.
• 10: I. Emiris and E. Tsigaridas. Real algebraic numbers and polynomial systems of small degree. submitted to Journal of Symbolic Computation, 2008.
• 11: Hazel Everett , Sylvain Lazard , Daniel Lazard , Mohab Safey El Din, The voronoi diagram of three lines, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247116]
• 12: J.-C. Faugère. Gb/FGb. available at http://fgbrs.lip6.fr.
• 13: Robert M. Freund , Fernando Ordóñez , Kim-Chuan Toh, Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems, Mathematical Programming: Series A and B, v.109 n.2, p.445-475, January 2007 [doi>10.1007/s10107-006-0035-y]
• 14: M. Giusti, K. H\"agele, J. Heintz, J.-E Morais, J.-L. Monta\ na, and L.-M. Pardo. Lower bounds for Diophantine approximation. In Proceedings of MEGA'96, number 117, 118 in Journal of Pure and Applied Algebra, pages 277--317, 1997.
• 15: M. Giusti, J. Heintz, J.-E. Morais, J. Morgenstern, and L.-M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101--146, 1998.
• 16: Marc Giusti , Joos Heintz , Jose Enrique Morais , Luis M. Pardo, When Polynomial Equation Systems Can Be "Solved" Fast?, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.205-231, July 17-22, 1995
• 17: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 18: D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
• 19: J. Heintz, M.-F. Roy, and P. Solernò. On the complexity of semi-algebraic sets. In Proceedings IFIP'89 San Francisco, North-Holland, 1989.
• 20: J. Heintz, M.-F. Roy, and P. Solernò. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5):427--431, 1993.
• 21: D. Henrion. Polynômes et optimisation convexe en commande robuste. PhD thesis, LAAS, Toulouse, 2007. Habilitation à diriger des recherches.
• 22: Z. Jelonek and K. Kurdyka. On asymptotic critical values of a complex polynomial. J. Reine Angew. Math., 565:1--11, 2003.
• 23: K. Kurdyka, P. Orro, and S. Simon. Semialgebraic sard theorem for generalized critical value. Journal of differential geometry, 56(1):67--92, 2000.
• 24: Y. N. Lakshmann. A single exponential bound of the complexity of computing Gröbner bases of zero-dimensional ideals. In C. Traverso T. Mora, editor, Proc. Effective Methods in Algebraic Geometry, MEGA'90, volume 94 of Progress in Mathematics, pages 227--234. Birkhaüser, 1991.
• 25: Y.N. Lakshmann and D. Lazard. On the complexity of zero-dimensional algebraic systems. In MEGA, volume 94 of Progress in Mathematics, pages 217--225. Birkhaüser, 1991.
• 26: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 27: J. B. Lasserre, M. Laurent, and P. Rostalski. Semidefinite characterization and computation of real radical ideals, 2006.
• 28: Daniel Lazard , Fabrice Rouillier, Solving parametric polynomial systems, Journal of Symbolic Computation, v.42 n.6, p.636-667, June, 2007 [doi>10.1016/j.jsc.2007.01.007]
• 29: Daniel Lazard, Quantifier elimination: optimal solution for two classical examples, Journal of Symbolic Computation, v.5 n.1-2, p.261-266, February/April 1988 [doi>10.1016/S0747-7171(88)80015-4]
• 30: Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Journal of Complexity, v.19 n.4, p.564-596, August 2003 [doi>10.1016/S0885-064X(03)00031-1]
• 31: Jiawang Nie , James Demmel , Bernd Sturmfels, Minimizing Polynomials via Sum of Squares over the Gradient Ideal, Mathematical Programming: Series A and B, v.106 n.3, p.587-606, May 2006 [doi>10.1007/s10107-005-0672-6]
• 32: P. A. Parillo. Semi-definite relaxations for semi-algebraic problems. Mathematical Programming, 92(2):293--320, 2003.
• 33: P. Parrilo and B. Sturmfels. Minimizing polynomial functions. Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 60:83, 2003.
• 34: S. Prajna, A. Papachristodoulou, P. Parillo, and P. Seiler. Sostools. available at http://www.cds.caltech.edu/sostools/.
• 35: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• 36: F. Rouillier. RS, RealSolving. available at http://fgbrs.lip6.fr.
• 37: F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. AAECC Journal, 9(5):433--461, 1999.
• 38: F. Rouillier , M.-F. Roy , M. Safey El Din, Finding at least one point in each connected component of a real algebraic set defined by a single equation, Journal of Complexity, v.16 n.4, p.716-750, Dec. 1, 2000 [doi>10.1006/jcom.2000.0563]
• 39: M. Safey El Din. Finding sampling points on real hypersurfaces in easier in singular situations. In MEGA (Effective Methods in Algebraic Geometry) Electronic proceedings, 2005.
• 40: M. Safey El Din. Practical and theoretical issues for the computation of generalized critical values of a polynomial mapping and its applications. In Proceedings of Asian Symposium on Computer Mathematics 2007, 2007. to appear.
• 41: M. Safey El Din. RAGLib (Real Algebraic Geometry Library), Maple package. available at http://www-spiral.lip6.fr/$\sim$safey/RAGLib, 2007.
• 42: M. Safey El Din. Testing sign conditions on a multivariate polynomial and applications. Mathematics in Computer Science, 1(1):177--207, December 2007.
• 43: Mohab Safey El Din , Éric Schost, Polar varieties and computation of one point in each connected component of a smooth real algebraic set, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.224-231, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860901]
• 44: M. Safey El Din and É. Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Journal of Discrete and Computational Geometry, 2004.
• 45: Markus Schweighofer, Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares, SIAM Journal on Optimization, v.17 n.3, p.920-942, September 2006 [doi>10.1137/050647098]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms

Keywords:
complexity, global optimization, polynomial system solving, real solutions