2003/02/09 by Alexandre d'Aspremont, Alexandre d’Aspremont, d'Aspremont, Alexandre
Computer Science · Mathematics · #90C10 #90C22 #90C27 #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #math.OC #msc:90C10 #msc:90C22 #msc:90C27
paper · pdf · doi:10.48550/arxiv.math/0302092
No figures, this version removes typos, improves notation and corrects two minor errors in section 3 and 4
openalex publication_date 2003/02/09 · arxiv created 2003/02/27 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Using techniques developed in [Lasserre02], we show that some minimum cardinality problems subject to linear inequalities can be represented as finite sequences of semidefinite programs. In particular, we provide a semidefinite representation of the minimum rank problem on positive semidefinite matrices. We also use this technique to cast the problem of finding convex lower bounds on the objective as a semidefinite program.