论文标题
本地最小值和相关概念的复杂性方面
Complexity aspects of local minima and related notions
论文作者
论文摘要
我们考虑（i）临界点，（ii）二阶点，（iii）局部最小值和（iv）多元多项式的严格局部最小值的概念。对于每种类型的点，作为多项式程度的函数，我们研究决定（1）如果给定点为该类型的复杂性（1），以及（2）多项式具有该类型的点。我们的结果表征了这两个问题的复杂性，以前的文献使所有程度均打开。我们的主要贡献表明，这些问题中的许多问题对于立方多项式来说是可以解决的。特别是，我们提出了有效检查的有效和足够的条件，可以使立方多项式的局部最小化。我们还表明，可以通过在变量数量中求解线性的半尺度程序来有效地找到局部最低立方多项式的最小值。相比之下，我们表明，确定立方多项式是否具有关键点是很强烈的NP-HARD。我们还证明，任何立方多项式的一组二阶点都是谱系，相反，任何谱图都是立方多项式的二阶点的投影。在我们的最后一部分中，我们简要介绍了在三阶牛顿方法的设计中找到局部多项式的局部最小值的潜在应用。
We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if a polynomial has a point of that type. Our results characterize the complexity of these two questions for all degrees left open by prior literature. Our main contributions reveal that many of these questions turn out to be tractable for cubic polynomials. In particular, we present an efficiently-checkable necessary and sufficient condition for local minimality of a point for a cubic polynomial. We also show that a local minimum of a cubic polynomial can be efficiently found by solving semidefinite programs of size linear in the number of variables. By contrast, we show that it is strongly NP-hard to decide if a cubic polynomial has a critical point. We also prove that the set of second-order points of any cubic polynomial is a spectrahedron, and conversely that any spectrahedron is the projection of the set of second-order points of a cubic polynomial. In our final section, we briefly present a potential application of finding local minima of cubic polynomials to the design of a third-order Newton method.
