Minimizing polynomials via sum of squares over the gradient ideal. (English) Zbl 1134.90032
Summary: A method is proposed for finding the global minimum of a multivariate polynomial via sum of squares (SOS) relaxation over its gradient variety. That variety consists of all points where the gradient is zero and it need not be finite. A polynomial which is nonnegative on its gradient variety is shown to be SOS modulo its gradient ideal, provided the gradient ideal is radical or the polynomial is strictly positive on the real gradient variety. This opens up the possibility of solving previously intractable polynomial optimization problems. The related problem of constrained minimization is also considered, and numerical examples are discussed. Experiments show that our method using the gradient variety outperforms prior SOS methods.
MSC:
| 90C22 | Semidefinite programming |
| 14P10 | Semialgebraic sets and related spaces |
| 90C46 | Optimality conditions and duality in mathematical programming |
Keywords:
polynomials; global optimization; sum of squares (SOS); semidefinite programming (SDP); radical ideal; variety; gradient ideal; algebraic geometryReferences:
| [1] | Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer-Verlag, 2003 · Zbl 1031.14028 |
| [2] | Berg, C.: The multidimensional moment problem and semi-groups. In: Moments in Mathematics, H.J. Landau (ed.), AMS, Providence, RI, 1980, pp 110–124 |
| [3] | Bochnak, J., Coste, M., Roy, M-F.: Real Algebraic Geometry, Springer, 1998 · Zbl 0912.14023 |
| [4] | Blekherman, G.: There are significantly more nonnegative polynomials than sums of squares. To appear in Israel Journal of Mathematics · Zbl 1139.14044 |
| [5] | Becker, E., Neuhaus, R.: Computation of real radicals of polynomial ideals. Computational algebraic geometry (Nice, 1992), 1–20, Progress in Mathematics, 109, Birkhäuser, Boston, MA, 1993 · Zbl 0804.13010 |
| [6] | Becker, E., Neuhaus, R.: Computation of real radicals of polynomial ideals. II. J. Pure Appl. Algebra 124, 261–280 (1998) · Zbl 0894.13002 · doi:10.1016/S0022-4049(96)00103-X |
| [7] | Cox, D.A., Little, J.B., D.O’Shea.: Ideals, Varieties and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra, Second Edition. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1997 |
| [8] | Cox, D.A., Little, J.B., D.O’Shea.: Using Algebraic Geometry, Graduate Texts in Mathematics, Vol. 185. Springer-Verlag, New York, 1998 · Zbl 0920.13026 |
| [9] | Corless, R.M., Gianni, P.M., Trager, B.M.: A reorder Schur factorization method for zero-dimensional polynomial systems with multiple roots. Proc. ACM Int. Symp. Symbolic and Algebraic Computation, Maui, Hawaii, 1997, pp 133–140 · Zbl 0917.65048 |
| [10] | Curto, R.E., Fialkow, L.A.: The truncated complex K-moment problem. Trans. Am. Math. Soc. 352, 2825–2855 (2000) · Zbl 0955.47011 · doi:10.1090/S0002-9947-00-02472-7 |
| [11] | Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, Vol. 150. Springer-Verlag, New York, 1995 · Zbl 0819.13001 |
| [12] | Fortuna, E., Gianni, P., Trager, B.: Derivations and radicals of polynomial ideals over fields of arbitrary characteristic. Computer algebra (London, ON, 2001). J. Symbolic Comput. 33 (5), 609–625 (2002) · Zbl 1059.13014 |
| [13] | Grigoriev, D., Vorobjov, N. N., Jr. Solving systems of polynomial inequalities in subexponential time. J. Symbolic Comput. 5 (1–2), 37–64 (1988) · Zbl 0662.12001 |
| [14] | Hanzon, B., Jibetean, D.: Global minimization of a multivariate polynomial using matrix methods. J. Global Optimization 27, 1–23 (2003) · Zbl 1035.90084 · doi:10.1023/A:1024664432540 |
| [15] | Henrion, D., Lasserre, J. B.: GloptiPoly: Global Optimization over Polynomials with Matlab and SeDuMi. Proceeding of the 41st IEEE Conference on Decision and Control (CDC’2002), Las Vegas, Nevada, December 10–13, 2002, pp 747–752 · Zbl 1070.65549 |
| [16] | Henrion, D., Lasserre, J.: Detecting global optimality and extracting solutions in GloptiPoly. Positive polynomials in control, D. Henrion, A. Garulli Eds., Lecture Notes on Control and Information Sciences, Vol. 312, Springer, Berlin, 2005, pp 293–310 · Zbl 1119.93301 |
| [17] | Jibetean, D., Laurent, M.: Converging SDP bounds for global unconstrained polynomial optimization. Preprint, 2004. Website: http://www.cwi.nl/\(\sim\)monique · Zbl 1103.90073 |
| [18] | Krick, T., Logar, A.: An algorithm for the computation of the radical of an ideal in the ring of polynomials. Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci., 539, Springer, Berlin, 1991, pp 195–205 · Zbl 0823.13018 |
| [19] | Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (3), 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802 |
| [20] | Laurent, M.: Semidefinite representations for finite varieties. To appear in Mathematical Programming. Website: http://www.cwi.nl/\(\sim\)monique · Zbl 1152.90007 |
| [21] | Marshall, M.: Optimization of polynomial functions. Canad. Math. Bull. 46, 575–587 (2003) · Zbl 1063.14071 · doi:10.4153/CMB-2003-054-7 |
| [22] | Nesterov, Y.: Squared functional systems and optimization problems. High Performance Optimization H. Frenk et al. (eds.), Kluwer Academic Publishers, 2000, pp 405–440 · Zbl 0958.90090 |
| [23] | Nie, J., Demmel, J. W.: Minimum ellipsoid bounds for solutions of polynomial systems via sum of squares, to appear in J. Global Optimization, arXiv:math.OC/0411122 |
| [24] | Nie, J., Demmel, J. W., Powers, V.: Representations of positive polynomials on non-compact semialgebraic sets via KKT ideals. Preprint, 2005 · Zbl 1106.13028 |
| [25] | Nocedal, J., Wright, S. J.: Numerical Optimization, Springer Series in Operations Research, Springer-Verlag, New York, 1999 · Zbl 0930.65067 |
| [26] | Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D Thesis, California Institute of Technology, 2000 |
| [27] | Parrilo, P., Sturmfels, B.: Minimizing polynomial functions, Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science (March 2001), S. Basu, L. Gonzalez-Vega (eds.), American Mathematical Society, 2003, pp 83–100 · Zbl 1099.13516 |
| [28] | Parrilo, P.: Semidefinite Programming relaxations for semialgebraic problems. Math. Program. Ser. B 96 (2), 293–320 (2003) · Zbl 1043.14018 · doi:10.1007/s10107-003-0387-5 |
| [29] | Prajna, S., Papachristodoulou, A., Parrilo, P.: SOSTOOLS User’s Guide. http://control.ee.ethz.ch/\(\sim\)parrilo/SOSTOOLS/ · Zbl 1119.93302 |
| [30] | Parrilo, P.: An explicit construction of distinguished representations of polynomials nonnegative over finite sets, If A Technical Report AUT02-02, March 2002 |
| [31] | Putinar, M.: Positive polynomials on compact semi-algebraic sets. Ind. Univ. Math. J. 42, 203–206 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045 |
| [32] | Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. I-III. J. Symbolic Comput. 13 (3), 255–352 (1992) · Zbl 0763.68042 · doi:10.1016/S0747-7171(10)80003-3 |
| [33] | Reznick, B.: Some concrete aspects of Hilbert’s 17 th problem. In Contemporary Mathematics, volume 253, American Mathematical Society, 2000, pp 251–272 · Zbl 0972.11021 |
| [34] | Shafarevich. Basic algebraic geometry. Die Grundlehren der mathematischen Wissenschaften. Band 213. Springer-Verlag, 1974 |
| [35] | L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review 38, 49–95 (1996) · Zbl 0845.65023 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
