zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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:
90C22Semidefinite programming
90C59Approximation methods and heuristics
References:
[1]Artin, E.: Über die zerlegung definiter funktionen in quadrate, Abhandlungen math. Seminar univ. Hamburg 5, No. 1, 100-115 (1927) · Zbl 52.0122.01 · doi:10.1007/BF02952513
[2]Aubry, P.; Rouillier, F.; El Din, M. Safey: Real solving for positive dimensional systems, J. symbolic comput. 34, No. 6, 543-560 (2002) · Zbl 1046.14031 · doi:10.1006/jsco.2002.0563
[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], Contemporary math. 253 (2000)
[6]Everett, H.; Lazard, D.; Lazard, S.; El Din, M. Safey: The Voronoi diagram of three lines in R3, , 255-264 (2007) · Zbl 1221.68268
[7]Golub, G. H.; Van Loan, C. F.: Matrix computations, (1996)
[8]Henrion, D.; Lasserre, J. -B.: Positive polynomials in control, Lecture notes on control and information sciences 312, 293-310 (2005)
[9]Hillar, C.: Sums of polynomial squares over totally real fields are rational sums of squares, Proc. amer. Math. soc. 137, 921-930 (2009) · Zbl 1163.12005 · doi:10.1090/S0002-9939-08-09641-X
[10], Issac (2008)
[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 · doi:10.1137/0214016
[13]Lax, A.; Lax, P. D.: On sums of squares, Linear algebra appl. 20, 71-75 (1978)
[14]Leep, D. B.; Starr, C. L.: Polynomials in R[x,y] that are sums of squares in R(x,y), Proc. amer. Math. soc. 129, No. 11, 3133-3141 (2001) · Zbl 0972.12003 · doi:10.1090/S0002-9939-01-05927-5
[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) · Zbl 1143.13028 · doi:10.1016/j.jco.2006.07.002
[17]Peyrl, H.; Parrilo, P. A.: A macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients, SNC’07 proc. 2007 internat. Workshop on symbolic-numeric comput, 207-208 (2007)
[18]Peyrl, H.; Parrilo, P. A.: Computing sum of squares decompositions with rational coefficients, Theoret. comput. Sci. 409, 269-281 (2008) · Zbl 1156.65062 · doi:10.1016/j.tcs.2008.09.025
[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 · doi:10.1007/BF02572604
[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 · doi:10.1090/S0002-9939-05-07879-2
[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).
[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 · doi:10.1080/10556789908805766
[29]Vandenberghe, L.; Boyd, S.: Semidefinite programming, SIAM rev. 38, No. 1, 49-95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[30]Wolkowicz, H.; Saigal, R.; Vandenberghe, L. E.: Handbook of semidefinite programming, (2000)