证明了计算非凸函数临界点近似解在一般情况下是不可行的。
On Approximate Computation of Critical Points
- 通过归约证明：多项式时间算法求解低次多项式临界点近似解，将导致P=NP。
- 即使允许输出任意点（无临界点时），仍无法在多项式时间内保证梯度范数≤2^n。
- 在有唯一临界点、函数下有界等理想条件下，逼近仍困难，挑战传统认知。
我们证明，对简单的非凸函数类，计算甚至非常粗糙的临界点近似值也是不可行的。具体而言，若存在一个多项式时间算法，能接收任意n个变量、常数次数（低至3次）的多项式输入，并在该多项式存在临界点时输出一个梯度欧氏范数不超过2^n的点，则P=NP。该算法在无临界点时可返回任意点。我们还针对附加结构假设（如临界点存在且唯一、函数下有界）下的近似临界点计算，建立了难解性结果，逼近精度以距离临界点的距离衡量。总体上，这些结果与非凸优化中‘近似临界点可高效计算’的普遍信念相悖。
原文摘要 · Abstract (English)
We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in $n$ variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm at most $2^n$ whenever the polynomial has a critical point, then P=NP. The algorithm is permitted to return an arbitrary point when no critical point exists. We also prove hardness results for approximate computation of critical points under additional structural assumptions, including settings in which existence and uniqueness of a critical point are guaranteed, the function is lower bounded, and approximation is measured in terms of distance to a critical point. Overall, our results stand in contrast to the commonly-held belief that, in nonconvex optimization, approximate computation of critical points is a tractable task.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。