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

DSOS 和 SDSOS 优化：比完全平方和和半定性优化更易处理的替代方法

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

Motivated by applications in robotics and computer vision, we study problems
related to spatial reasoning of a 3D environment using sublevel sets of
polynomials. These include: tightly containing a cloud of points (e.g.,
representing an obstacle) with convex or nearly-convex basic semialgebraic
sets, computation of Euclidean distances between two such sets, separation of
two convex basic semalgebraic sets that overlap, and tight containment of the
union of several basic semialgebraic sets with a single convex one. We use
algebraic techniques from sum of squares optimization that reduce all these
tasks to semidefinite programs of small size and present numerical experiments
in realistic scenarios.

运用代数学方法，本文研究了利用函数多项式下水平集进行三维空间推理的问题，包括两个基本半代数凸集之间互相包含的相关计算、相交的两个半代数凸集之间的分离、多个半代数集合与一个凸集的紧凑包含等，并且我们将这些任务的求解转化为小型半定规划并进行了实验验证。