计算二次规划KKT解的复杂性

《Journal of the ACM》：The Complexity of Computing KKT Solutions of Quadratic Programs

本文证明，求解带盒式约束的二次规划问题的KKT点属于CLS类（连续局部搜索类），并通过构造线性算术电路并分析扰动，证明该问题是CLS完全的。核心方法包括将KKT点计算问题转化为线性算术电路的扰动分析，利用分层构造和平均技巧处理多变量约束，最终通过归约证明其复杂性。

　　本研究探讨了非凸二次规划问题中寻找KKT点的计算复杂性。二次规划（Quadratic Programming, QP）是一种优化问题，目标是找到一组实数变量的值，使得二次函数在满足线性约束的条件下取得最小值。这类问题在科学、工程和经济等多个领域都有广泛的应用，而且已经被证明是NP难的问题。然而，本研究进一步指出，即使我们仅寻找一个KKT点，而不是全局最优解，该问题仍然具有较高的计算复杂性。

KKT点是指在梯度下降法下局部最优的解，这可能是一个梯度为零的点，或者在边界约束下进一步优化受到阻碍的点。KKT点的特性在于它们具有可验证的证书，即梯度和约束条件。因此，搜索KKT点的问题属于TFNP类，这类问题保证了解的存在性，且可以被有效地验证。然而，研究者发现，即使在某些情况下，KKT点的计算仍难以高效完成，尤其是在涉及箱约束（box constraints）的QPs中。

在已有的研究中，针对全局最优解的计算复杂性已有许多成果，包括一些证明其为NP难的文献。同时，对于局部最优解的计算复杂性也有相关研究，其中一些问题被证明为NP难。此外，还有研究指出，对于某些特殊的QP形式，比如平方自由二次形式（diagonal entries为零且没有线性项），找到近似解也是NP难的。然而，这些结果大多针对的是具有特定约束条件的QP问题。

本研究的核心结论是，计算QP的KKT点问题属于CLS复杂度类，并且是CLS-完全的。CLS（Continuous Local Search）是一个用于研究连续局部搜索问题的复杂度类，其定义是PPAD和PLS的交集。PPAD（Polynomial Parity Argument on Directed graphs）和PLS（Polynomial Time Local Search）是用于研究计算问题中解的存在性和局部搜索复杂性的两个复杂度类。CLS类的引入旨在更好地理解某些看似难以解决的搜索问题，而KKT点的计算正好属于这类问题。

研究者在证明过程中，首先通过构造一个二次多项式来模拟一个线性算术电路（linear arithmetic circuit）的KKT点。为了实现这一点，他们使用了特定的技巧，如“指导变量”（guide variables）和“平均技巧”（averaging trick），这些技巧能够有效地模拟电路中的操作，并且在存在扰动的情况下也能保持一定的鲁棒性。然而，由于KKT点的计算涉及到梯度，因此在某些情况下，扰动可能导致梯度计算的不准确，进而影响KKT点的正确性。

为了克服这一问题，研究者引入了一种称为“mesa构造”的方法，这种方法能够确保即使在存在扰动的情况下，也不会引入新的KKT点。具体来说，他们构建了一个由多个线性函数组成的函数，这些函数的最小值构成了一个类似于平顶山的形状，从而确保在扰动下梯度的变化不会影响最终的KKT点。通过这种方法，他们能够证明计算QP的KKT点问题属于CLS类，并且是CLS-完全的。

此外，研究者还考虑了不同类型的QP问题，包括具有不同约束条件的QP，如单位球（unit sphere）或交集球（intersection of spheres）等。他们指出，这些特殊形式的QP在计算KKT点时可能具有不同的复杂性，但本研究的主要结果是针对具有箱约束的QP的。

研究还涉及了一些技术性问题，如如何在有限的扰动下保持KKT点的正确性，以及如何通过构造特定的函数来模拟电路中的操作。他们提出了一种构造方法，通过引入辅助变量和特定的扰动处理，使得即使存在扰动，也不会对KKT点的计算产生显著影响。这种方法不仅适用于当前的研究，还可能为其他类似问题提供思路。

总之，本研究的结果表明，计算QP的KKT点问题具有较高的复杂性，即使我们不追求全局最优解，该问题仍然属于CLS类，并且是CLS-完全的。这意味着，除非PPAD和PLS中的一个包含另一个，否则这类问题无法在多项式时间内求解。这一结论不仅对QP问题本身具有重要意义，也为其他涉及KKT点的优化问题提供了理论支持。