A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
Résumé
We provide a sparse version of the bounded degree SOS (BSOS) hierarchy for polynomial optimization problems. The presented version permits to handle 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.
Origine : Fichiers produits par l'(les) auteur(s)