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.

本文介绍了 DSOS 和 SDSOS 最优化算法作为线性规划和二阶锥规划的替代方法，以允许一个在计算时间与解决方案质量之间进行权衡的选择，并且用多个应用领域的数值实验表明，我们可以在目前传统的平方和算法难以实现的规模上处理问题。