Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/TAC.2018.2886170 | IEEE Transactions on Automatic Control |
Keywords | Field | DocType |
Two dimensional displays,Optimization,Convex functions,Standards,Lyapunov methods,Heuristic algorithms,Programming | Diagonal,Mathematical optimization,Polynomial,Matrix (mathematics),Lyapunov stability,Orthogonality,Monomial basis,Solver,Explained sum of squares,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 9 | 0018-9286 |
Citations | PageRank | References |
2 | 0.37 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Zheng | 1 | 267 | 18.67 |
| Giovanni Fantuzzi | 2 | 10 | 1.86 |
| Antonis Papachristodoulou | 3 | 990 | 90.01 |