Optimal data fitting: a moment approach

DOI10.1137/18M1170108MaRDI QIDQ4555461zbMATH OpenOpenAlexWikidataFDO

Authors Victor Magron, Jean B. Lasserre

Publication date 20 November 2018

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingseparation problemmoment relaxationsminimum-volume covering ellipsoid

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Abstract: We propose a moment relaxation for two problems, the separation and covering problem with semi-algebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases and (b) after performing some small perturbation of the original problem, convergence can be achieved with r=d. We further provide a practical iterative algorithm that is computationally tractable for large datasets and present encouraging computational results.

Recommendations

• An introduction to polynomial and semi-algebraic optimization
• Linear optimization with cones of moments and nonnegative polynomials
• Solving polynomial least squares problems via semidefinite programming relaxations
• Sums of squares, moment matrices and optimization over polynomials
• Moments, positive polynomials and their applications

Cites work

• scientific article; zbMATH DE number 3694044 (Why is no real title available?)
• scientific article; zbMATH DE number 1489799 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• An Algorithm for Separating Patterns by Ellipsoids
• Computation of Minimum-Volume Covering Ellipsoids
• Determinant Maximization with Linear Matrix Inequality Constraints
• Global optimization with polynomials and the problem of moments
• Minimum-volume ellipsoids. Theory and algorithms
• On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
• Pattern separation by convex programming
• Revisiting two theorems of Curto and Fialkow on moment matrices
• Solving semidefinite-quadratic-linear programs using SDPT3
• The truncated complex $K$-moment problem
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Describes a project that uses

Uses Software

• Mosek
• YALMIP
• Gurobi
• SDPT3
• SeDuMi

This page was built for publication: Optimal data fitting: a moment approach

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