Block Factor-Width-Two Matrices and Their Applications to Semidefinite and Sum-of-Squares Optimization

Semidefinite and sum-of-squares (SOS) optimization are fundamental computational tools in many areas, including linear and nonlinear systems theory. However, the scale of problems that can be addressed reliably and efficiently is still limited. In this article, we introduce a new notion of block factor-width-two matrices and build a new hierarchy of inner and outer approximations of the cone of positive semidefinite (PSD) matrices. This notion is a block extension of the standard factor-width-two matrices, and allows for an improved inner-approximation of the PSD cone. In the context of SOS optimization, this leads to a block extension of the scaled diagonally dominant sum-of-squares (SDSOS) polynomials. By varying a matrix partition, the notion of block factor-width-two matrices can balance a tradeoff between the computation scalability and solution quality for solving semidefinite and SOS optimization problems. Numerical experiments on a range of large-scale instances confirm our theoretical findings.

I. Introduction

Semidefinite programs (SDPs) are a class of convex problems over the cone of positive semidefinite (PSD) matrices [2], which is one of the major computational tools in linear control theory. Many analysis and synthesis problems in linear systems can be addressed via solving certain SDPs; see [3] for an overview. The later development of sum-of-squares (SOS) optimization [4], [5] extends the applications of SDPs to nonlinear problems involving polynomials, and, thus, allows addressing many nonlinear control problems systematically, e.g., certifying asymptotic stability of equilibrium points of nonlinear systems [6], [7], approximating region of attraction [8]–[10], and providing bounds on infinite-time averages [11].