We provide a sparse version of the bounded degree SOS hierarchy BSOS [7] 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.

本文提出了一种稀疏版本的有界次数 SOS 层次结构 BSOS，适用于多项式优化问题，特别针对结构稀疏模式问题。当稀疏模式满足运行交替性质时，这种具有固定大小的半定规划的稀疏 - BSOS 层次结构会收敛于原问题的全局最优解。此外，对于 SOS - 凸问题类，在层次结构的第一步就会出现有限收敛，就像在密集版本中一样。

Sparse-BSOS：具有稀疏性的大规模多项式优化有界次 SOS 层次结构

Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial  optimization with sparsity

Lasserre's hierarchy is a sequence of semidefinite relaxations for solving
polynomial optimization problems globally. This paper studies the relationship
between optimality conditions in nonlinear programming theory and finite
convergence of Lasserre's hierarchy. Our main results are: i) Lasserre's
hierarchy has finite convergence when the constraint qualification, strict
complementarity and second order sufficiency conditions hold at every global
minimizer, under the standard archimedean assumption; the proof uses a result
of Marshall on boundary hessian conditions. ii) these optimality conditions are
all satisfied at every local minimizer if a finite set of polynomials, which
are in the coefficients of input polynomials, do not vanish at the input data
(i.e., they hold in a Zariski open set). This implies that Lasserre's hierarchy
has finite convergence generically.

研究 Lasserre 层次与非线性规划理论中最优性条件的关系，并证明在一定条件下 Lasserre 层次有有限收敛性，这些最优性条件在局部极小值点成立且在输入数据中一组有限的多项式不为零时，Lasserre 层次具有一般的有限收敛性。