论文标题
多项式优化的复杂性，精确性和合理性
Complexity, Exactness, and Rationality in Polynomial Optimization
论文作者
论文摘要
我们专注于理性解决方案或几乎可行的理性解决方案，这些解决方案是多项式优化问题的可行性证书。我们表明，在某些可分离性条件下，某些立方多项式约束的集合允许合理解决方案。但是，在其他情况下，我们表明NP难以检测是否存在理性解决方案或是否存在任何合理规模。我们将此想法扩展到各种设置，包括几乎可行的，但超级最佳的解决方案以及检测无限制函数的理性射线。最后，我们表明，在固定维度中，由多项式不等式定义的集合的可行性问题是在NP中通过提供简单的证书来验证可行性。我们以几个相关的非理性示例和QCQP和SECP中的规模问题进行编码的结论。
We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. We extend this idea to various settings including near feasible, but super optimal solutions and detecting rational rays on which a cubic function is unbounded. Lastly, we show that in fixed dimension, the feasibility problem over a set defined by polynomial inequalities is in NP by providing a simple certificate to verify feasibility. We conclude with several related examples of irrationality and encoding size issues in QCQPs and SOCPs.
