Exploiting Sparsity in the Coefficient Matching Conditions in Sum-of-Squares Programming Using ADMM
File(s)1703.01969v2.pdf (174.69 KB)
Accepted version
Author(s)
Zheng, Yang
Fantuzzi, Giovanni
Papachristodoulou, Antonis
Type
Journal Article
Abstract
This letter introduces an efficient first-order method based on the alternating direction method of multipliers (ADMM) to solve semidefinite programs arising from sum-of-squares (SOS) programming. We exploit the sparsity of the coefficient matching conditions when SOS programs are formulated in the usual monomial basis to reduce the computational cost of the ADMM algorithm. Each iteration of our algorithm requires one projection onto the positive semidefinite cone and the solution of multiple quadratic programs with closed-form solutions free of any matrix inversion. Our techniques are implemented in the open-source MATLAB solver SOSADMM. Numerical experiments on SOS problems arising from unconstrained polynomial minimization and from Lyapunov stability analysis for polynomial systems show speed-ups compared to the interior-point solver SeDuMi, and the first-order solver CDCS.
Date Issued
2017-07
Date Acceptance
2017-05-18
Citation
IEEE Control Systems Letters, 2017, 1 (1), pp.80-85
ISSN
2475-1456
Publisher
Institute of Electrical and Electronics Engineers
Start Page
80
End Page
85
Journal / Book Title
IEEE Control Systems Letters
Volume
1
Issue
1
Copyright Statement
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects
math.OC
Publication Status
Published
Date Publish Online
2017-05-23