Block Factor-Width-Two Matrices and Their Applications to Semidefinite and Sum-of-Squares Optimization
From MaRDI portal
Publication:6092999
DOI10.1109/TAC.2022.3151187arXiv1909.11076OpenAlexW2975680413WikidataQ120717316 ScholiaQ120717316MaRDI QIDQ6092999FDOQ6092999
Authors: Yang Zheng, Aivar Sootla, Antonis Papachristodoulou 
Publication date: 6 September 2023
Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1909.11076
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)
