A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

DOI10.1007/978-3-030-21170-7_1zbMATH Open1436.90099arXiv1811.05439OpenAlexW2972919843MaRDI QIDQ3296188FDOQ3296188

Authors: E. de Klerk, Monique Laurent 

Publication date: 7 July 2020

Published in: Association for Women in Mathematics Series (Search for Journal in Brave)

Abstract: The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, due to J.B. Lasserre, is to approximate the convex cone of positive Borel measures by finite dimensional outer and inner conic approximations. We will review some results on these approximations, with a special focus on the convergence rate of the hierarchies of upper and lower bounds for the general problem of moments that are obtained from these inner and outer approximations.

Full work available at URL: https://arxiv.org/abs/1811.05439

Recommendations

• A semidefinite programming approach to the generalized problem of moments
• Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere
• Moments, positive polynomials and their applications
• A semidefinite approach for truncated \(K\)-moment problems
• Positive polynomials and semidefinite programming

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Cites Work

• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Global optimization with polynomials and the problem of moments
• Approximation Theory and Harmonic Analysis on Spheres and Balls
• Title not available (Why is that?)
• The \(K\)-moment problem for compact semi-algebraic sets
• On duality theory of conic linear problems.
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• Moments of non-negative mass
• GloptiPoly 3: moments, optimization and semidefinite programming
• Sums of squares, moment matrices and optimization over polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The proof of Tchakaloff’s Theorem
• A semidefinite programming approach to the generalized problem of moments
• An encyclopaedia of cubature formulas.
• Orthogonal polynomials of several variables
• Maxima for Graphs and a New Proof of a Theorem of Turán
• The General Moment Problem, A Geometric Approach
• On the complexity of Putinar's Positivstellensatz
• Solution of the truncated complex moment problem for flat data
• The Five-Electron Case of Thomson’s Problem
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Title not available (Why is that?)
• On the complexity of Schmüdgen's Positivstellensatz
• An introduction to polynomial and semi-algebraic optimization
• An epsilon of room. I: Real analysis. Pages from year three of a mathematical blog
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• A note on Tchakaloff’s Theorem
• Simulated Annealing for Convex Optimization
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Title not available (Why is that?)
• How to Integrate a Polynomial over a Sphere
• Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• On the convergence rate of grid search for polynomial optimization over the simplex
• Strong duality in lasserre's hierarchy for polynomial optimization
• Quadrature-based polynomial optimization
• Bound-constrained polynomial optimization using only elementary calculations
• Extensions of Gauss quadrature via linear programming
• Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies
• The moment problem
• Distributionally robust optimization with polynomial densities: theory, models and algorithms
• Cubature, approximation, and isotropy in the hypercube
• Optimization over polynomials: selected topics
• Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing

Cited In (19)

• A framework of distributionally robust possibilistic optimization
• Global minimization of polynomial integral functionals
• A semidefinite programming approach to the generalized problem of moments
• Generalized truncated moment problems with unbounded sets
• Moments, positive polynomials and their applications
• Minimizing rational functions: a hierarchy of approximations via pushforward measures
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
• Finite convergence of moment-SOS relaxations with nonreal radical ideals
• Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
• Distributionally robust possibilistic optimization problems
• Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
• Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
• Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares hierarchies for binary polynomial optimization
• A distributional Farkas' lemma and moment optimization problems with no-gap dual semi-definite programs
• Title not available (Why is that?)
• Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

Uses Software

• GloptiPoly

This page was built for publication: A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3296188)