Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity |
| |
Authors: | Tillmann Weisser Jean B. Lasserre Kim-Chuan Toh |
| |
Affiliation: | 1.LAAS-CNRS, University of Toulouse, LAAS,Toulouse cedex 4,France;2.LAAS-CNRS and Institute of Mathematics,University of Toulouse, LAAS,Toulouse cedex 4,France;3.Department of Mathematics,National University of Singapore,Singapore,Singapore |
| |
Abstract: | 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: | |
本文献已被 SpringerLink 等数据库收录! |
|