论文标题
关于在polytope上找到二次函数的局部最小化的复杂性
On the complexity of finding a local minimizer of a quadratic function over a polytope
论文作者
论文摘要
我们表明，除非p = np，否则不可能有多项式时间算法在欧几里得距离内找到一个点$ c^n $（对于任何常数$ c \ ge 0 $）的本地最小化器，具有$ n $ n $变量的二次功能。这个结果（即使有$ c = 0 $）回答了1992年出现在复杂性理论中的七个开放性问题的列表中，以进行数值优化。我们的证明技术还意味着，确定二次函数是否在（无限）的多面体上具有局部最小化的问题，并且决定是否具有四分之一的多项式具有局部最小化器的问题。
We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over an (unbounded) polyhedron, and that of deciding if a quartic polynomial has a local minimizer are NP-hard.
