Fast ADMM for sum-of-squares programs using partial orthogonality

Zheng Y, Fantuzzi G, Papachristodoulou A (2019)

Publication Type: Journal article

Publication year: 2019

Journal

IEEETransactions on Automatic Control Institute of Electrical and Electronics Engineers (IEEE)

Book Volume: 64

Pages Range: 3869-3876

Article Number: 8571259

Journal Issue: 9

DOI: 10.1109/TAC.2018.2886170

Abstract

When sum-of-squares (SOS) programs are recast as semidefinite programs (SDPs) using the standard monomial basis, the constraint matrices in the SDP possess a structural property that we call partial orthogonality. In this paper, we leverage partial orthogonality to develop a fast first-order method, based on the alternating direction method of multipliers (ADMM), for the solution of the homogeneous self-dual embedding of SDPs describing SOS programs. Precisely, we show how a “diagonal plus low rank” structure implied by partial orthogonality can be exploited to project efficiently the iterates of a recent ADMM algorithm for generic conic programs onto the set defined by the affine constraints of the SDP. The resulting algorithm, implemented as a new package in the solver CDCS, is tested on a range of large-scale SOS programs arising from constrained polynomial optimization problems and from Lyapunov stability analysis of polynomial dynamical systems. These numerical experiments demonstrate the effectiveness of our approach compared to common state-of-the-art solvers.

Authors with CRIS profile

Giovanni Fantuzzi

Involved external institutions

University of Oxford GB United Kingdom (GB) Imperial College London / The Imperial College of Science, Technology and Medicine GB United Kingdom (GB)

How to cite

APA:

Zheng, Y., Fantuzzi, G., & Papachristodoulou, A. (2019). Fast ADMM for sum-of-squares programs using partial orthogonality. IEEETransactions on Automatic Control, 64(9), 3869-3876. https://dx.doi.org/10.1109/TAC.2018.2886170

MLA:

Zheng, Yang, Giovanni Fantuzzi, and Antonis Papachristodoulou. "Fast ADMM for sum-of-squares programs using partial orthogonality." IEEETransactions on Automatic Control 64.9 (2019): 3869-3876.

BibTeX: Download