Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars

ABSTRACT

We generalize the technique by Peyrl and Parillo [Proc. SNC 2007] to computing lower bound certificates for several well-known factorization problems in hybrid symbolic-numeric computation. The idea is to transform a numerical sum-of-squares (SOS) representation of a positive polynomial into an exact rational identity. Our algorithms successfully certify accurate rational lower bounds near the irrational global optima for benchmark approximate polynomial greatest common divisors and multivariate polynomial irreducibility radii from the literature, and factor coefficient bounds in the setting of a model problem by Rump (up to n = 14, factor degree = 13.

The numeric SOSes produced by the current fixed precision semi-definite programming (SDP) packages (SeDuMi, SOSTOOLS, YALMIP) are usually too coarse to allow successful projection to exact SOSes via Maple 11's exact linear algebra. Therefore, before projection we refine the SOSes by rank-preserving Newton iteration. For smaller problems the starting SOSes for Newton can be guessed without SDP ("SDP-free SOS"), but for larger inputs we additionally appeal to sparsity techniques in our SDP formulation.

REFERENCES

• 1: Boyd, D., Kaltofen, E., and Zhi, L. Integer polynomials with large single factor coefficient bounds. In preparation, 2008.
• 2: Chèze, G., and Yakoubsohn, J.-C. Distance computation to the resultant variety, Nov. 2007. Talk at the Journées 2007 da l'ANR GECKO, URL: http://www-sop.inria.fr/galaad/conf/07gecko/Yakoubshon.J.C.pdf.
• 3: Collins, G. E. Single-factor coefficient bounds. J. Symbolic Comput. 38, 6 (2004), 1507--1521.
• 4: Xavier Dahan , Éric Schost, Sharp estimates for triangular sets, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.103-110, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005302]
• 5: 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]
• 6: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 7: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 8: Brent Gregory , Erich Kaltofen, Analysis of the binary complexity of asymptotically fast algorithms for linear system solving, ACM SIGSAM Bulletin, v.22 n.2, p.41-49, April 1988 [doi>10.1145/43876.43880]
• 9: Gutierrez, J., Ed. ISSAC 2004 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2004), ACM Press.
• 10: Hillar, C. Sums of polynomial squares over totally real fields are rational sums of squares. Proc. American Math. Society (2008). To appear. URL: http://www.math.tamu.edu/ chillar/files/totallyrealsos.pdf.
• 11: Markus A. Hitz , Erich Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.236-243, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281624]
• 12: D. Jibetean , E. de Klerk, Global optimization of rational functions: a semidefinite programming approach, Mathematical Programming: Series A and B, v.106 n.1, p.93-109, May 2006 [doi>10.1007/s10107-005-0589-0]
• 13: Erich Kaltofen , Bin Li , Kartik Sivaramakrishnan , Zhengfeng Yang , Lihong Zhi, Lower bounds for approximate factorizations via semidefinite programming: (extended abstract), Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277532]
• 14: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 15: Erich Kaltofen , John P. May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials using singular value decomposition, Journal of Symbolic Computation, v.43 n.5, p.359-376, May, 2008 [doi>10.1016/j.jsc.2007.11.005]
• 16: Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145799]
• 17: Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277503]
• 18: N. K. Karmarkar , Y. N. Lakshman, On approximate GCDs of univariate polynomials, Journal of Symbolic Computation, v.26 n.6, p.653-666, Dec. 1998 [doi>10.1006/jsco.1998.0232]
• 19: 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]
• 20: Jean B. Lasserre, Convergent SDP-Relaxations in Polynomial Optimization with Sparsity, SIAM Journal on Optimization, v.17 n.3, p.822-843, September 2006 [doi>10.1137/05064504X]
• 21: Li, B., Liu, Z., and Zhi, L. Structured condition numbers of Sylvester matrices (extended abstract), Dec. 2007. Presented at MACIS 2007, URL: http://www-spiral.lip6.fr/MACIS2007/Papers/submission_17.pdf.
• 22: Bin Li , Jiawang Nie , Lihong Zhi, Approximate GCDs of polynomials and SOS relaxation, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277533]
• 23: Li, B., Nie, J., and Zhi, L. Approximate GCDs of polynomials and sparse SOS relaxations. Manuscript, 16 pages. Submitted, 2007.
• 24: Löfberg, J. YALMIP : A toolbox for modeling and optimization in MATLAB. In Proc. IEEE CCA/ISIC/CACSD Conf. (Taipei, Taiwan, 2004). URL: http://control.ee.ethz.ch/ joloef/yalmip.php.
• 25: Mignotte, M. Some useful bounds. In Computer Algebra, B. Buchberger, G. Collins, and R. Loos, Eds., 2 ed. Springer Verlag, Heidelberg, Germany, 1982, pp. 259--263.
• 26: Kosaku Nagasaka, Towards certified irreducibility testing of bivariate approximate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.192-199, July 07-10, 2002, Lille, France [doi>10.1145/780506.780531]
• 27: Nie, J., and Demmel, J. Sparse SOS relaxations for minimization functions that are summation of small polynomials, 2007.
• 28: Nie, J., Demmel, J., and Gu, M. Global minimization of rational functions and the nearest GCDs. ArXiv Mathematics e-prints (Jan. 2006). URL: http://arxiv.org/pdf/math/0601110.
• 29: Nie, J., Ranestad, K., and Sturmfels, B. The algebraic degree of semidefinite programming, 2006. URL: http://www.citebase.org/abstract?id=oai:arXiv.org:math/0611562.
• 30: Jiawang Nie , Markus Schweighofer, On the complexity of Putinar's Positivstellensatz, Journal of Complexity, v.23 n.1, p.135-150, February, 2007 [doi>10.1016/j.jco.2006.07.002]
• 31: Parrilo, P. A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, May 2000. URL: http://www.cds.caltech.edu/ pablo/.
• 32: Parrilo, P. A. Exploiting algebraic structure in sum of squares programs. Lecture Notes in Control and Information Sciences 312 (2005), 181--194.
• 33: Parrilo, P. A., and Sturmfels, B. Minimizing polynomial functions. DIMACS series in discrete mathematics and theoretical computer 60 (2003), 83. URL: http://www.citebase.org/abstract?id=oai:arXiv.org:math/0103170.
• 34: Helfried Peyrl , Pablo A. Parrilo, A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277534]
• 35: Prajna, S., Papachristodoulou, A., and Parrilo, P. A. SOSTOOLS: Sum of squares optimization toolbox for MATLAB. URL: http://www.cds.caltech.edu/sostools.
• 36: Reznick, B. Extremal PSD forms with few terms. Duke Mathematical Journal 45, 2 (1978), 363--374.
• 37: Siegfried M. Rump, Structured Perturbations Part I: Normwise Distances, SIAM Journal on Matrix Analysis and Applications, v.25 n.1, p.1-30, 2003 [doi>10.1137/S0895479802405732]
• 38: Rump, S. M. Global optimization: a model problem, 2006. URL: http://www.ti3.tu-harburg.de/rump/Research/ModelProblem.pdf.
• 39: Rump, S. M., and Sekigawa, H. The ratio between the Toeplitz and the unstructured condition number, 2006. To appear. URL: http://www.ti3.tu-harburg.de/paper/rump/RuSe06.pdf.
• 40: Mohab Safey El Din, Computing the global optimum of a multivariate polynomial over the reals, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria [doi>10.1145/1390768.1390781]
• 41: Sturm, J. F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11/12 (1999), 625--653.
• 42: Verschelde, J., and Watt, S. M., Eds. SNC'07 Proc. 2007 Internat. Workshop on Symbolic-Numeric Comput. (New York, N. Y., 2007), ACM Press.
• 43: Gilles Villard, Certification of the QR factor R and of lattice basis reducedness, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277597]
• 44: Hayato Waki , Sunyoung Kim , Masakazu Kojima , Masakazu Muramatsu, Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity, SIAM Journal on Optimization, v.17 n.1, p.218-242, 2006 [doi>10.1137/050623802]
• 45: Zhang, T., Xiao, R., and Xia, B. Real soultion isolation based on interval Krawczyk operator. In Proc. of the Seventh Asian Symposium on Computer Mathematics (Seoul, South Korea, 2005), S. Pae and H. Park, Eds., Korea Institute for Advanced Study, pp. 235--237. Extended abstract.
• 46: Lihong Zhi, Numerical optimization in hybrid symbolic-numeric computation, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277507]
• 47: Zhou, W., and Jeffrey, D. J. Fraction-free matrix factors: new forms for LU and QR factors. In Frontiers of Computer Science in China (2008). To appear. URL http://www.apmaths.uwo.ca/djeffrey/Offprints/FFLUQR.pdf.

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, Experimentation

Keywords:
approximate factorization, hybrid method, semidefinite programming, sum-of-squares, validated output