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 10 articles , 1 standard article )

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

  1. Chesi, Graziano; Shen, Tiantian: Convergent upper bounds of peak response of LTI and polytopic LTV systems through LMIs (2020)
  2. 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)
  3. Campos, Juan S.; Misener, Ruth; Parpas, Panos: A multilevel analysis of the Lasserre hierarchy (2019)
  4. 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)
  5. Dickinson, Peter J. C.; Povh, Janez: A new approximation hierarchy for polynomial conic optimization (2019)
  6. Papp, Dávid; Yildiz, Sercan: Sum-of-squares optimization without semidefinite programming (2019)
  7. Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey: Misspecified nonconvex statistical optimization for sparse phase retrieval (2019)
  8. Campos, Juan S.; Parpas, Panos: A multigrid approach to SDP relaxations of sparse polynomial optimization problems (2018)
  9. Josz, Cédric; Molzahn, Daniel K.: Lasserre hierarchy for large scale polynomial optimization in real and complex variables (2018)
  10. Weisser, Tillmann; Lasserre, Jean B.; Toh, Kim-Chuan: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity (2018)