Optimal data fitting: a moment approach

Dimitris Bertsimas(dbertsimmit.edu)
Xuan Vinh Doan(vanxuanmit.edu)
Jean Lasserre(lasserrelaas.fr)

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) there exist probability measures such that the moment relaxation is equivalent to the original problem with r = d. We further provide a practical iterative algorithm that is computationally tractable for large datasets and present encouraging computational results.

Keywords: moment relaxation, data fitting, separation problem, covering problem

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: January 2007

Download: [PDF]

Entry Submitted: 02/19/2007
Entry Accepted: 02/19/2007
Entry Last Modified: 02/19/2007

Modify/Update this entry