Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity

  • We provide a sparse version of the bounded degree SOS hierarchy BSOS (Lasserre et al. in EURO J Comp Optim:87–117, 2017) for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem.Moreover, for the class of SOS-convex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Tillmann Weisser, Jean B. Lasserre, Kim-Chuan Toh
DOI:https://doi.org/10.1007/s12532-017-0121-6
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2017
Tag:Software; Theoretical Computer Science
Volume:10
Issue:1
Page Number:32
First Page:1
Last Page:32
Mathematical Programming Computation :MPC 2018 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.