  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 DSOS and 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 tradeoffs 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 of the paper introduces an accompanying MATLAB package for DSOS and
SDSOS optimization.
