Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
File(s)
Published version
Author(s)
Zheng, Yang
Fantuzzi, Giovanni
Papachristodoulou, Antonis
Type
Journal Article
Abstract
Chordal and factor-width decomposition methods for semidefinite programming and polynomial optimization have recently enabled the analysis and control of large-scale linear systems and medium-scale nonlinear systems. Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. Factor-width decompositions, instead, relax or strengthen SDPs with dense semidefinite matrices into more tractable problems, trading feasibility or optimality for lower computational complexity. This article reviews recent advances in large-scale semidefinite and polynomial optimization enabled by these two types of decomposition, highlighting connections and differences between them. We also demonstrate that chordal and factor-width decompositions allow for significant computational savings on a range of classical problems from control theory, and on more recent problems from machine learning. Finally, we outline possible directions for future research that have the potential to facilitate the efficient optimization-based study of increasingly complex large-scale dynamical systems.
Date Issued
2021-10-19
Date Acceptance
2021-09-03
Citation
Annual Reviews in Control, 2021, 52, pp.243-279
ISSN
1367-5788
Publisher
Elsevier BV
Start Page
243
End Page
279
Journal / Book Title
Annual Reviews in Control
Volume
52
Copyright Statement
© 2021 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license.
License URL
Identifier
https://www.sciencedirect.com/science/article/pii/S1367578821000717?via%3Dihub
Subjects
math.OC
math.OC
cs.SY
eess.SY
math.DS
0906 Electrical and Electronic Engineering
0913 Mechanical Engineering
Industrial Engineering & Automation
Publication Status
Published online
Date Publish Online
2021-10-19