Mathematical Programming Computation, Volume 10, Issue 1, March 2018

Font Size:  Small  Medium  Large

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

Tillmann Weisser, Jean B. Lasserre, Kim-Chuan Toh


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.

Full Text: PDF

mpc footer
© MPS 2008-2018