TY - JOUR
T1 - DSOS and SDSOS optimization
T2 - More tractable alternatives to sum of squares and semidefinite optimization
AU - Ahmadi, Amir Ali
AU - Majumdar, Anirudha
N1 - Funding Information:
\ast Received by the editors May 23, 2018; accepted for publication (in revised form) September 25, 2018; published electronically April 16, 2019. An extended abstract of this work appears in [4]. http://www.siam.org/journals/siaga/3-2/M118935.html Funding: The first author was partially supported by the DARPA Young Faculty Award, the Sloan Fellowship, the NSF CAREER Award, the AFOSR Young Investigator Program Award, and the Google Research Award. \dagger Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08544 (a a a@princeton.edu, http://aaa.princeton.edu/). \ddagger Department of Mechanical and Aerospace Engineering, Princeton University, Princeton, NJ 08544 (ani.majumdar@princeton.edu, https://irom-lab.princeton.edu/majumdar/).
Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
PY - 2019
Y1 - 2019
N2 - In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs, however, has limited the scale of problems to which it can be applied. In this paper, we introduce diagonally dominant sum of squares (DSOS) and scaled diagonally dominant sum of squares (SDSOS) optimization as linear programming and second-order cone programming-based alternatives to sum of squares optimization that allow one to trade off computation time with solution quality. These are optimization problems over certain subsets of sum of squares polynomials (or equivalently subsets of positive semidefinite matrices), which can be of interest in general applications of semidefinite programming where scalability is a limitation. We show that some basic theorems from SOS optimization which rely on results from real algebraic geometry are still valid for DSOS and SDSOS optimization. Furthermore, we show with numerical experiments from diverse application areas-polynomial optimization, statistics and machine learning, derivative pricing, and control theory-that with reasonable trade-offs in accuracy, we can handle problems at scales that are currently significantly beyond the reach of traditional sum of squares approaches. Finally, we provide a review of recent techniques that bridge the gap between our DSOS/SDSOS approach and the SOS approach at the expense of additional running time. The supplementary material to the paper introduces an accompanying MATLAB package for DSOS and SDSOS optimization.
AB - In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs, however, has limited the scale of problems to which it can be applied. In this paper, we introduce diagonally dominant sum of squares (DSOS) and scaled diagonally dominant sum of squares (SDSOS) optimization as linear programming and second-order cone programming-based alternatives to sum of squares optimization that allow one to trade off computation time with solution quality. These are optimization problems over certain subsets of sum of squares polynomials (or equivalently subsets of positive semidefinite matrices), which can be of interest in general applications of semidefinite programming where scalability is a limitation. We show that some basic theorems from SOS optimization which rely on results from real algebraic geometry are still valid for DSOS and SDSOS optimization. Furthermore, we show with numerical experiments from diverse application areas-polynomial optimization, statistics and machine learning, derivative pricing, and control theory-that with reasonable trade-offs in accuracy, we can handle problems at scales that are currently significantly beyond the reach of traditional sum of squares approaches. Finally, we provide a review of recent techniques that bridge the gap between our DSOS/SDSOS approach and the SOS approach at the expense of additional running time. The supplementary material to the paper introduces an accompanying MATLAB package for DSOS and SDSOS optimization.
KW - Linear programming
KW - Nonnegative polynomials
KW - Polynomial optimization
KW - Second-order cone programming
KW - Semidefinite programming
KW - Sum of squares optimization
UR - http://www.scopus.com/inward/record.url?scp=85090635387&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090635387&partnerID=8YFLogxK
U2 - 10.1137/18M118935X
DO - 10.1137/18M118935X
M3 - Article
AN - SCOPUS:85090635387
SN - 2470-6566
VL - 3
SP - 193
EP - 230
JO - SIAM Journal on Applied Algebra and Geometry
JF - SIAM Journal on Applied Algebra and Geometry
IS - 2
ER -