Abstract
We consider the global minimization of a polynomial on a compact set \(\mathbf {B}\). We show that each step of the Moment-SOS hierarchy has a nice and simple interpretation that complements the usual one. Namely, it computes coefficients of a polynomial in an orthonormal basis of \(L^2(\mathbf {B},\mu )\) where \(\mu \) is an arbitrary reference measure whose support is exactly \(\mathbf {B}\). The resulting polynomial is a certain density (with respect to \(\mu \)) of some signed measure on \(\mathbf {B}\). When some relaxation is exact (which generically takes place) the coefficients of the optimal polynomial density are values of orthonormal polynomials at the global minimizer and the optimal (signed) density is simply related to the Christoffel–Darboux (CD) kernel and the Christoffel function associated with \(\mu \). In contrast to the hierarchy of upper bounds which computes positive densities, the global optimum can be achieved exactly as integration against a polynomial (signed) density because the CD-kernel is a reproducing kernel, and so can mimic a Dirac measure (as long as finitely many moments are concerned).
Similar content being viewed by others
References
de Klerk, E., Laurent, M.: Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial optimization on the sphere. Math. Program. (2020) (To appear)
Doherty, A.C., Wehner, S.: Convergence of SDP hierarchies for polynomial optimization on the hypersphere. ar**v:1210.5048, (2012)
Dunkl, C., Xu, Y.: Orthogonal Polynomials of Several Variables. Cambridge University Press, Cambridge (2001)
Fang, K., Fawzi, H.: The sum-of-squares hierarchy on the sphere, and applications in quantum information theory. Math. Program. (2020) (To appear)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments SIAM. J. Optim. 11, 796–817 (2001)
Lasserre, J.B.: A new look at nonnegativity on closed sets and polynomial optimization SIAM. J. Optim. 21, 864–885 (2011)
Lasserre, J.B.: An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge (2015)
Lasserre, J.B.: Connecting optimization with spectral analysis of tri-diagonal matrices. Math. Program. (2020) (To appear)
Nie, J.: Optimality conditions and finite convergence of Lasserre’s. Hierarchy Math. Program. Ser. A 146(1–2), 97–121 (2014)
Putinar, M.: Positive polynomial on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969–984 (1993)
Slot, L., Laurent, M.: Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Math. Program. (2020) (To appear)
Slot, L., Laurent, M.: Near-optimal analysis of univariate moment bounds for polynomial optimization. Math. Program. (2020) (To appear)
Slot, L., Laurent, M.: Sum-of-squares hierarchies for binary polynomial optimization. ar**v:2011.04027
Acknowledgements
Work partly funded by the AI Interdisciplinary Institute ANITI through the French “Investing for the Future PI3A” program under the Grant agreement ANR-19-PI3A-0004
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The author declare no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Lasserre, J.B. The moment-SOS hierarchy and the Christoffel–Darboux kernel. Optim Lett 15, 1835–1845 (2021). https://doi.org/10.1007/s11590-021-01713-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-021-01713-4