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.
Keywords for this software
References in zbMATH (referenced in 9 articles , 1 standard article )
Showing results 1 to 9 of 9.
- Marandi, Ahmadreza; de Klerk, Etienne; Dahl, Joachim: Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy (2020)
- Campos, Juan S.; Misener, Ruth; Parpas, Panos: A multilevel analysis of the Lasserre hierarchy (2019)
- Chuong, T. D.; Jeyakumar, V.; Li, G.: A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs (2019)
- Dickinson, Peter J. C.; Povh, Janez: A new approximation hierarchy for polynomial conic optimization (2019)
- Papp, Dávid; Yildiz, Sercan: Sum-of-squares optimization without semidefinite programming (2019)
- Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey: Misspecified nonconvex statistical optimization for sparse phase retrieval (2019)
- Campos, Juan S.; Parpas, Panos: A multigrid approach to SDP relaxations of sparse polynomial optimization problems (2018)
- Josz, Cédric; Molzahn, Daniel K.: Lasserre hierarchy for large scale polynomial optimization in real and complex variables (2018)
- Weisser, Tillmann; Lasserre, Jean B.; Toh, Kim-Chuan: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity (2018)