DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

In recent years, optimization theory has been greatly impacted by the advent\nof sum of squares (SOS) optimization. The reliance of this technique on\nlarge-scale semidefinite programs however, has limited the scale of problems to\nwhich it can be applied. In this paper, we introduce DSOS and SDSOS\noptimization as linear programming and second-order cone programming-based\nalternatives to sum of squares optimization that allow one to trade off\ncomputation time with solution quality. These are optimization problems over\ncertain subsets of sum of squares polynomials (or equivalently subsets of\npositive semidefinite matrices), which can be of interest in general\napplications of semidefinite programming where scalability is a limitation. We\nshow that some basic theorems from SOS optimization which rely on results from\nreal algebraic geometry are still valid for DSOS and SDSOS optimization.\nFurthermore, we show with numerical experiments from diverse application\nareas---polynomial optimization, statistics and machine learning, derivative\npricing, and control theory---that with reasonable tradeoffs in accuracy, we\ncan handle problems at scales that are currently significantly beyond the reach\nof traditional sum of squares approaches. Finally, we provide a review of\nrecent techniques that bridge the gap between our DSOS/SDSOS approach and the\nSOS approach at the expense of additional running time. The Supplementary\nMaterial of the paper introduces an accompanying MATLAB package for DSOS and\nSDSOS optimization.\n