Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-06T11:14:58.896Z Has data issue: false hasContentIssue false
  • English
  • Français

The Moment-SOS hierarchy: Applications and related topics

Part of: Integral transforms, operational calculus General theory of linear operators Nontrigonometric harmonic analysis Hamilton-Jacobi theories, including dynamic programming

Published online by Cambridge University Press:  04 September 2024

Jean B. Lasserre Open the ORCID record for Jean B. Lasserre [Opens in a new window]
Jean B. Lasserre*
Affiliation:
LAAS-CNRS and Toulouse School of Economics (TSE), University of Toulouse, 7 Avenue du Colonel Roche, BP54200, 31031 Toulouse cédex 4, France E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The Moment-SOS hierarchy, first introduced in optimization in 2000, is based on the theory of the S-moment problem and its dual counterpart: polynomials that are positive on S. It turns out that this methodology can also be used to solve problems with positivity constraints ‘f(x) ≥ 0 for all $\mathbf{x}\in S$’ or linear constraints on Borel measures. Such problems can be viewed as specific instances of the generalized moment problem (GMP), whose list of important applications in various domains of science and engineering is almost endless. We describe this methodology in optimization and also in two other applications for illustration. Finally we also introduce the Christoffel function and reveal its links with the Moment-SOS hierarchy and positive polynomials.

MSC classification

Primary: 44A60: Moment problems 90C22: Semidefinite programming
Secondary: 42C05: Orthogonal functions and polynomials, general theory 47A57: Operator methods in interpolation, moment and extension problems 49L25: Viscosity solutions
Type
Research Article
Information
Acta Numerica , Volume 33 , July 2024 , pp. 841 - 908
Copyright
© The Author(s), 2024. Published by Cambridge University Press

References

Ahmadi, A. A. and Majumdar, A. (2019), DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebra Geometry 3, 193–230.10.1137/18M118935XCrossRefGoogle Scholar
Aloise, D. and Hansen, P. (2011), Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering, J. Global Optim. 49, 449–465.10.1007/s10898-010-9571-3CrossRefGoogle Scholar
Anjos, M. and Lasserre, J. B., eds (2012), Handbook on Semidefinite, Conic and Polynomial Optimization , Vol. 166 of International Series in Operations Research and Management Science, Springer.10.1007/978-1-4614-0769-0CrossRefGoogle Scholar
Aylward, E. M., Parrilo, P. A. and Slotine, J.-J. E. (2008), Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming, Automatica 44, 2163–2170.10.1016/j.automatica.2007.12.012CrossRefGoogle Scholar
Bacari, F., Gogolin, C., Wittek, P. and Acín, A. (2020), Verifying the output of quantum optimizers with ground-state energy lower bounds, Phys. Rev. Res. 2, art. 043163.10.1103/PhysRevResearch.2.043163CrossRefGoogle Scholar
Bach, F. and Rudi, A. (2023), Exponential convergence of Sum-of-Squares hierarchies for trigonometric polynomials, SIAM J. Optim. 33, 2137–2159.10.1137/22M1540818CrossRefGoogle Scholar
Bachoc, C. and Vallentin, F. (2008), New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21, 909–924.10.1090/S0894-0347-07-00589-9CrossRefGoogle Scholar
Bachoc, C., Passuello, A. and Vallentin, F. (2013), Bounds for projective codes from semidefinite programming, Adv. Math. Commun. 7, 127–145.10.3934/amc.2013.7.127CrossRefGoogle Scholar
Bafna, M., Barak, B., Kothari, P. K., Schramm, T. and Steurer, D. (2021), Playing unique games on certified small-set expanders, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , Association for Computing Machinery (ACM), pp. 1629–1642.10.1145/3406325.3451099CrossRefGoogle Scholar
Baldi, L. and Mourrain, B. (2022), Exact moment representation in Polynomial Optimization. Available at arXiv:2012:14652.Google Scholar
Barak, B. and Steurer, D. (2014), Sum-of-squares proofs and the quest towards optimal algorithms, in Proceedings of the International Congress of Mathematicians (ICM 2014) (Sang, S. Y. et al., eds), Kyung Moon Sa, pp. 509–533.Google Scholar
Baran, M. (1995), Complex equilibrium measure and Bernstein type theorems for compact sets in ${\mathrm{\mathbb{R}}}^n$ , Proc. Amer. Math. Soc. 123, 485–494.Google Scholar
Bedford, E. and Taylor, B. A. (1986), The complex equilibrium measure of a symmetric convex set in ${\mathrm{\mathbb{R}}}^n$ , Trans. Amer. Math. Soc. 294, 705–717.Google Scholar
Bertsimas, D. and Popescu, I. (2005), Optimal inequalities in probability theory: A convex optimization approach, SIAM J. Optim. 15, 780–804.10.1137/S1052623401399903CrossRefGoogle Scholar
Blekherman, G., Parrilo, P. and Thomas, R., eds (2012), Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization, SIAM.10.1137/1.9781611972290CrossRefGoogle Scholar
Burgdorf, S., Klep, I. and Povh, J. (2016), Optimization of Polynomials in Non-Commuting Variables, SpringerBriefs in Mathematics, Springer.Google Scholar
Chen Tong, J. B. Lasserre, Magron, V. and Pauwels, E. (2021), Semialgebraic representation of monotone deep equilibrium models and application to certification, in Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (Ranzato, M. et al., eds), Curran Associates, pp. 27146–27159.Google Scholar
Cicconet, F. and Almeida, K. C. (2019), Moment-SOS relaxation of the medium term hydrothermal dispatch problem, Int. J. Elec. Power Energy Systems 104, 124–133.10.1016/j.ijepes.2018.06.004CrossRefGoogle Scholar
Courtier, N. E., Drummond, R., Ascensio, P., Couto, L. D. and Howey, D. A. (2022), Discretisation-free battery fast-charging optimisation using the measure-moment approach, in 2022 European Control Conference (ECC) , IEEE, pp. 628–634.10.23919/ECC55457.2022.9838296CrossRefGoogle Scholar
de Castro, Y., Gamboa, F., Henrion, D. and Lasserre, J. B. (2017), Exact solutions to super resolution on semi-algebraic domains in higher dimensions, IEEE Trans. Inform. Theory 63, 621–630.10.1109/TIT.2016.2619368CrossRefGoogle Scholar
de Castro, Y., Gamboa, F., Henrion, D., Hess, R. and Lasserre, J. B. (2019), Approximate optimal designs for multivariate polynomial regression, Ann . Statist. 47, 125–157.10.1214/18-AOS1683CrossRefGoogle Scholar
de Klerk, E. and Laurent, M. (2011), On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM J. Optim. 21, 824–832.10.1137/100814147CrossRefGoogle Scholar
de Laat, D. (2020), Moment methods in energy minimization: New bounds for Riesz minimal energy problems, Trans. Amer. Math. Soc. 373, 1407–1453.10.1090/tran/7976CrossRefGoogle Scholar
de Laat, D., Machado, F. C., de Oliveira Filho, F. M. and Vallentin, F. (2022), k-point semidefinite programming bounds for equiangular lines, Math. Program. 194, 533–567.10.1007/s10107-021-01638-xCrossRefGoogle Scholar
Doherty, A. C., Parrilo, P. A. and Spedalieri, F. (2005), Detecting multipartite entanglement, Phys. Rev. A 71, art. 032333.10.1103/PhysRevA.71.032333CrossRefGoogle Scholar
Dostert, M. and Vallentin, F. (2020), New dense superball packings in three dimensions, Adv. Geom. 20, 473–482.10.1515/advgeom-2020-0002CrossRefGoogle Scholar
Dowdy, G. R. and Barton, P. I. (2018), Dynamics bounds on stochastic chemical kinetic systems using semidefinite programming, J. Chem. Phys. 149, art. 74103.10.1063/1.5029926CrossRefGoogle ScholarPubMed
Dyer, M. E. and Frieze, A. M. (1988), The complexity of computing the volume of a polyhedron, SIAM J. Comput. 17, 967–974.10.1137/0217060CrossRefGoogle Scholar
Eckhoff, K. S. (1993), Accurate and efficient reconstruction of discontinuous functions from truncated series expansions, Math. Comp. 61(204), 745–763.10.1090/S0025-5718-1993-1195430-1CrossRefGoogle Scholar
Eisert, J., Hyllus, P., Gühne, O. and Curty, M. (2004), Complete hierarchies of efficient approximations to problems in entanglement theory, Phys. Rev. A 70, art. 062317.10.1103/PhysRevA.70.062317CrossRefGoogle Scholar
Fan, J., Nie, J. and Zhou, A. (2018), Tensor eigenvalue complementarity problems, Math. Program. Ser. A 170, 507–539.10.1007/s10107-017-1167-yCrossRefGoogle Scholar
Fang, K. and Fawzi, H. (2021), The sum-of-squares hierarchy on the sphere and applications in quantum information theory, Math. Program. 190, 331–360.10.1007/s10107-020-01537-7CrossRefGoogle Scholar
Fantuzzi, G., Goluskin, D., Huang, D. and Chernyshenko, S. I. (2016), Bounds for deterministic and stochastic dynamical systems using sum-of-squares optimization, SIAM J. Appl. Dyn. Systems 15, 1962–1988.10.1137/15M1053347CrossRefGoogle Scholar
Fattorini, H. O. (1999), Infinite Dimensional Optimization , Cambridge University Press.10.1017/CBO9780511574795CrossRefGoogle Scholar
Gepp, A., Harris, G. and Vanstone, B. (2020), Financial applications of semidefinite programming: A review and call for interdisciplinary research, Account. Finance 60, 3527–3555.10.1111/acfi.12543CrossRefGoogle Scholar
Goemans, M. X. and Williamson, D. P. (1995), Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42, 1115–1145.10.1145/227683.227684CrossRefGoogle Scholar
Goluskin, D. and Fantuzzi, G. (2019), Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming, Nonlinearity 32, 1705–1730.10.1088/1361-6544/ab018bCrossRefGoogle Scholar
Handelman, D. (1988), Representing polynomials by positive linear functions on compact convex polyhedra, Pacific J. Math. 132, 35–62.10.2140/pjm.1988.132.35CrossRefGoogle Scholar
Haussmann, D., Liers, F., Stingl, M. and Vera, J. C. (2018), Deciding robust feasibility and infeasibility using a set containment approach: An application to stationary passive gas network operations, SIAM J. Optim. 28, 2489–2517.Google Scholar
Henrion, D. and Garulli, A., eds (2005), Positive Polynomials in Control , Vol. 312 of Lecture Notes on Control and Information Sciences, Springer.10.1007/b96977CrossRefGoogle Scholar
Henrion, D. and Lasserre, J. B. (2022), Graph recovery from incomplete moment information, Constr. Approx. 56, 165–187.10.1007/s00365-022-09563-8CrossRefGoogle Scholar
Henrion, D., Korda, M. and Lasserre, J. B. (2021), The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry , Control and Nonlinear PDEs , Vol. 4 of Optimization and Applications, World Scientific.Google Scholar
Henrion, D., Lasserre, J. B. and Savorgnan, C. (2009), Approximate volume and integration for basic semi-algebraic sets, SIAM Rev. 51, 722–743.10.1137/080730287CrossRefGoogle Scholar
Pan, Jie and Jiang, Fu (2020), Low complexity beamspace super resolution for DOA estimation of linear array, Sensors 20, art. 2222.10.3390/s20082222CrossRefGoogle ScholarPubMed
Khot, S. (2010), Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry, in Proceedings of the 2010 International Congress of Mathematicians (ICM 2010) (Bhatia, R. et al., eds), Vol. IV, Hindustan Book Agency, pp. 2676–2697.Google Scholar
Khot, S. (2014), Hardness of approximation, in Proceedings of the 2014 International Congress of Mathematicians (ICM 2014) (Sang, S. Y. et al., eds), Kyung Moon Sa, pp. 711–728.Google Scholar
Kojima, M., Kim, S. and Maramatsu, M. (2005), Sparsity in sums of squares of squares of polynomials, Math. Program. 103, 45–62.10.1007/s10107-004-0554-3CrossRefGoogle Scholar
Korda, M., Henrion, D. and Jones, C. N. (2014), Convex computation of the maximum controlled invariant set for polynomial control systems, SIAM J. Control Optim. 52, 2944–2969.10.1137/130914565CrossRefGoogle Scholar
Korda, M., Henrion, D. and Lasserre, J. B. (2022), Moments and convex optimization for analysis and control of nonlinear PDEs, in Numerical Control: Part A (Trélat, E. and Zuazua, E., eds), Vol. 23 of Handbook of Numerical Analysis, Elsevier, pp. 339–366.10.1016/bs.hna.2021.12.010CrossRefGoogle Scholar
Kočvara, M., Mourrain, B. and Riener, C., eds (2023), Polynomial Optimization, Moments, and Applications, Springer Optimization and its Applications, Springer.10.1007/978-3-031-38659-6CrossRefGoogle Scholar
Krivine, J. L. (1964a), Anneaux préordonnés, J. Anal. Math. 12, 307–326.10.1007/BF02807438CrossRefGoogle Scholar
Krivine, J. L. (1964b), Quelques propriétés des préordres dans les anneaux commutatifs unitaires, C.R . Acad. Sci. Paris 258, 3417–3418.Google Scholar
Landau, H. (1987), Classical background of the moment problem, in Moments in Mathematics , Vol. 37 of Proceedings of Symposia in Applied Mathematics, American Mathematical Society (AMS), pp. 1–15.10.1090/psapm/037/921082CrossRefGoogle Scholar
Laraki, R. and Lasserre, J. B. (2012), Semidefinite programming for min-max problems and games, Math. Program. Ser. A 131, 305–332.10.1007/s10107-010-0353-yCrossRefGoogle Scholar
Lasserre, J. B. (2000), Optimisation globale et théorie des moments, C.R. Acad. Sci. Paris, Sér. I 331, 929–934.10.1016/S0764-4442(00)01750-XCrossRefGoogle Scholar
Lasserre, J. B. (2001), Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11, 796–817.10.1137/S1052623400366802CrossRefGoogle Scholar
Lasserre, J. B. (2002a), Bounds on measures satisfying moment conditions, Ann. Appl. Prob. 12, 1114–1137.10.1214/aoap/1031863183CrossRefGoogle Scholar
Lasserre, J. B. (2002b), Semidefinite programming vs. LP relaxations for polynomial programming, Math. Oper. Res. 27, 347–360.10.1287/moor.27.2.347.322CrossRefGoogle Scholar
Lasserre, J. B. (2006), Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim. 17, 822–843.10.1137/05064504XCrossRefGoogle Scholar
Lasserre, J. B. (2009a), Convexity in semi-algebraic geometry and polynomial optimization, SIAM J. Optim. 19, 1995–2014.10.1137/080728214CrossRefGoogle Scholar
Lasserre, J. B. (2009b), Moments, Positive Polynomials and their Applications , Imperial College Press.10.1142/p665CrossRefGoogle Scholar
Lasserre, J. B. (2011), A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, 864–885.10.1137/100806990CrossRefGoogle Scholar
Lasserre, J. B. (2013), The K-moment problem for continuous functionals, Trans. Amer. Math. Soc. 365, 2489–2504.10.1090/S0002-9947-2012-05701-1CrossRefGoogle Scholar
Lasserre, J. B. (2015), An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge University Press.10.1017/CBO9781107447226CrossRefGoogle Scholar
Lasserre, J. B. (2017), Computing Gaussian & exponential measures of semi-algebraic sets, Adv. Appl. Math. 91, 137–163.10.1016/j.aam.2017.06.006CrossRefGoogle Scholar
Lasserre, J. B. (2021), Connecting optimization with spectral analysis of tri-diagonal matrices, Math. Program. Ser. A 190, 795–809.10.1007/s10107-020-01549-3CrossRefGoogle Scholar
Lasserre, J. B. (2022), A disintegration of the Christoffel function, Comptes Rendus Math. 360, 1071–1079.10.5802/crmath.380CrossRefGoogle Scholar
Lasserre, J. B. (2023), Pell’s equation, sum-of-squares and equilibrium measures on a compact set, Comptes Rendus Math. 361, 935–952.10.5802/crmath.465CrossRefGoogle Scholar
Lasserre, J. B. and Pauwels, E. (2016), Sorting out typicality via the inverse moment matrix SOS polynomial, in Advances in Neural Information Processing Systems 29 (NIPS2016) (Lee, D. et al., eds), Curran Associates, pp. 190–198.Google Scholar
Lasserre, J. B. and Priéto-Rumeau, T. (2004), SDP vs. LP relaxations for the Moment approach in some performance evaluation problems, Stoch. Models 20, 439–456.10.1081/STM-200033112CrossRefGoogle Scholar
Lasserre, J. B. and Xu, Y. (2023), A generalized Pell’s equation for a class of multivariate orthogonal polynomials. Technical report, LAAS-CNRS, Toulouse, France. Available at hal-04163153v1. To appear in Trans. Amer. Math. Soc. Google Scholar
Lasserre, J. B., Henrion, D., Prieur, C. and Trélat, E. (2008), Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM J. Control Optim. 47, 1649–1666.10.1137/070685051CrossRefGoogle Scholar
Lasserre, J. B., Pauwels, E. and Putinar, M. (2022), The Christoffel Function for Data Analysis , Cambridge University Press.Google Scholar
Lasserre, J. B., Priéto-Rumeau, T. and Zervos, M. (2006), Pricing a class of exotic options via moments and SDP relaxations, Math. Finance 16, 469–494.10.1111/j.1467-9965.2006.00279.xCrossRefGoogle Scholar
Latorre, F., Rolland, P. and Cevher, V. (2020), Lipschitz constant estimation for neural networks via sparse polynomial optimization, in 8th International Conference on Learning Representations (ICLR 2020), OpenReview.Google Scholar
Laurent, M. (2003), A comparison of the Sherali–Adams, Lovász–Schrijver and Lasserre relaxations for 0-1 programming, Math. Oper. Res. 28, 470–496.10.1287/moor.28.3.470.16391CrossRefGoogle Scholar
Laurent, M. (2008), Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry (Putinar, M. and Sullivant, S., eds), Vol. 149 of The IMA Volumes in Mathematics and its Applications, Springer, pp. 157–270.10.1007/978-0-387-09686-5_7CrossRefGoogle Scholar
Laurent, M. and Slot, L. (2023), An effective version of Schmüdgen’s Positivstellensatz for the hypercube, Optim. Lett. 17, 515–530.10.1007/s11590-022-01922-5CrossRefGoogle Scholar
Magron, V. and Wang, J. (2023), Sparse Polynomial Optimization: Theory and Practice , Series on Optimization and its Applications, World Scientific.10.1142/q0382CrossRefGoogle Scholar
Majumdar, A., Hall, G. and Ahmadi, A. A. (2020), A survey of recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics, Annu. Rev. Control Robot Auton. Syst. 3, 331–60.10.1146/annurev-control-091819-074326CrossRefGoogle Scholar
Marmin, A., Castella, M., Pesquet, J.-C. and Duval, L. (2021), Sparse signal reconstruction for nonlinear models via piecewise rational optimization, Signal Process. 179, art. 107835.10.1016/j.sigpro.2020.107835CrossRefGoogle Scholar
Marschner, Z., Palmer, D., Zhang, P. and Solomon, J. (2020), Hexahedral mesh repair via sum-of-squares relaxations, Comput. Graph. Forum 39, 133–147.10.1111/cgf.14074CrossRefGoogle Scholar
Marschner, Z., Palmer, D., Zhang, P. and Solomon, J. (2021), Sum-of-squares geometry processing, ACM Trans. Graphics 40, 1–13.10.1145/3478513.3480551CrossRefGoogle Scholar
Marshall, M. (2008), Positive Polynomials and Sums of Squares , Vol. 146 of AMS Math. Surveys and Monographs, American Mathematical Society (AMS).10.1090/surv/146CrossRefGoogle Scholar
Marx, S., Pauwels, E., Weisser, T., Henrion, D. and Lasserre, J. B. (2021), Semi-algebraic approximation using Christoffel–Darboux kernel, Constr. Approx. 54, 391–429.10.1007/s00365-021-09535-4CrossRefGoogle Scholar
Marx, S., Weisser, T., Henrion, D. and Lasserre, J. B. (2020), A moment approach for entropy solutions to nonlinear hyperbolic PDEs, Math. Control Related Fields 10, 113–140.10.3934/mcrf.2019032CrossRefGoogle Scholar
Molzahn, D. and Josz, C. (2018), Lasserre hierarchy for large-scale polynomial optimization in real and complex variabales, SIAM J. Optim. 28, 1017–1048.Google Scholar
Molzhan, D. and Hiskens, I. (2015), Sparsity-exploiting moment-based relaxations of the optimal power flow problem, IEEE Trans. Power Systems 30, 3168–3180.10.1109/TPWRS.2014.2372478CrossRefGoogle Scholar
Moussa, K., Fiacchini, M. and Alamir, M. (2020), Robust optimal scheduling of combined chemo- and immunotherapy: Considerations on chemotherapy detrimental effects, in Proceedings of the 2020 American Control Conference (ACC) , IEEE, pp. 4252–4257.10.23919/ACC45564.2020.9147869CrossRefGoogle Scholar
Navascués, M., Pironio, S. and Acín, A. (2012), SDP relaxations for non-commutative polynomial optimization, in Handbook on Semidefinite, Conic and Polynomial Optimization (Anjos, M. and Lasserre, J. B., eds), Vol. 166 of International Series in Operations Research and Management Science, Springer, pp. 601–634.10.1007/978-1-4614-0769-0_21CrossRefGoogle Scholar
Nesterov, Y. (2000), Squared functional systems and optimization problems, in High Performance Optimization (Frenk, H. et al., eds), Kluwer, pp. 405–440.10.1007/978-1-4757-3216-0_17CrossRefGoogle Scholar
Nevai, P. and Freud, G. (1986), Orthogonal polynomials and christoffel functions, J. Approx. Theory 48, 3–167.10.1016/0021-9045(86)90016-XCrossRefGoogle Scholar
Mai, Ngoc Hoang Anh, Lasserre, J. B. and Magron, V. (2023), A hierarchy of spectral relaxations for polynomial optimization, Math. Program. Comput 15, 651–701.10.1007/s12532-023-00243-7CrossRefGoogle Scholar
Mai, Ngoc Hoang Anh, Lasserre, J. B., Magron, V. and Wang, J. (2022), Exploiting constant trace property in large scale polynomial optimization, ACM Trans. Math. Software 48, art. 40.10.1145/3555309CrossRefGoogle Scholar
Nie, J. (2009), Sum of squares method for sensor network localization, Comput. Optim. Appl. 43, 151–179.10.1007/s10589-007-9131-zCrossRefGoogle Scholar
Nie, J. (2013), Certifying convergence of Lasserre’s hierarchy via flat truncation, Math. Program. Ser. A 142, 485–510.10.1007/s10107-012-0589-9CrossRefGoogle Scholar
Nie, J. (2014), Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program. Ser. A 146, 97–121.10.1007/s10107-013-0680-xCrossRefGoogle Scholar
Nie, J. (2017), Low rank symmetric tensor approximations, SIAM J. Matrix Anal. Appl. 38, 1517–1540.10.1137/16M1107528CrossRefGoogle Scholar
Nie, J. (2023), Moment and Polynomial Optimization , Vol. 31 of MOS/SIAM Series in Optimization, SIAM.10.1137/1.9781611977608CrossRefGoogle Scholar
Nie, J. and Demmel, J. (2008), Sparse SOS relaxations for minimizing functions that are summations of small polynomials, SIAM J. Optim. 19, 1534–1558.10.1137/060668791CrossRefGoogle Scholar
Nie, J. and Tang, X. (2023), Convex generalized nash equilibrium problems and polynomial optimization, Math. Program. 198, 1485–1518.10.1007/s10107-021-01739-7CrossRefGoogle Scholar
Nie, J. and Yang, Z. (2020), Hermitian tensor decompositions, SIAM J. Matrix Anal. Appl. 41, 1115–1144.10.1137/19M1306889CrossRefGoogle Scholar
O’Donnell, R. (2017), SoS is not fully automatizable, even approximately, in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) (Papadimitriou, C. H., ed.), Vol. 67 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 59:1–59:10.Google Scholar
Parekh, O. (2023), Synergies between operations research and quantum information science, INFORMS J. Comput. 35, 266–273.10.1287/ijoc.2023.1268CrossRefGoogle Scholar
Parekh, O. and Thompson, K. (2021), Application of the level-2 quantum Lasserre hierarchy in quantum approximation algorithms, in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Bansal, N. et al., eds), Vol. 198 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 102:1–102:20.Google Scholar
Parrilo, P. A. (2000), Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, Pasadena, CA.Google Scholar
Parrilo, P. A. (2003), Semidefinite programming relaxations for semialgebraic problems, Math. Program. 96, 293–320.10.1007/s10107-003-0387-5CrossRefGoogle Scholar
Parrilo, P. A. and Lall, S. (2003), Semidefinite programming relaxations and algebraic optimization in control, Eur. J. Control 9, 307–321.10.3166/ejc.9.307-321CrossRefGoogle Scholar
Pauwels, E., Henrion, D. and Lasserre, J. B. (2017), Positivity certificates in optimal control, in Geometric and Numerical Foundations of Movements (Laumond, J. P. et al., eds), Vol. 117 of Springer Tracts in Advanced Robotics, Springer, pp. 113–132.10.1007/978-3-319-51547-2_6CrossRefGoogle Scholar
Prestel, A. and Denzel, C. N. (2001), Positive Polynomials , Springer Monographs in Mathematics, Springer.10.1007/978-3-662-04648-7CrossRefGoogle Scholar
Probst, T., Paudel, D. D., Chhatkuli, A. and Van Gool, L. (2019), Convex relaxations for consensus and non-minimal problems in 3D vision, in Proceedings of the 2019 IEEE International Conference on Computer Vision (ICCV) , IEEE, pp. 10233–10242.Google Scholar
Putinar, M. (1993), Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42, 969–984.10.1512/iumj.1993.42.42045CrossRefGoogle Scholar
Raghavendra, P., Schramm, T. and Steurer, D. (2018), High dimensional estimation via sum-of-squares proofs, in Proceedings of the International Congress of Mathematicians (ICM 2018) (Sirakov, B. et al., eds), World Scientific, pp. 3389–3423.Google Scholar
Rosen, D. M., Carlone, L., Bandera, A. S. and Leonard, J. J. (2019), Se-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group, Int. J. Robotics Research 38, 95–125.10.1177/0278364918784361CrossRefGoogle Scholar
Schmüdgen, K. (1991), The K-moment problem for compact semi-algebraic sets, Math. Ann. 289, 203–206.10.1007/BF01446568CrossRefGoogle Scholar
Schmüdgen, K. (2017), The Moment Problem, Graduate Texts in Mathematics, Springer.Google Scholar
Schweighofer, M. (2005), On the complexity of Schmüdgen’s Positivstellensatz, J. Complexity 20, 529–543.10.1016/j.jco.2004.01.005CrossRefGoogle Scholar
Sedighi, S., Mishra, K. V., Shankar, B. and Ottersten, M. R. B. (2021), Localization with 1-Bit passive radars in Narrow Band IoT-applications using multivariate polynomial optimization, IEEE Trans. Signal Process. 69, 2525–2540.10.1109/TSP.2021.3072834CrossRefGoogle Scholar
Selby, J. H., Sainz, A. B., Magron, V., Czekaj, L. and Horodecki, M. (2023), Correlations constrained by composite measurements, Quantum 7, art. 1080.10.22331/q-2023-08-10-1080CrossRefGoogle Scholar
Sherali, H. D. and Adams, W. P. (1990), A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math. 3, 411–430.10.1137/0403036CrossRefGoogle Scholar
Sherali, H. D. and Adams, W. P. (1999), A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems , Kluwer.10.1007/978-1-4757-4388-3CrossRefGoogle Scholar
Shor, N. Z. (1987), Quadratic optimization problems, Tekhnicheskaya Kibernetika 1, 128–139.Google Scholar
Simon, B. (2008), The Christoffel–Darboux kernel, in Perspectives in Partial Differential Equations, Harmonic Analysis and Applications , Vol. 79 of Proceedings of Symposia in Pure Mathematics, American Mathematical Society (AMS), pp. 295–335.10.1090/pspum/079/2500498CrossRefGoogle Scholar
Slot, L. (2022), Sum-of-Ssquares hierarchies for polynomial optimization and the Christoffel–Darboux kernel, SIAM J. Optim. 32, 2612–2635.10.1137/21M1458338CrossRefGoogle Scholar
Slot, L. and Laurent, M. (2021), Near optimal analysis of Lasserre’s univariate measure-based bounds for multivariate polynomial optimization, Math. Program. 188, 443–460.10.1007/s10107-020-01586-yCrossRefGoogle Scholar
Stein, N., Ozdaglar, A. and Parrilo, P. A. (2008), Separable and low-rank continuous games, Int. J. Game Theory 37, 457–474.10.1007/s00182-008-0129-2CrossRefGoogle Scholar
Tacchi, M., Lasserre, J. B. and Henrion, D. (2023), Stokes, Gibbs and volume computation of semi-algebraic sets, Discrete Comput. Geom. 69, 260–283.10.1007/s00454-022-00462-0CrossRefGoogle Scholar
Tacchi, M., Weisser, T., Lasserre, J. B. and Henrion, D. (2021), Exploiting sparsity in semi-algebraic set volume computation, Found. Comput. Math. 22, 161–209.10.1007/s10208-021-09508-wCrossRefGoogle Scholar
Tian, J., Wei, H. and Tan, J. (2015), Global optimization for power dispatch problems based on theory of moments, Int. J. Electr. Power Energy Syst. 71, 184–194.10.1016/j.ijepes.2015.02.018CrossRefGoogle Scholar
Tyburec, M., Zeman, J., Kruzik, M. and Henrion, D. (2021), Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy, Struct. Multidiscipl. Optim. 64, 1963–1981.10.1007/s00158-021-02957-5CrossRefGoogle Scholar
Vasilescu, F.-H. (2003), Spectral measures and moment problems, in Spectral Theory and its Applications , Vol. 2 of Theta Series in Advanced Mathematics, Theta, pp. 173–215.Google Scholar
Vinter, R. (1993), Convex duality and nonlinear optimal control, SIAM J. Control Optim. 31, 518–538.10.1137/0331024CrossRefGoogle Scholar
Waki, S., Kim, S., Kojima, M. and Maramatsu, M. (2006), Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim. 17, 218–242.10.1137/050623802CrossRefGoogle Scholar
Wang, J., Li, H. and Xia, B. (2019), A new sparse SOS decomposition algorithm based on term sparsity, in Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation (ISSAC ’19), Association for Computing Machinery (ACM), pp. 347–354.10.1145/3326229.3326254CrossRefGoogle Scholar
Wang, J., Magron, V. and Lasserre, J. B. (2021), TSSOS: A moment-SOS hierarchy that exploits term sparsity, SIAM J. Optim. 31, 30–58.10.1137/19M1307871CrossRefGoogle Scholar
Wang, J., Magron, V., Lasserre, J. B. and Mai, Ngoc Hoang Anh (2022), CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization, ACM Trans. Math. Software 48, 1–26.10.1145/3569709CrossRefGoogle Scholar
Wittek, P., Darányi, S. and Nelhans, G. (2017), Ruling out static latent homophily in citation networks, Scientometrics 110, 765–777.10.1007/s11192-016-2194-9CrossRefGoogle ScholarPubMed
Ji, Xiangfeng, Ban, Xuegang (Jeff), Zhang, Jian and Ran, Bin (2019), Moment-based travel time reliability assessment with Lasserre’s relaxation, Transp. B 7, 401–422.Google Scholar
Yang, H. and Carlone, L. (2020), In perfect shape: Certifiably optimal 3D shape reconstruction from 2D landmarks, in Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) , IEEE, pp. 618–627.10.1109/CVPR42600.2020.00070CrossRefGoogle Scholar
Yang, H. and Carlone, L. (2023), Certifiably optimal outlier-robust geometric perception: Semidefinite relaxations and scalable global optimization, IEEE Trans. Pattern Anal. Mach. Intell. 45, 2816–2834.Google ScholarPubMed
Yang, H. and Pavone, M. (2023), Object pose estimation with statistical guarantees: Conformal keypoint detection and geometric uncertainty propagation, in Proceedings of the 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) , IEEE, pp. 8947–8958.10.1109/CVPR52729.2023.00864CrossRefGoogle Scholar
Yang, H., Shi, J. and Carlone, L. (2020), TEASER: Fast and certifiable point cloud registration, IEEE Trans. Robotics 37, 314–333.10.1109/TRO.2020.3033695CrossRefGoogle Scholar
Yurtsever, A., Tropp, J. A., Fercoq, O., Udell, M. and Cevher, V. (2021), Scalable semidefinite programming, SIAM J. Math. Data Sci. 3, 171–200.10.1137/19M1305045CrossRefGoogle Scholar