论文标题
SONC优化和确切的非负证书通过二阶锥度编程
SONC Optimization and Exact Nonnegativity Certificates via Second-Order Cone Programming
论文作者
论文摘要
二阶锥（SOC）是一类简单的凸锥，并且对它们进行优化可以比半芬矿编程更有效地完成。从理论和实践中，研究哪个凸锥在使用SOC的代表方面都很有趣，因为它们具有强大的表现能力。在本文中，我们建设性地证明了非负电路总和（SONC）承认SOC代表。基于此，我们通过SOC编程给出了一种新的算法，用于无限制的多项式优化。我们还提供了一个混合数字符号方案，该方案将数值程序与圆形预测算法结合在一起，以获得确切的非负性证书。数值实验证明了我们的算法对于具有相当大的变量程度和数量的多项式效率。
The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables.
