×

Border basis relaxation for polynomial optimization. (English) Zbl 1346.90655

Summary: A relaxation method based on border basis reduction which improves the efficiency of Lasserre’s approach is proposed to compute the infimum of a polynomial function on a basic closed semi-algebraic set. A new stopping criterion is given to detect when the relaxation sequence reaches the infimum, using a sparse flat extension criterion. We also provide a new algorithm to reconstruct a finite sum of weighted Dirac measures from a truncated sequence of moments, which can be applied to other sparse reconstruction problems. As an application, we obtain a new algorithm to compute zero-dimensional minimizer ideals and the minimizer points or zero-dimensional G-radical ideals. Experiments show the impact of this new method on significant benchmarks.

MSC:

90C22 Semidefinite programming
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

RAGlib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abril Bucero, M.; Mourrain, B., Exact relaxation for polynomial optimization on semi-algebraic sets (2013)
[2] Brachat, J.; Comon, P.; Mourrain, B.; Tsigaridas, E., Symmetric tensor decomposition, Linear Algebra Appl., 433, 1851-1872 (2010) · Zbl 1206.65141
[3] Demmel, J.; Nie, J.; Powers, V., Representations of positive polynomials on noncompact semialgebraic sets via kkt ideals, J. Pure Appl. Algebra, 209, 1, 189-200 (2007) · Zbl 1106.13028
[4] Elkadi, M.; Mourrain, B., Introduction à la résolution des systèmes d’équations algébriques, Mathématiques et Applications, vol. 59 (2007), Springer-Verlag
[5] Floudas, C. A.; Pardalos, P. M.; Adjiman, C. S.; Esposito, W. R.; Gumus, Z. H.; Harding, S. T.; Klepeis, J. L.; Meyer, C. A.; Schweiger, C. A., Handbook of Test Problems in Local and Global Optimization (1999), Kluwer Academic Publishers · Zbl 0943.90001
[6] Giesbrecht, M.; Labahn, G.; Lee, W.-S., Symbolic-numeric sparse interpolation of multivariate polynomials, J. Symb. Comput., 44, 8, 943-959 (Aug. 2009)
[7] Greuet, A.; Safey El Din, M., Deciding reachability of the infimum of a multivariate polynomial, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ISSAC ’11 (2011), ACM: ACM New York, NY, USA), 131-138 · Zbl 1323.65074
[8] Ha, H. V.; Pham, T., Representation of positive polynomials and optimization on noncompact semialgebraic sets, SIAM J. Optim., 20, 6, 3082-3103 (2010) · Zbl 1279.14071
[9] Henrion, D.; Lasserre, J., Positive polynomials in control, (Detecting Global Optimality and Extracting Solutions in GloptiPoly. Detecting Global Optimality and Extracting Solutions in GloptiPoly, Lectures Notes in Control and Information Sciences (2005), Springer), 293-310
[10] Lasserre, J., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817 (2001) · Zbl 1010.90061
[11] Lasserre, J., Moments, Positive Polynomials and Their Applications (2009), Imperial College Press
[12] Lasserre, J.; Laurent, M.; Rostalski, P., Semidefinite characterization and computation of real radical ideals, Found. Comput. Math., 8, 5, 607-647 (2008) · Zbl 1176.14010
[13] Lasserre, J.; Laurent, M.; Rostalski, P., A unified approach for real and complex zeros of zero-dimensional ideals, (Putinar, M.; Sullivant, S., Emerging Applications of Algebraic Geometry, vol. 149 (2009), Springer), 125-156 · Zbl 1171.12001
[14] Lasserre, J.-B.; Laurent, M.; Mourrain, B.; Rostalski, P.; Trébuchet, P., Moment matrices, border bases and real radical computation, J. Symb. Comput (2012)
[15] Laurent, M., Semidefinite representations for finite varieties, Math. Program., 109, 1-26 (2007) · Zbl 1152.90007
[16] Laurent, M.; Mourrain, B., A generalized flat extension theorem for moment matrices, Arch. Math. (Basel), 93, 1, 87-98 (July 2009)
[17] Ma, Y.; Wang, C.; Zhi, L., A certificate for semidefinite relaxations in computing positive dimensional real varieties (2013)
[18] Marshall, M., Representations of non-negative polynomials, degree bounds and applications to optimization, Can. J. Math., 61, 1, 205-221 (2009) · Zbl 1163.13019
[19] Mourrain, B., A new criterion for normal form algorithms, (Fossorier, M.; Imai, H.; Lin, S.; Poli, A., Proc. AAECC. Proc. AAECC, Lecture Notes in Computer Science, vol. 1719 (1999), Springer: Springer Berlin), 430-443 · Zbl 0976.12005
[20] Mourrain, B.; Trébuchet, P., Generalized normal forms and polynomials system solving, (Kauers, M., ISSAC: Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation (2005)), 253-260 · Zbl 1360.68947
[21] Mourrain, B.; Trébuchet, P., Stable normal forms for polynomial system solving, Theor. Comput. Sci., 409, 2, 229-240 (2008) · Zbl 1159.68045
[22] Mourrain, B.; Trébuchet, P., Border basis representation of a general quotient algebra, (van der Hoeven, J., ISSAC 2012 (2012)), 265-272 · Zbl 1323.68618
[23] Nesterov, Y.; Nemirovski, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), SIAM: SIAM Philaldelphia · Zbl 0824.90112
[24] Nie, J., An exact Jacobian SDP relaxation for polynomial optimization, Math. Program., 1-31 (2011)
[25] Nie, J., Certifying convergence of Lasserre’s hierarchy via flat truncation, Math. Program., 1-26 (2012)
[26] Nie, J.; Demmel, J.; Sturmfels, B., Minimizing polynomials via sum of squares over gradient ideal, Math. Program., 106, 3, 587-606 (2006) · Zbl 1134.90032
[27] Nie, J.; Wang, L., Semidefinite relaxations for best rank-1 tensor approximations (2013)
[28] Ottaviani, G.; Spaenlehauer, P.-J.; Sturmfels, B., Exact solutions in structured low-rank approximation (2013)
[29] Parrilo, P., Semidefinite programming relaxations for semialgebraic problems, Math. Program., Ser. B, 96, 2, 293-320 (2003) · Zbl 1043.14018
[30] Parrilo, P.; Sturmfels, B., Minimizing polynomial functions, (Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic. Proceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic, Geometry in Mathematics and Computer Science (2003), American Mathematical Society), 83-100 · Zbl 1099.13516
[31] Riener, C.; Theobald, T.; Andrén, L. J.; Lasserre, J. B., Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., 38, 1, 122-141 (Feb. 2013)
[32] Safey El Din, M., Computing the global optimum of a multivariate polynomial over the reals, (Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation. Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, ISSAC ’08 (2008), ACM: ACM New York, NY, USA), 71-78 · Zbl 1487.65072
[33] Shor, N., Class of global minimum bounds of polynomial functions, Cybernetics, 23, 731-734 (1987) · Zbl 0648.90058
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.