跳转至

八股⚓︎

约 2972 个字 预计阅读时间 10 分钟 总阅读量 次

P/NP/NP-complete/NP-hard

计算复杂度⚓︎

P 问题 (Polynomial Time)

P 问题 是指那些能够在一个“多项式”的时间内找到确切解的问题。

  • 通俗解释：“Polynomial”就是“多项式”。如果一个问题的求解时间（最坏情况下）随着问题规模 \(n\) 的增长，不超过 \(n\) 的某个常数次幂（例如 \(O(n)\), \(O(n^2)\), \(O(n^3)\)），那么它就是P问题。我们称这类问题是 “计算上可行的”（Computationally Tractable）。

  • 技术定义：一个判定性问题（答案是“是”或“否”）如果能被一个确定性图灵机在多项式时间内解决，那么它就属于P类问题。

  • 其他例子：

    • 排序问题
    • 最大公约数计算
    • 最大流问题
    • 线性规划（在多项式时间内可解）

NP 问题 (Nondeterministic Polynomial Time)

NP 问题 是指那些能在多项式时间内快速验证一个解是否正确的问题。

Problems for which there exists an algorithm checking of a given structure in a polynomial time, thereby verifying the yes answer.

重要关系：所有 P 问题都是 NP 问题。因为如果一个问题能被快速解决，那它的解当然也能被快速验证（我们只要再算一遍就行了）。所以，P 是 NP 的一个子集。

P vs NP：这是计算机科学领域最著名的未解之谜。“是否 P = NP?”。如果能证明P=NP，意味着所有能被快速验证的问题，也都能被快速解决，这将颠覆整个世界。目前，学术界普遍认为 P ≠ NP。

1. NP-Complete 问题 (NPC)

NP-Complete 问题 是 NP 问题中最“难”的一类。

The first problem showed to be NP-complete is the satisfiability problem in which we ask if the set of boolean formulas has a truth assignment of boolean variables

  • 技术定义：一个问题要成为 NPC 问题，必须满足两个条件：

    1. 它本身是一个 NP 问题。（解的正确性可以被快速验证）
    2. 所有其他的 NP 问题都可以“规约”（Reduce）到它。

  • “规约”（Reduction）的理解：可以通俗地理解为“转化”。如果问题 A 能规约到问题 B（记为 \(A \le_p B\)），意思是我可以用一个解决问题 B 的“黑盒子”算法，来解决问题 A。这个转化的过程本身必须在多ar 时间内完成。这实质上说明了问题 B 至少和问题 A 一样难。

  • 其他例子：

    • 布尔可满足性问题（SAT，第一个被证明的NPC问题）
    • 背包问题（判定版本）
    • 哈密顿回路问题
    • 顶点覆盖问题

NP-Hard 问题 (NPH)

NP-Hard 问题 是指那些至少和任何 NP 问题一样难的问题。对于一个优化问题，如果它对应的决策问题是NP- Complete的，那么这个优化就是NP-complete的

An optimization problem is NP-hard if the corresponding decision problem is NP -complete

  • 通俗解释：NP-Hard 问题是“硬核”难题。它不一定本身是 NP 问题（即它的解不一定能被快速验证），但任何 NP 问题都可以规约到它。它定义了困难的下界。

  • 技术定义：一个问题是 NP-Hard，只需满足 NPC 定义的第二个条件：所有 NP 问题都可以规约到它。它不要求自己必须是 NP 问题。

  • NP-Hard 和 NP-Complete 的关系:

    • 如果一个 NP-Hard 问题同时也是一个 NP 问题，那它就是 NP-Complete 问题。
    • 可以说，NPC = NP ∩ NP-Hard。

  • 其他例子：

    • 停机问题（这是一个不可判定问题，比 NP 问题难得多，但它也是 NP-Hard）
    • 整数规划问题的优化版本

总结与可视化⚓︎

类别 通俗解释 关键特性 例子（运筹学）
P 能被快速解决 存在多项式时间解法 最短路、最大流、线性规划
NP 能被快速验证 解的正确性可在多项式时间验证 旅行商问题(判定版)、背包问题(判定版)
NP-Complete NP问题里最难的 1. 属于NP
2. 所有NP问题都能规约到它		 旅行商问题(判定版)、背包问题(判定版)
NP-Hard 至少和NPC一样难 所有NP问题都能规约到它（不要求属于NP） 旅行商问题(优化版)、整数规划(优化版)

仿射/凸/凸集⚓︎

好的，这几个概念是运筹优化和凸优化的基石，理解它们对于求解和分析优化问题至关重要。我们用直观的方式，从最基本的“零件”到最终的“构造”，一步步来梳理。

核心逻辑链条⚓︎

这三个概念是层层递进的： 1. 凸组合 (Convex Combination)：这是最基本的“操作”或“规则”。 2. 凸集 (Convex Set)：这是满足这个“规则”的“区域”或“形状”。 3. 凸包 (Convex Hull)：这是用这个“规则”对一堆点进行“加工”后得到的“最小封闭区域”。

1. 凸组合 (Convex Combination)⚓︎

给定一组点 \(x_1, x_2, \dots, x_k\)，这些点的一个凸组合是形如下式的一个新的点 \(x\): $ x = \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_k x_k $ 其中，系数 \(\theta_i\)（也叫权重）必须满足两个条件： 1. 非负性：$ \theta_i \ge 0 $ 对所有的 $ i=1, \dots, k $ 成立。 2. 和为一：$ \sum_{i=1}^k \theta_i = 1 $。

如果系数没有非负限制，那么这种组合就是仿射组合 (Affine)。

2. 凸集 (Convex Set)⚓︎

一个集合 \(C\) 是凸集，如果对于集合 \(C\) 中的任意两个点 \(x_1\) 和 \(x_2\)，连接它们的线段上的所有点都仍然在集合 \(C\) 中。

用数学语言说：对于任意 \(x_1, x_2 \in C\) 和任意 \(0 \le \theta \le 1\)，都有 \(\theta x_1 + (1-\theta) x_2 \in C\)。

一个凸集是“没有凹陷”或“没有洞”的形状。你可以想象在集合内部的任意两点之间拉一条橡皮筋，如果这条橡皮筋的任何部分都不会跑到集合外面去，那么这个集合就是凸集。

  • 交集性质：任意多个凸集的交集仍然是凸集。
  • 并集性质：两个凸集的并集不一定是凸集（比如两个不相交的圆形）。

3. 凸包 (Convex Hull)⚓︎

给定一个点集 \(S\)，其凸包 conv(S) 有两种等价的定义： 1. 组合定义：包含 \(S\) 中点位的所有凸组合的集合。 2. 几何定义：能够包含集合 \(S\) 的最小的凸集。

4. 凸函数 (Convex Function)**⚓︎

一个定义在凸集 \(S\) 上的函数 \(f\) 是凸函数，如果对于 \(S\) 中的任意两点 \(x_1, x_2\) 和任意 \(0 \le \theta \le 1\)，都满足以下不等式（这被称为琴生不等式 Jensen's Inequality）：

$ f(\theta x_1 + (1-\theta) x_2) \le \theta f(x_1) + (1-\theta) f(x_2) $

  • 左边 \(f(\theta x_1 + (1-\theta) x_2)\)：代表位于 \(x_1\) 和 \(x_2\) 之间线段上某一点 \(\tilde{x} = \theta x_1 + (1-\theta) x_2\) 处的函数值（在函数曲线上）。
  • 右边 \(\theta f(x_1) + (1-\theta) f(x_2)\)：代表点 \((x_1, f(x_1))\) 和点 \((x_2, f(x_2))\) 连接的弦上对应位置的值。

这个定义精确地描述了“弦在图像之上”的几何直观。几何直观是：函数图像上任意两点之间的弦（线段）都位于函数图像的上方（或恰好在图像上）。

凸函数的判定⚓︎

对于可微函数，我们有更简单的判断方法：

  • 一阶条件（如果函数一阶可导）： 函数 \(f\) 是凸函数的充要条件是，其图像始终位于其任何一条切线的上方。 数学表达式为：对于定义域内的任意 \(x, y\)，都有 $ f(y) \ge f(x) + \nabla f(x)^T (y-x) $ 其中 \(\nabla f(x)\) 是函数在点 \(x\) 的梯度。这个性质在很多优化算法的证明中非常关键。

  • 二阶条件（如果函数二阶可导）： 这是最常用的判断方法。

    • 一维情况：如果函数 \(f(x)\) 的二阶导数始终非负，即 \(f''(x) \ge 0\)，那么函数是凸函数。这表示函数的斜率是单调不减的。
    • 多维情况：如果函数 \(f(x)\) 的海森矩阵（Hessian Matrix）\(\nabla^2 f(x)\) 在定义域内始终是半正定（Positive Semidefinite）的，那么函数是凸函数。

严格凸 (Strictly Convex)：如果上述不等式中的 \(\le\) 可以被替换为 \(<\)（对于不同的两点），则称函数是严格凸的。例如 \(f(x)=x^2\)。严格凸函数的“碗底”是唯一的。

凹函数 (Concave Function)：如果 \(-f\) 是一个凸函数，那么 \(f\) 就是一个凹函数（例如 \(f(x) = \log(x)\)）。它的图形是“拱形”的，弦位于图像下方。

作用⚓︎

凸优化的基石，而凸优化是运筹优化中最高效、理论最完美的分支。

  1. 保证全局最优：

    • 核心定理：如果一个优化问题，它的可行域是一个凸集，并且它的目标函数是一个凸函数，那么==任何局部最优解都是全局最优解==。
    • 意义：这意味着我们不必担心算法会陷入一个较差的局部最优解。像梯度下降这类简单的算法就能找到问题的真正最优解。

  2. 正是因为“局部即全局”的特性，我们可以设计出==非常高效且理论上收敛的算法==。

    • 梯度下降法：对于一般的凸问题，简单的梯度下降法及其变种（如随机梯度下降、Adam等）就能保证收敛到全局最优解。
    • 内点法 (Interior-Point Methods)：对于特定结构的凸问题，如线性规划(LP)、二次规划(QP)、二阶锥规划(SOCP)和半定规划(SDP)，内点法被证明是多项式时间算法。这意味着即使问题规模变得非常大，求解时间也只是以多项式级别增长，而不是指数爆炸。

  3. 对偶理论：

    • 强对偶性：对于大多数凸优化问题，强对偶性（Strong Duality）成立。这意味着原问题（Primal Problem）的最优值与它的对偶问题（Dual Problem）的最优值相等。
    • 应用价值：
      • 提供最优性证明：如果你为原问题找到了一个可行解 \(x^*\)，并为对偶问题找到了一个可行解 \(y^*\)，且它们的目标函数值相等，那么你就证明了 \(x^*\) 是全局最优解。这提供了一个可靠的算法终止条件。
      • 问题分解：有时对偶问题比原问题结构更简单，或者更容易分解成多个小问题并行求解，这在分布式优化中非常有用。
      • 提供下界：对于困难的非凸问题（如整数规划），我们会先将其“松弛”为一个凸问题（如线性规划）。求解这个松弛问题的对偶，可以为原问题的最优解提供一个非常紧密的下界（Lower Bound），这是分支定界 (Branch and Bound) 算法的核心步骤。

  4. 算法设计（松弛 Relaxation）：

    • 对于困难的非凸问题（如整数规划），一个核心思想是“松弛”。例如，一个整数规划的可行解是一些离散的点。这些离散点的凸包构成了一个凸集。
    • 我们通过去掉整数约束，将其松弛为一个线性规划问题，其实我们求解的就是在整数解的凸包上进行优化。
    • 这个松弛问题（LP Relaxation）的解为原问题提供了一个重要的界（Bound），这是分支定界（Branch and Bound）等高级算法的基础。

可以这样总结：凸组合是基本运算，凸集是具有良好性质的区域，凸包是对任意点集构造这种良好区域的方法。

列 / 行 生成⚓︎

列生成⚓︎

列生成 (Column Generation) 是求解大规模线性规划（并进而求解大规模整数规划）的核心高级技巧之一。它非常适合那些约束数量相对较少，但变量（列）数量巨大甚至无穷的问题。

想象一个线性规划问题，它有几百万个甚至更多的变量（列）。一次性把所有变量都加载到模型中是不现实的。

列生成的核心思想是：从一个小的子集开始：我们不考虑全部的变量，只选取一小部分“有前途的”变量（列）构成一个规模较小的限制主问题 (Restricted Master Problem, RMP)。

求解RMP：这个RMP规模小，可以用标准单纯形法等方法快速求解。

寻找“更优”的变量：利用上一步求解RMP得到的对偶变量（影子价格），去检查在所有未被包含的变量中，是否存在一个如果加入RMP，就能让目标函数变得更好的变量。这个寻找过程就是“定价子问题”(Pricing Subproblem)。

按需添加：如果找到了这样的变量（列），就把它加入RMP，形成一个新的、稍大一点的RMP，然后回到第2步。

如果没有找到任何能改进当前解的变量，说明当前的RMP解对于原问题（包含所有变量的完整问题）也已经是最优的了。算法结束。

行生成⚓︎

主要指的就是 Benders 分解，主要用于解决具有特定结构的混合整数规划问题，这些问题可以被分解为：

  1. “困难”的决策变量：通常是整数或二元变量，一旦确定下来，问题的剩余部分就变得简单。
  2. “简单”的评估变量：通常是连续变量，当困难变量固定后，它们对应的子问题是一个简单的线性规划（LP）。

核心思想是“分解与迭代”：

  1. 主问题 (Master Problem)：只负责对“困难”的整数变量做出战略决策。
  2. 子问题 (Subproblem)：接收主问题给出的战略决策（固定的整数变量值），然后评估这个决策的后果，即计算出在这个决策下，连续变量能达到的最优成本。
  3. 生成约束/行 (Generate Cut/Row)：如果子问题发现主问题的决策是不可行的，或者虽然可行但主问题低估了其成本，子问题就会生成一个新的约束（一行），并将其反馈给主问题。
  4. 迭代：主问题加入了这个新约束后，变得更加“聪明”，它会在下一次迭代中做出更好的决策。

总结：行生成 vs. 列生成⚓︎

特性 行生成 (Benders Decomposition) 列生成 (Column Generation)
问题结构 约束较多，变量可分解为“困难”和“简单”两组 变量（列）极多，约束相对较少
分解方式 在变量上分解问题 (Project onto x-space) 在约束上对偶化，从而分解问题
主问题 近似原问题，包含困难变量\(x\)和成本变量\(\eta\)，不断添加约束（行） 包含一小部分变量（列）的子集，不断添加变量（列）
子问题 评估问题：固定\(x\)，求解一个LP，检查可行性与成本 定价问题：寻找一个具有负Reduced Cost的新列来加入主问题
信息传递 子问题通过其对偶解生成约束（割平面）给主问题 主问题通过其对偶解（影子价格）为子问题定价
本质 求解一个松弛版本，并通过添加行来逐步加强这个松弛 求解一个受限版本，并通过添加列来逐步扩展这个限制

KKT 条件⚓︎

启发式算法相关⚓︎