标题： 半正规划的平方和逼近计算复杂度 显示英文标题

标题： Computational complexity of sum-of-squares bounds for copositive programs

摘要： 近年来，由于半正规划在离散和连续优化问题建模中的能力，它受到了广泛关注。文献中提出了几种基于半定规划（SDP）的半正规划松弛方法，旨在提供可处理的界值。然而，虽然这些基于SDP的松弛方法适用于椭球算法和内点法，但它们是否能在多项式时间内求解（甚至近似求解）并不明显。 本文考虑了Parrilo（2000）、de Klerk & Pasechnik（2002）以及Peña、Vera与Zuluaga（2006）引入的半正规划松弛的平方和（SOS）层次结构，这些层次结构可以表示为SDP。我们建立了足以保证这些松弛方法在固定精度下以多项式时间可计算的充分条件。这些条件由标准二次规划及其倒数所表示的半正规划满足。 作为应用，我们证明了图的（加权）稳定性数的SOS界可以有效计算。此外，我们提供了某些半正规划的病态例子（这些例子不满足充分条件），其SOS松弛仅允许双指数规模的可行解。 显示英文摘要

摘要： In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik (2002) and Pe\~na, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently. Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size.