research-article

Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method

Authors:

Erich L. Kaltofen,

Lihong ZhiAuthors Info & Claims

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

Pages 227 - 234

https://doi.org/10.1145/1837934.1837979

Published: 25 July 2010 Publication History

Abstract

We give a stability criterion for real polynomial inequalities with floating point or inexact scalars by estimating from below or computing the radius of semidefiniteness. That radius is the maximum deformation of the polynomial coefficient vector measured in a weighted Euclidean vector norm within which the inequality remains true. A large radius means that the inequalities may be considered numerically valid.

The radius of positive (or negative) semidefiniteness is the distance to the nearest polynomial with a real root, which has been thoroughly studied before. We solve this problem by parameterized Lagrangian multipliers and Karush-Kuhn-Tucker conditions. Our algorithms can compute the radius for several simultaneous inequalities including possibly additional linear coefficient constraints. Our distance measure is the weighted Euclidean coefficient norm, but we also discuss several formulas for the weighted infinity and 1-norms.

The computation of the nearest polynomial with a real root can be interpreted as a dual of Seidenberg's method that decides if a real hypersurface contains a real point. Sums-of-squares rational lower bound certificates for the radius of semidefiniteness provide a new approach to solving Seidenberg's problem, especially when the coefficients are numeric. They also offer a surprising alternative sum-of-squares proof for those polynomials that themselves cannot be represented by a polynomial sum-of-squares but that have a positive distance to the nearest indefinite polynomial.

References

[1]

Aubry, P., Rouillier, F., and Safey El Din, M. Real solving for positive dimensional systems. J. Symbolic Comput. 34, 6 (Dec. 2002), 543--560. URL: http://www-spiral.lip6.fr/~safey/Articles/RR-3992.ps.gz.

Digital Library

[2]

Becker, E., Powers, V., and Wörmann, T. Deciding positivity of real polynomials. In Real Algebraic Geometry and Ordered Structures, C. N. Delzell and J. J. Madden, Eds., vol. 253 of Contemporary Math. AMS, 2000, pp. 251--272.

[3]

Corless, R. M., Gianni, P. M., Trager, B. M., and Watt, S. M. The singular value decomposition for polynomial systems. In Proc. 1995 Internat. Symp. Symbolic Algebraic Comput. ISSAC'95 (New York, N. Y., 1995), A. H. M. Levelt, Ed., ACM Press, pp. 96--103.

Digital Library

[4]

Corless, R. M., Kaltofen, E., and Watt, S. M. Hybrid methods. In Computer Algebra Handbook, J. Grabmeier, E. Kaltofen, and V. Weispfenning, Eds. Springer Verlag, Heidelberg, Germany, 2003, Section 2.12.3, pp. 112--125. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/01/symnum.pdf.

[5]

Ecker, J. G., and Kupferschmid, M. Introduction to Operations Research. John Wiley and Sons, 1988. 509 pp.

[6]

Henrion, D., and Lasserre, J.-B. Detecting global optimality and extracting solutions in GloptiPoly. In Positive polynomials in control, D. Henrion and A. Garulli, Eds., vol. 312 of Lecture Notes on Control and Information Sciences. Springer Verlag, Heidelberg, Germany, 2005, pp. 293--310. URL: http://homepages.laas.fr/henrion/Papers/extract.pdf.

[7]

Hitz, M. A., and Kaltofen, E. Efficient algorithms for computing the nearest polynomial with constrained roots. In Proc. 1998 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'98) (New York, N. Y., 1998), O. Gloor, Ed., ACM Press, pp. 236--243. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/98/HiKa98.pdf.

Digital Library

[8]

Hitz, M. A., Kaltofen, E., and Lakshman Y. N. Efficient algorithms for computing the nearest polynomial with a real root and related problems. In Proc. 1999 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'99) (New York, N. Y., 1999), S. Dooley, Ed., ACM Press, pp. 205--212. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/99/HKL99.pdf.

Digital Library

[9]

Jacobson, N. Basic Algebra I. W. H. Freeman & Co., San Francisco, 1974.

[10]

Jibetean, D., and de Klerk, E. Global optimization of rational functions: a semidefinite programming approach. Math. Program. 106, 1 (2006), 93--109.

Digital Library

[11]

Kaltofen, E. Computing the irreducible real factors and components of an algebraic curve. Applic. Algebra Engin. Commun. Comput. 1, 2 (1990), 135--148. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/90/Ka90_aaecc.pdf.

[12]

Kaltofen, E., Li, B., Yang, Z., and Zhi, L. Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In ISSAC 2008 (New York, N. Y., 2008), D. Jeffrey, Ed., ACM Press, pp. 155--163. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/08/KLYZ08.pdf.

Digital Library

[13]

Kaltofen, E., Yang, Z., and Zhi, L. Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In ISSAC MMVI Proc. 2006 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2006), J.-G. Dumas, Ed., ACM Press, pp. 169--176. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/06/KYZ06.pdf.

Digital Library

[14]

Kaltofen, E. L., Li, B., Yang, Z., and Zhi, L. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, Jan. 2009. Accepted for publication in J. Symbolic Comput. URL: http://www.math.ncsu.edu/~kaltofen/bibliography/09/KLYZ09.pdf.

Digital Library

[15]

Karmarkar, N. K., and Lakshman Y. N. On approximate GCDs of univariate polynomials. J. Symbolic Comput. 26, 6 (1998), 653--666. Special issue on Symbolic Numeric Algebra for Polynomials S. M. Watt and H. J. Stetter, editors.

Digital Library

[16]

Kharitonov, V. L. Asymptotic stability of an equilibrium of a family of systems of linear differential equations. Differential Equations 14 (1979), 1483--1485.

[17]

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.

[18]

Marshall, M. Positive Polynomials and Sums of Squares. American Math. Soc., 2008. 187 pp.

[19]

Nie, J., Demmel, J., and Gu, M. Global minimization of rational functions and the nearest GCDs. J. of Global Optimization 40, 4 (2008), 697--718.

Digital Library

[20]

Peyrl, H., and Parrilo, P. A. Computing sum of squares decompositions with rational coefficients. Theoretical Comput. Sci. 409 (2008), 269--281.

Digital Library

[21]

Pope, S., and Szanto, A. Nearest multivariate system with given root multiplicities. Journal of Symbolic Computation 44 (2009), 606--625. URL: http://www4.ncsu.edu/~aszanto/Pope-Szanto-Preprint.pdf.

Digital Library

[22]

Prajna, S., Papachristodoulou, A., Seiler, P., and Parrilo, P. A. SOSTOOLS: Sum of squares optimization toolbox for MATLAB. Available from http://www.cds.caltech.edu/sostools and http://www.mit.edu/~parrilo/sostools, 2004.

[23]

Rezvani, N., and Corless, R. M. The nearest singular polynomial with a given zero, revisited. SIGSAM Bulletin 39, 3 (Sept. 2005), 73--79.

Digital Library

[24]

Ruatta, O., Sciabica, M., and Szanto, A. Over-constrained Weierstrass iteration and the nearest consistent system. Rapport de Recherche 5215, INRIA, www.inria.fr, June 2004. Accepted in Journal of Complexity. URL: ftp://ftp-sop.inria.fr/galaad/oruatta/RR-5215.pdf.

[25]

Safey El Din, M. 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, 2001. URL: http://www-spiral.lip6.fr/~safey/these_safey.ps.gz.

[26]

Seidenberg, A. A new decision method for elementary algebra. Annals Math. 60 (1954), 365--374.

[27]

Stetter, H. J. The nearest polynomial with a given zero, and similar problems. SIGSAM Bulletin 33, 4 (Dec. 1999), 2--4.

Digital Library

[28]

Sturm, J. F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11/12 (1999), 625--653.

[29]

Zeng, G. Nonstandard decision methods for the solvability of real polynomial equations. Science in China Series-A Mathematics 42, 12 (1999), 1251--1261.

[30]

Zhi, L., Noda, M.-T., Kai, H., and Wu, W. Hybrid method for computing the nearest singular polynomials. Japan J. Industrial and Applied Math. 21, 2 (June 2004), 149--162. URL: http://www.mmrc.iss.ac.cn/~lzhi/Publications/znkwjjiam04.pdf.

[31]

Zhi, L., and Wu, W. Nearest singular polynomial. J. Symbolic Comput. 26, 6 (1998), 667--675. Special issue on Symbolic Numeric Algebra for Polynomials S. M. Watt and H. J. Stetter, editors.

Digital Library

Cited By

Ruatta OSciabica MSzanto A(2015)Overdetermined Weierstrass iteration and the nearest consistent systemTheoretical Computer Science10.1016/j.tcs.2014.10.008562:C(346-364)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.008
Guo FKaltofen EZhi Lvan der Hoeven Jvan Hoeij M(2012)Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functionsProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442859(195-202)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442859
Sekigawa HShirayanagi K(2011)Isolated real zero of a real polynomial system under perturbationACM Communications in Computer Algebra10.1145/2016567.201659145:1/2(131-132)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1145/2016567.2016591
Show More Cited By

Index Terms

Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method

Recommendations

Nearest multivariate system with given root multiplicities

We present a symbolic-numeric technique to find the closest multivariate polynomial system to a given one which has roots with prescribed multiplicity structure. Our method generalizes the ''Weierstrass iteration'', defined by Ruatta, to the case when ...
Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients

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-...
Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

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) ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

July 2010

366 pages

ISBN:9781450301503

DOI:10.1145/1837934

Program Chair:
Wolfram Koepf
London, Ontario, Canada

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Gesellschaft fur Informtatik

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSAC '10

Sponsor:

ISSAC '10: International Symposium on Symbolic and Algebraic Computation

July 25 - 28, 2010

Munich, Germany

Acceptance Rates

ISSAC '10 Paper Acceptance Rate 45 of 110 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
90
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ruatta OSciabica MSzanto A(2015)Overdetermined Weierstrass iteration and the nearest consistent systemTheoretical Computer Science10.1016/j.tcs.2014.10.008562:C(346-364)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.008
Guo FKaltofen EZhi Lvan der Hoeven Jvan Hoeij M(2012)Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functionsProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442859(195-202)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442859
Sekigawa HShirayanagi K(2011)Isolated real zero of a real polynomial system under perturbationACM Communications in Computer Algebra10.1145/2016567.201659145:1/2(131-132)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1145/2016567.2016591
Kaltofen E(2011)The “Seven Dwarfs” of Symbolic ComputationNumerical and Symbolic Scientific Computing10.1007/978-3-7091-0794-2_5(95-104)Online publication date: 12-Oct-2011
https://doi.org/10.1007/978-3-7091-0794-2_5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents