凸优化 ¶

非线性优化（凸优化）课程的总览页：章节大纲、知识主线与历年题整理（去重 + 详解）。

Acknowledgement¶

• Dimitri P. Bertsekas《Nonlinear Programming》
• 《最优化、建模、算法和理论》- 北大

引论 ¶

优化算法很多时候都要利用数学上的结构，而凸优化就是利用了凸集、凸函数等结构，来简化优化问题的求解。

只要能建立成凸优化问题，就可以利用现成的工具包进行求解：

• cvx toolbox 在多项式时间复杂度中，找到全局最优解
• 可以在 \(O(n^{3.5})\) 左右时间复杂度中，找到全局最优解

大纲 ¶

章节导航 ¶

知识主线 ¶

1. 建模（01）：把实际问题写成 \(\min f(x),\ h(x)=0,\ g(x) \ge 0\) 的标准形式；利用凸性保证「局部最优即全局最优」，凸规划下 KKT 条件为充要条件。
2. 无约束问题（02-03）：先掌握极值点的解析条件（平稳点 \(\nabla f = 0\) + Hessian 正定），再掌握数值迭代的三要素——迭代方向、步长、终止条件。
3. 有约束问题（04-05）：先掌握最优性条件（可行方向、Gordan、Fritz John、Slater、KKT），再掌握把约束问题无约束化的数值方法——罚函数法 / 障碍函数法（SUMT 逐次逼近）。
4. 现代优化算法（06）：不依赖导数信息的种群 / 概率搜索（遗传算法、蚁群算法、模拟退火），用于求解 NPH 等难解问题。

历年题整理（去重）¶

1. 广义牛顿法与最速下降法（2025）¶

与最速下降法的区别 ¶

牛顿法的优势 ¶

• 多利用了二阶导数（曲率）信息，选择方向时不仅看坡度是否够大，还考虑走一步之后坡度的变化，「看得更远」，极值点附近收敛速率远高于最速下降法；
• 最速下降法的相邻两次搜索方向互相垂直（最优步长下 \(\nabla f(x^{(k+1)}) \perp \nabla f(x^{(k)})\)），迭代路径呈「之字形」，牛顿法避免了这种来回震荡。

牛顿法的缺陷 ¶

• 计算量大：每次迭代都要计算 Hessian 矩阵并求逆，求逆的复杂度为 \(O(n^3)\)；
• 数值不稳定：\(H_k\) 病态时 \(H_k^{-1}\) 误差放大，迭代点可能跑飞；
• 远离极值点时可能失效：Taylor 展开只在邻域内有效，远离极值点时牛顿方向不一定是下降方向，甚至可能发散。

缺陷的克服方法 ¶

1. 修正牛顿法（Levenberg-Marquardt 阻尼）：求解 \((H_k+\mu_k I)\Delta x=-g_k\)，取 \(\mu_k>\left|\lambda_{\min}\right|\)（\(H_k\) 的最小负特征值）保证矩阵正定，从而保证 \(p_k\) 为下降方向。\(\mu \to 0\) 退化为牛顿法，\(\mu \to \infty\) 退化为最速下降法；
2. 拟牛顿法：用一阶信息构造 \(G_k \approx H_k^{-1}\)（满足拟牛顿条件 \(G_{k+1}y_k=\delta_k\)），如 DFP、BFGS，避免计算二阶导数与求逆；
3. 混合策略：迭代初期用最速下降法（远端下降稳定），接近极值点后切换为牛顿法（局部收敛快）；
4. 阻尼牛顿法：在牛顿方向上做一维线搜索确定步长，改善远端行为。

2. 逐次逼近法：罚函数法与障碍函数法（2024、2025）¶

SUMT 解决思路 ¶

通过构造制约函数，把有约束非线性规划问题转化为一系列无约束优化问题求解（SUMT，序列无约束极小化技术）：每次给定参数值求一个无约束问题的极小点，再改变参数重复求解，让解序列在参数的极限过程中逼近原约束问题的最优解——即「逐次逼近」。

罚函数法（外点法）¶

• 构造：对可行域外的点施加惩罚，允许迭代点从外部逼近最优解

罚因子 \(M>0\) 逐次增大、趋于无穷；当 \(M \to \infty\) 时 \(x^*\) 即为原问题的约束极值解。

• 优点： 1. 初始点可以任选，不要求可行，启动方便； 2. 既能处理不等式约束，也能处理等式约束； 3. 对目标函数在可行域外有定义的问题同样适用。
• 缺点： 1. 罚因子 \(M\) 很大时函数病态，数值计算困难； 2. 迭代点在可行域外，中间结果不是可行解； 3. 收敛较慢。
• 常见罚函数形式：\(h_i^2(x)\)、\([\min (0, g_j(x))]^2\)、\(|h_i(x)|\) 等。

障碍函数法（内点法）¶

• 构造：在边界上设置「高墙」，阻止迭代点离开可行域，从内部逼近最优解

障碍因子 \(r>0\) 逐次减小、趋于 \(0\)；\(x\) 从严格内点出发逐渐趋向边界上的最优解。

• 优点： 1. 迭代点始终在可行域内，每个中间结果都是可行解； 2. 相对收敛较快，数值上较稳定。
• 缺点： 1. 初始点必须是严格内点，启动要求高； 2. 不能处理等式约束； 3. 要求目标函数在可行域内处处有定义。

两法的共同点 ¶

• 都属于 SUMT 逐次逼近思想：约束问题 → 一系列无约束问题；
• 都通过参数的极限过程（\(M \to \infty\) 或 \(r \to 0\)）逼近原问题最优解；
• 收敛性分析殊途同归：极小点序列的极限都满足 KKT 条件（\(\lambda_i(k)=-2M_k h_i(x^{(k)})\)、\(\mu_j(k)=-2M_k g_j(x^{(k)})\) 或 \(\mu_j(k)=r/g_j(x^{(k)}) \ge 0\)）。

起作用约束与不起作用约束 ¶

• 起作用约束（紧约束）：在某点处取等号的约束。对不等式约束 \(g_j(x) \ge 0\)，若 \(g_j(x^{(0)})=0\)，称该约束在 \(x^{(0)}\) 处起作用；起作用约束集合 \(J(x^{(0)})=\{j \mid g_j(x^{(0)})=0\}\)（等式约束恒起作用）。
• 不起作用约束（松约束）：\(g_j(x^{(0)})>0\)，约束未被触及，对点的移动不起限制作用；在 KKT 条件中对应乘子 \(\mu_j=0\)。

3. NPH 问题与多项式时间最优算法（2025）¶

回答：在目前学术界普遍接受的假设下（\(P \ne NP\)），NPH 问题不存在多项式时间最优算法；但严格地说，这仍是一个尚未解决的开放问题。

理由 ¶

1. 定义：NPH（NP-Hard）问题是指所有 NP 问题都可以在多项式时间内归约到它的问题。
2. 归约关系：若任意一个 NPH 问题存在多项式时间最优算法，则所有 NP 问题都可以借助归约在多项式时间内求解，即 \(P = NP\)。
3. 开放问题：\(P\) 与 \(NP\) 是否相等是计算机科学最著名的未解难题（千禧年七大数学难题之一）。几十年来，大量 NPC 问题（SAT、TSP、01 背包等）都没有找到多项式时间算法，这是 \(P \ne NP\) 猜想的有力经验证据，学界普遍猜想 \(P \ne NP\)。
4. 结论：因此普遍认为 NPH 问题不存在多项式时间最优算法，但该结论尚未被证明。实际中通常采用指数时间精确算法，或多项式时间的近似算法 / 启发式算法（贪心、遗传算法、模拟退火、蚁群算法、分支定界等）求解。

4. 遗传算法求 \(\max x^2\)（2025）¶

编码：\(x\) 取 \(0 \sim 15\) 共 16 个整数，用 4 位二进制串编码（\(0000 \sim 1111\)）。

Step 1 初始群体（随机生成 4 个个体）并计算适应度（取 \(f(x)=x^2\)）：

\(\sum f = 330\)，平均适应度 \(82.5\)。

Step 2 选择（轮盘赌）：产生 4 个 \([0,1]\) 随机数，落入哪个累积区间就选中哪个个体。例如随机数 \(0.25,\ 0.42,\ 0.65,\ 0.90\)：

• \(0.25 \to\) B，\(0.42 \to\) B，\(0.65 \to\) D，\(0.90 \to\) D
• 选择结果（交配池）：\(\{1011,\ 1011,\ 1101,\ 1101\}\)

Step 3 交叉（单点交叉，配对两两进行）：

• 配对 1：\((1011,\ 1101)\)，交叉点在第 2 位后：\(10\,|\,11 \times 11\,|\,01 \Rightarrow 1001(9),\ 1111(15)\)
• 配对 2：\((1011,\ 1101)\)，交叉点在第 3 位后：\(101\,|\,1 \times 110\,|\,1 \Rightarrow 1011(11),\ 1101(13)\)（末位相同，交换不产生新个体）

Step 4 变异：取变异概率 \(p_m = 0.01\)，共 \(4 \times 4 = 16\) 个基因位，期望翻转 \(0.16\) 位，本代假设无位翻转。

进化一代后的新群体：

\(\sum f = 596\)，平均适应度 \(149 > 82.5\)；最优个体 \(1111 \Rightarrow x^*=15\)，\(f=225\)，已达理论全局最优。

5. 马尔可夫过程：状态转移矩阵与价值函数（2024、2025）¶

通用解法模板 ¶

1. 构造状态转移矩阵 \(P\)：从图中读出每个状态的出边概率，\(P_{ij}=P(s_{t+1}=j \mid s_t=i)\)（第 \(i\) 行 = 从状态 \(i\) 出发的转移概率，每行之和为 1）；
2. 读出即时奖励：\(R(s_i)\) 为图中标注在各状态上的奖励；
3. 列 Bellman 期望方程并求解：

矩阵形式：

示例（三个状态 \(s_1, s_2, s_3\)：\(s_1 \to s_2\) 概率 1，\(s_2 \to s_1 / s_3\) 各 0.5，\(s_3 \to s_2\) 概率 1；奖励 \(R=(1, 0, -1)^T\)）：

代入 \(V=(I-0.85P)^{-1}R\)，即解方程组：

解得 \(V=(1,\ 0,\ -1)^T\)。

6. 有约束与无约束优化的算法设计区别（2024）¶

设计要素对比 ¶

原因分析 ¶

无约束问题中任何下降方向都可行；有约束问题中方向选择必须兼顾下降性与可行性——一个纯下降方向可能直接穿出可行域，一个纯可行方向可能不使目标函数下降。

难点 ¶

1. 最优点处可行下降方向可能不存在（这正是最优性的几何刻画）；
2. 起作用约束集合 \(J(x^{(k)})\) 随迭代变化，算法需动态识别；
3. 数值上：罚因子 \(M \to \infty\) 或障碍因子 \(r \to 0\) 都会带来函数病态；
4. 非凸问题时只有局部收敛性保证，难以保证全局最优。

7. 现代优化算法的终止条件（2024）¶

数值迭代类算法（梯度法、牛顿法等）¶

1. 前后差值够小： - 绝对误差准则：\(\|x_{k+1}-x_k\| \le \varepsilon_1\) 或 \(\left|f(x_{k+1})-f(x_k)\right| \le \varepsilon_2\)——迭代点的移动或函数值的改善已经可以忽略； - 相对误差准则：\(\dfrac{\|x_{k+1}-x_k\|}{\|x_k\|} \le \varepsilon_3\) 或 \(\dfrac{\left|f(x_{k+1})-f(x_k)\right|}{\left|f(x_k)\right|} \le \varepsilon_4\)——消除量纲 / 数值尺度的影响。
2. 梯度够小：\(\|\nabla f(x^{(k)})\| \le \varepsilon\)——到达平稳点；凸目标函数下即全局最优。
3. KKT 残差足够小（有约束问题）：约束最优性条件近似满足。

现代（智能）优化算法（遗传、蚁群、模拟退火等）¶

1. 达到最大迭代次数 / 最大进化代数：预算用尽，防止无限迭代；
2. 最优适应度连续多代无显著改进：算法已收敛或陷入停滞（早停）；
3. 种群适应度变化很小 / 多样性低于阈值：种群趋同，继续进化收益极小（早熟收敛）；
4. 达到预设精度或目标值：解的质量已满足要求；
5. 计算资源限制：时间 / 函数评估次数达到上限。

8. 求 \(N\) 个数最大值的算法设计与复杂度（2024）¶

算法：LinearMax
输入：数组 a[1..N]
输出：最大值 max

max ← a[1]
for i ← 2 to N do
    if a[i] > max then
        max ← a[i]
return max

时间复杂度分析：循环执行 \(N-1\) 次，每次做一次比较，故时间复杂度为 \(O(N)\)；只用了常数个辅助变量，空间复杂度 \(O(1)\)。

最优性：在只允许比较的模型下，\(N-1\) 次比较已是下界——每次比较至多淘汰一个候选，\(N\) 个候选要淘汰 \(N-1\) 个才能确定最大值，因此该算法是渐近最优的。