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

DOI10.1109/TAC.2022.3151187MaRDI QIDQ6092999zbMATH OpenOpenAlexWikidataFDO

Authors Yang Zheng, Aivar Sootla, Antonis Papachristodoulou

Publication date 6 September 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.11076

zbMATH Keywords

large-scale systemsmatrix decompositionsemidefinite optimizationsum-of-squares (SOS) polynomials

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: 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 paper, 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 trade-off 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.

Cited in

(3)

• An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
• Fixed-time prescribed performance control of affine parameter-varying systems with an application in aero engines
• A predictor-corrector algorithm for semidefinite programming that uses the factor width cone

This page was built for publication: Block Factor-Width-Two Matrices and Their Applications to Semidefinite and Sum-of-Squares Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6092999)