×

zbMATH — the first resource for mathematics

Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. (English) Zbl 1229.90115
Summary: We present a hybrid symbolic-numeric algorithm for certifying a polynomial or rational function with rational coefficients to be non-negative for all real values of the variables by computing a representation for it as a fraction of two polynomial sum-of-squares (SOS) with rational coefficients. Our new approach turns the earlier methods by Peyrl and Parrilo at SNC’07 and ours at ISSAC’08 both based on polynomial SOS, which do not always exist, into a universal algorithm for all inputs via Artin’s theorem.
Furthermore, we scrutinize the all-important process of converting the numerical SOS numerators and denominators produced by block semidefinite programming into an exact rational identity. We improve on our own Newton iteration-based high precision refinement algorithm by compressing the initial Gram matrices and by deploying rational vector recovery aside from orthogonal projection. We successfully demonstrate our algorithm on (1) various exceptional SOS problems with necessary polynomial denominators from the literature and on (2) very large (thousands of variables) SOS lower bound certificates for Rump’s model problem (up to \(n=18\), factor degree=17).

MSC:
90C22 Semidefinite programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Artin, E., Über die zerlegung definiter funktionen in quadrate, Abhandlungen math. seminar univ. Hamburg, 5, 1, 100-115, (1927) · JFM 52.0122.01
[2] Aubry, P.; Rouillier, F.; Safey El Din, M., Real solving for positive dimensional systems, J. symbolic comput., 34, 6, 543-560, (2002), URL: http://www-spiral.lip6.fr/ safey/Articles/RR-3992.ps.gz · Zbl 1046.14031
[3] Becker, E., Powers, V., Wörmann, T., 2000. Deciding positivity of real polynomials. In: Delzell (2000), pp. 251-272, URL: http://www.mathcs.emory.edu/ vicki/pub/psd.pdf.
[4] Delzell, C.N., 1980. A constructive, continuous solution to Hilbert’s 17th problem, and other results in semi-algebraic geometry. Ph.D. Thesis, Stanford University.
[5] ()
[6] Everett, H.; Lazard, D.; Lazard, S.; Safey El Din, M., The Voronoi diagram of three lines in \(R^3\), (), 255-264 · Zbl 1221.68268
[7] Golub, G.H.; Van Loan, C.F., Matrix computations, (1996), Johns Hopkins University Press Baltimore, Maryland · Zbl 0865.65009
[8] Henrion, D.; Lasserre, J.-B., Positive polynomials in control, (), 293-310, URL: http://homepages.laas.fr/henrion/Papers/extract.pdf
[9] Hillar, C., Sums of polynomial squares over totally real fields are rational sums of squares, Proc. amer. math. soc., 137, 921-930, (2009), URL: http://www.math.tamu.edu/ chillar/files/totallyrealsos.pdf · Zbl 1163.12005
[10] ()
[11] Kaltofen, E., Li, B., Yang, Z., Zhi, L., 2008. Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In: Jeffrey (2008), pp. 155-163, URL: EKbib/08/KLYZ08.pdf.
[12] Lagarias, J.C., The computational complexity of simultaneous Diophantine approximation problems, SIAM J. comp., 14, 196-209, (1985) · Zbl 0563.10025
[13] Lax, A.; Lax, P.D., On sums of squares, Linear algebra appl., 20, 71-75, (1978) · Zbl 0371.15013
[14] Leep, D.B.; Starr, C.L., Polynomials in \(\mathbb{R} [x, y]\) that are sums of squares in \(\mathbb{R}(x, y)\), Proc. amer. math. soc., 129, 11, 3133-3141, (2001) · Zbl 0972.12003
[15] Löfberg, J., 2004. YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proc. IEEE CCA/ISIC/CACSD Conf. Taipei, Taiwan, URL: http://control.ee.ethz.ch/ joloef/yalmip.php.
[16] Nie, J.; Schweighofer, M., On the complexity of putinar’s positivstellensatz, J. complexity, 23, (2007), 135-70 · Zbl 1143.13028
[17] Peyrl, H.; Parrilo, P.A., A macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients, (), 207-208
[18] Peyrl, H.; Parrilo, P.A., Computing sum of squares decompositions with rational coefficients, Theoret. comput. sci., 409, 269-281, (2008) · Zbl 1156.65062
[19] Prajna, S., Papachristodoulou, A., Seiler, P., Parrilo, P.A., 2004. SOSTOOLS: Sum of squares optimization toolbox for MATLAB. Available from http://www.cds.caltech.edu/sostools and http://www.mit.edu/ parrilo/sostools.
[20] Reznick, B., Uniform denominators in hilbert’s seventeenth problem, Math. Z., 220, 75-97, (1995) · Zbl 0828.12002
[21] Reznick, B., 2000. Some concrete aspects of Hilbert’s 17th problem. In: Delzell (2000), pp. 251-272, also in Seminaire de Structures Algébriques Ordonnées, F. Delon, M.A. Dickmann, D. Gondard (Eds.), Publ. Équipe de Logique, Univ. Paris VII, Jan. 1996. URL: http://www.math.uiuc.edu/ reznick/hil17.pdf. · Zbl 0972.11021
[22] Reznick, B., On the absence of uniform denominators in hilbert’s 17th problem, Proc. amer. math. soc., 133, 2829-2834, (2005) · Zbl 1120.12002
[23] Rump, S.M., 2006. Global optimization: a model problem. URL: http://www.ti3.tu-harburg.de/rump/Research/ModelProblem.pdf.
[24] Rump, S.M., 2009. A model problem for global optimization. Manuscript. 6 pages.
[25] Rump, S.M.; Sekigawa, H., The ratio between the Toeplitz and the unstructured condition number, Operator theory: advances and applications, 199, 397-419, (2009) · Zbl 1203.15004
[26] Safey El Din, M., 2001. Résolution réelle des systèmes polynomiaux en dimension positive. Thèse de doctorat, Univ. Paris VI (Univ. Pierre et Marie Curie), Paris, France, URL: http://www-spiral.lip6.fr/ safey/these_safey.ps.gz.
[27] Safey El Din, M., 2008. Computing the global optimum of a multivariate polynomial over the reals. In: Jeffrey (2008). · Zbl 1166.65317
[28] Sturm, J.F., Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. methods softw., 11/12, 625-653, (1999) · Zbl 0973.90526
[29] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM rev., 38, 1, 49-95, (1996) · Zbl 0845.65023
[30] Wolkowicz, H.; Saigal, R.; Vandenberghe, L.E., Handbook of semidefinite programming, (2000), Kluwer Academic Boston
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.