Sparse-BSOS

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.


References in zbMATH (referenced in 14 articles , 1 standard article )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Chen, Tong; Lasserre, Jean-Bernard; Magron, Victor; Pauwels, Edouard: A sublevel moment-SOS hierarchy for polynomial optimization (2022)
  2. Katthän, Lukas; Naumann, Helen; Theobald, Thorsten: A unified framework of SAGE and SONC polynomials and its duality theory (2021)
  3. Lakshmi, Mayur V.; Fantuzzi, Giovanni; Chernyshenko, Sergei I.; Lasagna, Davide: Finding unstable periodic orbits: a hybrid approach with polynomial optimization (2021)
  4. Wang, Jie; Magron, Victor; Lasserre, Jean-Bernard: TSSOS: a moment-SOS hierarchy that exploits term sparsity (2021)
  5. Chesi, Graziano; Shen, Tiantian: Convergent upper bounds of peak response of LTI and polytopic LTV systems through LMIs (2020)
  6. 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)
  7. Campos, Juan S.; Misener, Ruth; Parpas, Panos: A multilevel analysis of the Lasserre hierarchy (2019)
  8. 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)
  9. Dickinson, Peter J. C.; Povh, Janez: A new approximation hierarchy for polynomial conic optimization (2019)
  10. Papp, Dávid; Yildiz, Sercan: Sum-of-squares optimization without semidefinite programming (2019)
  11. Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey: Misspecified nonconvex statistical optimization for sparse phase retrieval (2019)
  12. Campos, Juan S.; Parpas, Panos: A multigrid approach to SDP relaxations of sparse polynomial optimization problems (2018)
  13. Josz, Cédric; Molzahn, Daniel K.: Lasserre hierarchy for large scale polynomial optimization in real and complex variables (2018)
  14. Weisser, Tillmann; Lasserre, Jean B.; Toh, Kim-Chuan: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity (2018)