2.2 凸性与计算复杂性：沙盘地形先侦查

2.2 凸性与计算复杂性：沙盘地形先侦查

本节摘要：求解之前要侦察两件事——地形（问题是凸还是非凸）与兵力（算法耗时是否随规模可控增长）。本节给出凸集与凸函数的判别方法及代码验证，解释"凸问题局部最优即全局最优"为何让算法工程师安心；再以旅行商问题为例展示组合爆炸，建立多项式时间与 NP 难的工程直觉。

为什么同样的代码，有时秒出、有时跑到天荒地老

初学者最常见的挫败：同一个求解器，昨天在 20 个变量的配比问题上毫秒出解，今天在 30 个城市的路径问题上跑了一夜还在转。差别不在代码，在问题的两个深层属性：地形与规模增长方式。这两件事都可以在写代码之前侦察出来，本章把它们当作建模的收尾动作。

侦察一：地形是凸的吗

想象可行域是一片山地，目标函数是海拔，求最优解就是找最低的谷底。如果整片地形是碗状的（凸的），从任何出发点往下走，走到的地方必然是全局最低点——因为碗里没有藏起来的坑。如果地形有多个坑（非凸），下山算法就只能找到出发地附近的那个坑，换初始点可能落进另一个坑。

数学定义两条。凸集：集合里任取两点，连线整段仍在集合里——圆盘、三角形、半平面都是；环形、月牙形不是。凸函数：任取两点，函数图像在连线之下，等价判别是二阶导数（Hessian 矩阵）处处半正定。用代码验证最直观：

import numpy as np

def is_convex_1d(f, lo=-5, hi=5, n=400, samples=50):
    """在区间上撒点验证凸定义：中点函数值不超过端点均值"""
    xs = np.linspace(lo, hi, n)
    ys = f(xs)
    rng = np.random.default_rng(0)
    for _ in range(samples):
        i, j = sorted(rng.integers(0, n, 2))
        mid = (i + j) // 2
        if ys[mid] > (ys[i] + ys[j]) / 2 + 1e-12:
            return False, (xs[i], xs[j])
    return True, None

print(is_convex_1d(lambda x: x**2))        # (True, None)   凸
print(is_convex_1d(lambda x: np.sin(x)))   # (False, ...)   非凸
​

组合层面同样重要：凸目标 + 凸可行域 = 凸优化问题。线性规划两类都满足，天然凸；二次目标配线性约束（第 8 章 LQR 的影子）也是凸的，前提是二次项矩阵半正定。工程上有一张速查表：

💡 关键直觉：判断模型凸性，就是判断"能不能放心从任意初始点出发"。凸问题给算法工程师的安全感，相当于暴雨天出门前确认全城只有一家地势最低的咖啡馆——不管从哪条路走过去，到的都是同一家。

侦察二：兵力够吗——组合爆炸与 NP 难

旅行商问题（第 5 章正主，这里先当侦察样本）：30 个城市各走一次再回起点，问最短路线。路线总数是 29!/2，一个 30 位数字量级的数；宇宙原子数才约 80 位数级。枚举在任何计算机上都不现实。这不是程序写得不好，是问题本身的结构性困难。

复杂性的标尺是问题规模 n 增大时耗时的增长曲线：n、n²、n³ 这类多项式增长，规模翻倍耗时可预期地翻几倍，工程上"可解"；2ⁿ、n! 这类指数增长，n 每加 1 耗时翻倍以上，很快撞墙。用代码感受一下：

import time

def tour_count(n):
    import math
    return math.factorial(n - 1) // 2

for n in [10, 15, 20, 25]:
    print(f"n={n:2d}  路线数 {tour_count(n):.2e}")

# 多项式 vs 指数 的耗时增长（模拟每秒一亿次基本操作）
ops_per_sec = 1e8
for n in [30, 40, 50]:
    t_exp = 2.0**n / ops_per_sec
    print(f"n={n}: 指数算法约需 {t_exp/3.15e7:.1e} 年，n^3 算法 {n**3/ops_per_sec*1e3:.2f} 毫秒")
​

理论语境里，能在多项式时间内验证一个候选解的问题叫 NP；其中存在多项式求解算法的子类叫 P；NP 里最难的一批彼此等价的问题叫 NP 难（如整数规划、旅行商的判定版）。P 是否等于 NP 是未解之谜，但工程态度很明确：遇到 NP 难，别追求精确最优，直接规划启发式、近似算法或缩小规模。第 3 章的分支定界、第 5 章的近邻与 2-opt，都是这个态度的产物。

另一个工程要点：复杂性看的是最坏情况。实际数据常有特殊结构（稀疏、间隔、树状约束），真实求解器在"理论上 NP 难"的问题上常常几分钟出解。所以正确的姿势是：复杂性侦察定基调（要不要写精确算法），实跑小规模实例校准（真实数据是否友好），两手都要。

⚠️ 常见坑：把"求解器返回了一个解"当成"求到了最优解"。非线性求解器默认只报局部最优；整数求解器有时间上限，超时会返回带间隙的可行解。读日志、看状态码，是建模者的基本卫生习惯。

侦察清单：动笔前的五分钟

把本节内容压成一张可以在开会时过一遍的清单。第一问，变量是连续还是离散——离散即预警 NP 难，规模超过几万个二值变量就要规划分解或启发式。第二问，目标与约束有没有曲线——全是线性即 LP，安心；有二次项就查二次矩阵是否半正定，凸则仍是安全区。第三问，约束数量与变量数量哪个大——约束远多于变量时对偶法与列生成有机会，反之割平面类方法更顺手。第四问，问题的特殊结构是什么——网络流、指派、最短路这类结构有专用多项式算法，识别出结构等于白拿十倍加速。第五问，需要的求解时间是分钟级、小时级还是隔夜级——答案直接决定精确算法与启发式的分界，以及要不要设间隙阈值提前收兵。五分钟换回的是整个项目周期的可控，这买卖在任何预算表里都划算。

本节要点回顾

• 凸性决定地形：凸目标加凸可行域，局部最优即全局最优，初始点无关紧要；
• 二阶判别与中点采样是验证凸性的两把尺子，代码几行就能跑；
• LP 与凸 QP 是安全区，整数规划与一般非线性是非凸雷区，入场前先备案；
• 复杂性看增长曲线：多项式可解与 NP 难的分野，直接决定精确算法还是启发式；
• 侦察 + 实测两手抓：理论上限定基调，小规模实测校准预期。

兵法和侦察术都齐了。下一章四件确定性兵器依次出鞘，从线性规划的单纯形法一路打到动态规划的贝尔曼方程。