凸优化考前突击¶

Note

这门课距离考试还有10天. 一学期一次课也没去, 甚至连教室在哪都不知道...

突击看PPT, 发现完全是💩依托, 也不知道就算课堂上认真听讲有啥用...

还好有 Gemini 😍

复习策略是:

(1) 阶段1: 3天

先把课件逐章喂给AI, 让它来把每一章的故事理顺, 而不是像PPT那张毫无逻辑的堆砌

(2) 阶段2: 3天

理解清楚以后, 逐章纸质整理: 公式、推导证明、简单习题 ...

(3) 阶段3: 3天

做两套往年题, 飞速拟合

参考资料:

Chapter 2: 对偶与最优性条件¶

“故事”是这样的：

遇到一个“困难”问题 (Primal Problem)： 我们想在一个“牢笼”（约束条件）里找到一个最低点
我们不直接解它，而是创造一个“影子”问题 (Dual Problem)： 这个影子问题本身更容易求解 (它总是凹的，求极大值就是凸优化)
我们发现这个“影子”的最高点，永远低于“真实”的最低点 (Weak Duality)： 这给了我们一个下界
在“特定条件”下，这个“影子”的最高点和“真实”的最低点是相等的 (Strong Duality)： 这就是我们的 “Aha!” 时刻
KKT 条件： 当“影子”和“真实”相等时，它们在最优解 $x^*$ 处必须满足的一组“铁证”。只要找到满足 KKT 的点，我们就找到了答案

登场角色1: 原始问题¶

我们想最小化一个目标函数 $f_0(x)$ , 但我们的 $x$ 被关在了一个“牢笼”里

这个“牢笼”由两种“栅栏”构成：

不等式约束 (Inequality)： $f_i(x) \le 0$ (比如，你的成本 $f_i(x)$ 不能超过预算 0)
等式约束 (Equality)： $h_i(x) = 0$ (比如，你生产A和B的数量必须严格相等)
这个问题的真正最优值，我们称之为 $p^*$

为什么它困难？ 因为这些约束（尤其是 $h_i(x)=0$）把可行域限制得非常复杂，你不能简单地求导为0

登场角色2: 拉格朗日函数¶

既然“硬约束”这么麻烦，我们引入一个“价格”系统，把“硬约束”变成“软惩罚”

这就是拉格朗日函数 $L(x, \lambda, \nu)$

\[L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)\]

$f_0(x)$： 你的“原始成本”
$\lambda_i$ 和 $\nu_i$： 违反约束的“价格”（拉格朗日乘子）
$\lambda_i f_i(x)$： 违反不等式约束的“惩罚金”
$\nu_i h_i(x)$： 违反等式约束的“惩罚金”

关键设定 (Dual Feasibility)：

我们必须规定不等式约束的价格 $\lambda_i \ge 0$

为什么？
- 我们的约束是 $f_i(x) \le 0$
- 如果你“违规”了，即 $f_i(x) > 0$，我们必须“惩罚”你
- 为了让“惩罚金” $\lambda_i f_i(x)$ 为正，价格 $\lambda_i$ 必须为正
而等式约束 $\nu_i$ 可以是任意实数
- 因为 $h_i(x)$ 无论正负都是违规, $\nu_i$ 可以配合它产生惩罚

登场角色3: 对偶函数¶

现在，我们来问一个问题：给定一组“价格” $(\lambda, \nu)$，一个“最聪明”的 $x$（它暂时无视了约束，只看“总成本” $L$）能把总成本压到多低？

这就是拉格朗日对偶函数 $g(\lambda, \nu)$

\[g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu)\]

inf (infimum) 在这里你就理解为 min（最小值）。
$g$ 的神奇特性： $g(\lambda, \nu)$ 永远是一个凹函数
这太棒了！ 因为 $g$ 是凹函数，求 $g$ 的最大值（$\max g$）就是一个凸优化问题，这是我们擅长解决的！

核心剧情1: 弱对偶性¶

这是我们的第一个重大发现!

定理: 对于任何“合理的价格” (即 $\lambda \ge 0$), 对偶函数 $g(\lambda, \nu)$ 的值, 永远 小于或等于 我们原始问题的真正最优值 $p^*$

$g(\lambda, \nu) \le p^*$ (当 $\lambda \ge 0$)

Proof:

$p^*$ 是在“牢笼” (可行集 $C$) 里的最小值
$g(\lambda, \nu)$ 是在“更广阔的土地” (定义域 $\mathcal{D}$) 上的最小值
在“牢笼” $C$ 里， $x$ 是“守规矩”的，所以 $h_i(x)=0$ 且 $f_i(x) \le 0$
因为 $\lambda_i \ge 0$ 且 $f_i(x) \le 0$，所以 $\sum \lambda_i f_i(x) \le 0$
所以，在“牢笼” $C$ 里，$L(x, \lambda, \nu) = f_0(x) + (\le 0) + (0) \le f_0(x)$
因此：$g(\lambda, \nu) = \min_{x \in \mathcal{D}} L(x, \lambda, \nu) \le \min_{x \in C} L(x, \lambda, \nu) \le \min_{x \in C} f_0(x) = p^*$
翻译： "影子"（对偶函数）永远是我们真实目标（$p^*$）的一个下界

核心剧情2: 对偶问题¶

既然任何 $g(\lambda, \nu)$ 都是一个下界, 我们自然想知道：这个下界最高能有多高？

这就是拉格朗日对偶问题 (Dual Problem)

\[\max_{\lambda, \nu} \quad g(\lambda, \nu)\]

\[\text{s.t.} \quad \lambda \ge 0\]

我们把这个“最高的下界”的值称为 $d^*$
根据弱对偶性，我们永远有 $d^* \le p^*$
$p^* - d^* \ge 0$ 这个差距，就叫对偶间隙 (Duality Gap)

剧情高潮: 强对偶性¶

在极少数（但对我们极其重要）的情况下, 这个“对偶间隙”会消失！

强对偶性 (Strong Duality)：$d^* = p^*$

这什么时候发生？
- 一般不成立
- 但对于凸优化问题 (即 $f_0, f_i$ 都是凸函数， $h_i$ 是仿射函数)，它“通常”成立
- “通常”需要一个“通行证”，最著名的就是 Slater 约束品性
Slater 条件是什么？
- 只要你能找到至少一个 $x_0$ 严格满足所有不等式约束（即 $f_i(x_0) < 0$）并且满足所有等式约束（$Ax_0 = b$），那么强对偶性就成立
- 人话: 只要你的“牢笼”不是一个“密不透风的空壳”，而是有一点点“内部空间”，你就可以用“影子”来完美找到“真实”的解

最终章: KKT 条件¶

这是你问题的核心!

KKT 条件就是当强对偶性 $d^* = p^*$ 成立时，最优解 $x^*$ 和最优价格 $(\lambda^*, \nu^*)$ 之间必须满足的一组“铁证”

Proof:

如果 $d^* = p^*$，那么在最优解 $x^*$ 和 $(\lambda^*, \nu^*)$ 处，下面这串推导必须成立：

$f_0(x^*) = p^*$ (定义)

$= d^* = g(\lambda^*, \nu^*)$ (强对偶)

$= \inf_x L(x, \lambda^*, \nu^*)$ (对偶函数的定义)

$\le L(x^*, \lambda^*, \nu^*)$ ($\inf$ 小于等于任意一点)

$= f_0(x^*) + \sum \lambda_i^* f_i(x^*) + \sum \nu_i^* h_i(x^*)$ (L的定义)

$\le f_0(x^*)$ (因为 $x^*$ 可行， $\lambda_i^* \ge 0, f_i \le 0, h_i = 0$)

我们得到了一个 $f_0(x^*) \le L(x^*, \lambda^*, \nu^*) \le f_0(x^*)$ 的“三明治” !

这说明中间所有的 “小于等于” 都是 “取等”

这个“必须相等”给我们揭示了四组必须满足的 KKT 条件

原始可行性
- $f_i(x^*) \le 0$
- $h_i(x^*) = 0$
- (废话， $x^*$ 必须在“牢笼”里)
对偶可行性
- $\lambda_i^* \ge 0$
- (废话，“价格”必须是“合理”的)
互补松弛性
- $\sum \lambda_i^* f_i(x^*) = 0$ $\implies$ $\lambda_i^* f_i(x^*) = 0$ 对每个 $i$ 成立
- 这是最核心的洞察！ 它意味着：
  - 如果一个约束不在边界上 ($f_i(x^*) < 0$，即“有空余”)，那么它的“价格”必须是 0 ($\lambda_i^* = 0$)
  - 如果一个约束的“价格”大于 0 ($\lambda_i^* > 0$)，那么这个约束必须在边界上 ($f_i(x^*) = 0$)
梯度平稳性
- $\inf_x L(x, \lambda^*, \nu^*) = L(x^*, \lambda^*, \nu^*)$ [cite: 411, 412]，这意味着 $x^*$ 必须是 $L(x, \lambda^*, \nu^*)$ 的一个极小值点
- 在 $x^*$ 这一点，拉格朗日函数 $L$ 对 $x$ 的梯度必须为 0
- $\nabla f_0(x^*) + \sum \lambda_i^* \nabla f_i(x^*) + \sum \nu_i^* \nabla h_i(x^*) = 0$

来个例题拟合一下:

alt text

Chapter 3: 无约束优化问题¶

第三章的核心故事：一个“盲人”在雾中下山

你 (算法): 一个“盲人”徒步者
目标函数 $f(x)$: 一片连绵起伏的山谷（一个“碗”）
目标点 $x^*$: 山谷的“最低点”
约束: 无约束！你可以在山谷的任何地方行走
“雾”: 你看不见全局，只能感知你脚下的情况
你的工具:
1. 梯度 $\nabla f(x)$: 你的“坡度计”。它告诉你当前位置最陡的上坡方向
2. Hessian $\nabla^2 f(x)$: 你的“曲率计”。它告诉你山谷在你脚下是“尖”的还是“平”的
你的目标: 找到山谷最低点 $x^*$，也就是唯一坡度为0的地方
你的策略 (通用下降方法): x^{k+1} = x^k + t^k d^k

这一章所有的知识点，都是在回答两个问题:

方向 $d^k$ 怎么选？ (最速下降? 牛顿下降?)
步长 $t^k$ 怎么定？ (精确搜索? 回溯下降?)

1. 强凸性假设¶

这是我们整个故事的“安全保证”

普通凸函数 (Convex):
- 保证你处在一个“碗”里，没有“假”的谷底（局部最小值）
- 但这个“碗底”可能是一条平坦的“河谷”（有无穷多最优解）
强凸性假设 (Strong Convexity):
- 数学形式: $\nabla^2 f(x) \succeq mI$，且 $m > 0$
- 生动形象: 这不仅是个“碗”，而且是个形状特别好的“碗”。它没有平坦的碗底，在任何地方都有一个最小的曲率 $m$
- 好处:
  1. 它保证了山谷最低点 $x^*$ 是唯一的
  2. 它让我们的“工具”变得极其强大

2. 上界/下界¶

因为“强凸性”这个安全保证，我们解锁了几个强大的“仪表盘”:

“仪表盘”读数：仅凭我脚下的“坡度” $\|\nabla f(x)\|_2$，我就能估算出我离“谷底” $p^*$ 还有多远

次优性上界:
- 数学形式: $f(x) - p^* \le \frac{1}{2m}\|\nabla f(x)\|_2^2$
- 停止准则: “我离谷底的最大高度差，不会超过我脚下坡度平方的 $\frac{1}{2m}$ 倍”
- 用途:
  - 这就是我们的停止条件
  - 当我发现脚下的坡度 $\|\nabla f(x)\|_2$ 足够小 (比如 $\le \epsilon$)，这个公式就保证了我的高度 $f(x)$ 已经离谷底 $p^*$ 非常非常近
  - 我可以停下来休息了
次优性下界:
- 数学形式: $f(x) - p^* \ge \frac{1}{2M}\|\nabla f(x)\|_2^2$
- 生动形象: “我离谷底的最小高度差，至少是我脚下坡度平方的 $\frac{1}{2M}$ 倍”
- 这里的 $M$ 是曲率的上界，即 $\nabla^2 f(x) \preceq MI$

3. 通用下降方法¶

“通用下降方法” 是我们下山的总纲领。

给定 $x^0$
停止条件: 如果 $\|\nabla f(x^k)\|_2 \le \epsilon$（坡度够平了），停止
确定方向 $d^k$：必须是下降方向
- 数学保证: 你的方向 $d^k$ 必须和“上坡”方向 $\nabla f(x^k)$ 形成“钝角”
- 数学形式: $\nabla f(x^k)^T d^k < 0$
确定步长 $t^k$ (直线搜索)：沿着 $d^k$ 方向走 $t^k$ 这么远
更新: $x^{k+1} = x^k + t^k d^k$
GOTO 2

4. 迈步子: 精确直线搜索¶

这是确定步长 $t^k$ 的第一种方法:

生动形象: “我既然选定了这个方向 $d^k$，我就要沿着这个方向走到头，直到找到这条直线上能达到的最低点，我才停下”
数学形式: $t = \text{argmin}_{s \ge 0} f(x^k + s d^k)$
评价:
- 这一步本身很“完美”，但“找”这个 $t$ 的计算代价可能非常大
- 你为了“一步”的完美，可能要花掉“十步”的力气

5. 迈步子: 回溯直线搜索¶

这是确定步长 $t^k$ 的第二种，也是更实用的方法:

生动形象: “我不想花时间去找‘完美’的步长。我只求‘足够好’的下降就行”
算法:
1. 先定个目标: “我希望我下降的高度，至少是我‘线性’预期的 $\alpha$ 倍” (比如 30%)
  - 这条“目标线”是: $f(x) + \alpha t \nabla f^T d$
2. 大胆尝试: 先试一步大步 $t=1$
3. WHILE 循环 (检查): while f(x + t*d) > f(x) + α*t*∇f(x)ᵀd
  - 翻译: “如果我这一步迈出去，发现 $f$ 的值高于我的‘目标线’……”
4. 回溯: “……说明步子迈大了。我把步长 $t$ 缩短一点 ($t = \beta t$，比如打个8折)，再看看”
5. End
评价:
- 这是最常用的策略。它计算代价小，并且保证了你会“充分”下降

6. 定方向: 最速下降方法¶

这是最本能的下降方向:

生动形象 (方向 $d^k$): “我不知道山谷长什么样，但我能感觉到我脚下最陡的上坡方向 ($\nabla f(x)$)。我反着走不就行了！”
数学形式:
- 方向 $d^k = - \nabla f(x^k)$
- 这“天然”满足下降条件：$\nabla f(x^k)^T d^k = -\|\nabla f(x^k)\|_2^2 < 0$。
收敛性:
- 它是线性收敛 (Geometric Series)。
- $f(x^k) - p^* \le c^k (f(x^0) - p^*)$。
- 致命弱点: 收敛因子 $c = (1 - m/M)$
  - $M/m$ (Hessian的条件数) 反映了山谷的“狭长”程度
  - 如果山谷又窄又长 (M/m 很大)，$c$ 就会非常接近 1。这意味着 $c^k$ 下降得极其缓慢
- 生动形象: 你会在这个狭长的山谷里，像“Z”字形一样，缓慢地来回“震荡”下山

7. 定方向: 牛顿下降方法¶

这是最“聪明”的下降方向:

生动形象 (方向 $d_{nt}^k$):
- “只看坡度太‘短视’了！我要用我的‘曲率计’($\nabla^2 f$) 在我脚下造一个局部的‘二次模型碗’ ($\hat{f}$)”
- “这个模型碗和我脚下的真实山谷几乎一模一样。然后我一步跳到我这个‘模型碗’的碗底！”
数学形式 (牛顿方向):
1. 二阶近似: $\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$
2. 求模型碗的底: $\nabla_v \hat{f} = 0 \implies \nabla f(x) + \nabla^2 f(x) v = 0$
3. 解出方向: $v = -[\nabla^2 f(x)]^{-1} \nabla f(x)$
4. 这就是牛顿方向 $d_{nt}^k = - \nabla^2 f(x^k)^{-1} \nabla f(x^k)$
牛顿减少量 $\lambda(x)^2$:
- $\lambda(x_k)^2 = \nabla f(x_k)^T \nabla^2 f(x_k)^{-1} \nabla f(x_k)$
- 生动形象: 这是你“预估”的下降量 $f(x) - \hat{f}(x+d_{nt})$
- 用途: $\frac{1}{2}\lambda(x^k)^2 \le \epsilon$ 是牛顿法的停止准则
收敛性 (优势体现):
- 阶段1: 阻尼牛顿阶段 (离谷底远) $\|\nabla f(x)\|$ 较大
  - 此时步长 $t^k < 1$ (回溯法在起作用)，算法稳定下降 (线性收敛)
- 阶段2: 二次收敛阶段 (离谷底近)：$\|\nabla f(x)\|$ 足够小
  - 回溯法会发现 $t^k=1$ 永远是最好的
  - 收敛速度是“二次”的
  - 生动形象: 你离谷底的误差，在每一步都会被“平方”
  - $Error_{k+1} \approx (Error_k)^2$
评价:
- 梯度下降 (GD): 每一步的计算都很便宜 (只用 $\nabla f$)，但你需要很多很多步
- 牛顿方法 (Newton): 每一步的计算都极其昂贵 (要计算、存储、求逆一个 $n \times n$ 的 Hessian 矩阵)，但你只需要很少几步 (5-8步) 就能达到极高精度

Chapter 4: 等式约束优化问题¶

第四章的核心故事: “在‘铁轨’上找最低点”

我们的“世界” $f(x)$: 仍然是那个“山谷”（一个n维凸函数）
我们的“目标” $\min f(x)$: 仍然是找到山谷的最低点
新的“铁律” $Ax = b$:
- 这不再是第二章那种“软惩罚”的栅栏
- 这是一条刚性的“铁轨”。你必须始终在 $Ax = b$ 这条“铁轨”（一个仿射子空间）上
我们的新问题: 我们不能再去山谷的“全局最低点”（它很可能不在铁轨上），我们必须找到“铁轨”上的最低点

“物理定律” (KKT 条件):

在那个完美的“铁轨最低点” $x^*$，必须有两种“力”达到平衡

“重力” $\nabla f(x^*)$: 想要把你拉向“山谷”最低点的力
“铁轨的支持力” $A^T \nu^*$: “铁轨”为了让你不“脱轨”而施加的、垂直于铁轨的“反作用力”

在最优点 $x^*$，这两种力必须完美抵消：

\[\nabla f(x^*) + A^T \nu^* = 0\]

同时，你当然也必须在“铁轨”上：

\[Ax^* = b\]

这两个方程组就是我们的KKT条件。这一整章，就是教你如何用不同的方法来求解 $(x^*, \nu^*)$

1. 消除方法¶

完全不用看, 肯定不会考

生动形象: “在 $n$ 维空间里思考‘铁轨’太麻烦了。我能不能只用一个变量 $z$ 来描述我在铁轨上的‘位置’？”
数学推导:
1. “铁轨” $Ax = b$ 是一个 $n$ 维空间中的 $(n-p)$ 维仿射子空间（假设 $A$ 是 $p \times n$ 且行满秩）
2. 我们可以用一个“基点” $\bar{x}$ (满足 $A\bar{x} = b$) 和一组“方向向量” $F$ (它的列张成了 $A$ 的零空间，即 $AF=0$) 来参数化这条铁轨
3. 任何在“铁轨”上的 $x$ 都可以被唯一表示为：$x = Fz + \bar{x}$，其中 $z \in \mathbb{R}^{n-p}$
4. 消除！我们把 $x$ 代入原始问题 $f(x)$，得到一个新问题： $\(\min_z \tilde{f}(z) = f(Fz + \bar{x})$\)
评价:
- 优点: 我们把一个有约束问题变成了无约束问题！我们可以直接用第三章的牛顿法 $\min \tilde{f}(z)$ 来求解 $z^*$，然后 $x^* = Fz^* + \bar{x}$
- 缺点: 破坏了问题的原始结构。你需要先费力气去找到 $F$ 和 $\bar{x}$，这在计算上可能很昂贵

2. 对偶方法¶

完全不用看, 肯定不会考

生动形象: “我们故技重施，用第二章的‘拉格朗日乘子’ $\nu$ 来给 $Ax=b$ 这个约束定一个‘价格’”
数学推导:
1. 拉格朗日函数: $L(x, \nu) = f(x) + \nu^T (Ax - b)$
2. 对偶函数: $g(\nu) = \inf_x L(x, \nu)$
3. 对偶问题: $\max_\nu g(\nu)$
评价:
- 优点: 这也把原问题转化成了一个（通常）无约束的对偶问题。如果 $f(x)$ 有特殊结构("可分离"), 这种方法非常高效
- 缺点: 同样破坏了问题结构

3. 直接求解: 牛顿方法¶

这是本章的重中之重

生动形象: “我们不“消除”也不“绕道”。我们正面硬刚那两个KKT“物理定律”！我们知道 $x^*$ 和 $\nu^*$ 必须满足它们，所以我们用牛顿法来直接解这个方程组”
目标方程组 (KKT系统):
1. $r_{dual}(x, \nu) = \nabla f(x) + A^T \nu = 0$
2. $r_{primal}(x, \nu) = Ax - b = 0$
牛顿法的精髓: 我们在当前点 $(x, \nu)$ 处，对这个非线性方程组进行一阶泰勒展开（线性化），然后求解这个线性方程组，得到一个 “牛顿步进” $(d_x, d_\nu)$
推导 (关键！):
1. 线性化 $r_{dual}$:
  
  \[r_{dual}(x+d_x, \nu+d_\nu) \approx \nabla f(x) + \nabla^2 f(x) d_x + A^T \nu + A^T d_\nu = 0\]
  
  \[\implies \nabla^2 f(x) d_x + A^T d_\nu = -(\nabla f(x) + A^T \nu)\]
2. 线性化 $r_{primal}$:
  
  \[r_{primal}(x+d_x, \nu+d_\nu) \approx Ax + Ad_x - b = 0\]
  
  \[\implies Ad_x = -(Ax - b)\]
“KKT 矩阵”: 把这两个线性方程写成矩阵形式，这就是我们要解的核心

\[\begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ d_\nu \end{bmatrix} = \begin{bmatrix} -r_{dual} \\ -r_{primal} \end{bmatrix} = \begin{bmatrix} - \nabla f(x) - A^T \nu \\ b - Ax \end{bmatrix}\]

整理 KKT 矩阵的两种形式

(1) $(d_x, d_v)$:

\[\begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ d_\nu \end{bmatrix} = \begin{bmatrix} -r_{dual} \\ -r_{primal} \end{bmatrix} = \begin{bmatrix} - \nabla f(x) - A^T \nu \\ b - Ax \end{bmatrix}\]

未知数: $(d_x, d_\nu)$
$d_x$ 是 $x$ 的步长
$d_\nu$ 是 $\nu$ 的步长
更新法则:
- $x^{k+1} = x^k + t^k d_x$
- $\nu^{k+1} = \nu^k + t^k d_\nu$

(2) $(d_x, w)$:

\[\begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ w \end{bmatrix} = \begin{bmatrix} - \nabla f(x) \\ b - Ax \end{bmatrix}\]

未知数: $(d_x, w)$
$d_x$ 是 $x$ 的步长
$w$ 是 $\nu$ 的下一个“完整”目标值
更新法则:
- $x^{k+1} = x^k + t^k d_x$
- $\nu^{k+1} = \nu^k + t^k (w - \nu^k)$ (如果 $t^k=1$，那么 $\nu^{k+1} = w$)

这个“正面硬刚”的策略, 又分为两种情况:

初始点可行
初始点不可行

下面我们来细致看一看:

(1) 牛顿法 (可行初始点)

生动形象: “我们从一个已经在‘铁轨’上的点 $x^0$ 开始”
条件: $Ax^0 = b$
推导:
- 因为我们已经在铁轨上了 ($Ax^k = b$)，我们的 $r_{primal}$ 永远是 0
- 我们只希望我们的“下一步” $d_x$ 也沿着铁轨，即 $A(x^k + d_x) = b \implies Ad_x = 0$
- KKT 系统简化为：
  
  \[\begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ w \end{bmatrix} = \begin{bmatrix} - \nabla f(x) \\ 0 \end{bmatrix}\]
  
  (这里的 $w$ 就是 $d_\nu$，代表了我们“下一步”的对偶变量)

算法:

从可行的 $x^0$ 开始
解简化的KKT矩阵，得到 $d_x^k$
停止准则: 用“牛顿减少量” $\lambda(x)^2 = d_x^T \nabla^2 f(x) d_x$。它估算了 $f(x) - p^*$。如果 $\frac{1}{2}\lambda(x^k)^2 \le \epsilon$，退出
回溯直线搜索: $t^k=1$，while f(x^k + t^k d_x^k) > f(x^k) + \alpha t^k \nabla f(x^k)^T d_x^k，则 $t^k := \beta t^k$
更新: $x^{k+1} = x^k + t^k d_x^k$。(因为 $Ad_x^k=0$，我们永远保持在铁轨上)

(2) 牛顿法 (不可行初始点)

生动形象: “我们的‘火车’ $x^0$ 不在铁轨上。我们的每一步 $(d_x, d_\nu)$ 必须同时做两件事：1. 把火车“拉回”铁轨；2. 把火车“推向”山谷最低点”
条件: $Ax^0 \ne b$
推导:
- 我们不能用“简化”的 KKT 系统了。我们必须解那个“完整”的 KKT 矩阵：
  
  \[\begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ d_\nu \end{bmatrix} = \begin{bmatrix} - \nabla f(x) - A^T \nu \\ b - Ax \end{bmatrix}\]

算法:
从任意 $(x^0, \nu^0)$ 开始
解完整的KKT矩阵，得到 $(d_x^k, d_\nu^k)$
停止准则: 我们的目标是让所有“定律”都满足，即 $r_{dual}=0$ 且 $r_{primal}=0$。所以我们看“总残差”的范数：$\|r(x, \nu)\|_2 = \sqrt{\|r_{dual}\|_2^2 + \|r_{primal}\|_2^2}$。如果 $\|r\|_2 \le \epsilon$，退出
回溯直线搜索 (重大区别！):
- 我们不能只看 $f(x)$ 了，因为我们可能需要“上坡”来“回到铁轨”
- 我们的目标是让“总残差”范数下降！
- while \|r(x^k + t^k d_x^k, \nu^k + t^k d_\nu^k)\|_2 > (1 - \alpha t^k) \|r(x^k, \nu^k)\|_2。
更新: $x^{k+1} = x^k + t^k d_x^k$, $\nu^{k+1} = \nu^k + t^k d_\nu^k$

Chapter 5: 等式不等式约束优化问题¶

第5章的核心故事: "带 '力场' 的山谷"

第3章 (无约束): 你在一个“开放的山谷”中，自由寻找最低点
第4章 (等式约束): 你被锁在一条“铁轨” ($Ax=b$) 上，寻找铁轨上的最低点
第5章 (不等式约束):
- 你在一个山谷中，但山谷四周布满了“隐形电围栏” ($f_i(x) \le 0$)
- 你可以靠近围栏，但绝对不能穿过（否则 $f(x) \to \infty$）
- 同时，你也可能还被“铁轨” ($Ax=b$) 束缚着

我们的难题:

我们不能直接用第3章的牛顿法，因为它“看不见”围栏，会直接冲出去

我们也不想直接解第2章的KKT方程，因为 $\lambda_i f_i(x)=0$ 这个“互补松弛”条件是非线性的，非常难解

我们的天才策略:

我们不解这个“硬”问题，而是解一个“软”的近似问题

idea: "我不在围栏处设置‘无限高’的墙，而是在靠近围栏时，设置一个越来越强的‘排斥力场’（障碍函数 $\phi(x)$），把我推开"

1. 障碍方法¶

障碍方法是“算法”，中心路径是这个算法“行走的轨迹”。

A. 障碍方法

原始问题:

\[\min f_0(x)$ s.t. $f_i(x) \le 0, Ax=b\]
“力场” (障碍函数 $\phi(x)$): 我们用 $\phi(x) = - \sum \log(-f_i(x))$ 来模拟“围栏”
- 生动理解: 当 $f_i(x) \to 0$ (你靠近围栏) 时, $\log(-f_i(x)) \to -\infty$, 所以 $-\log(-f_i(x)) \to +\infty$. 这个“力场”的排斥力会变得无穷大，“推”你回来
"近似问题":

\[\min \quad t f_0(x) + \phi(x) \quad \text{s.t.} \quad Ax=b\]
$t$ 的角色: $t$ 是一个“旋钮”，用来平衡“你的目标”和“力场”
- $t$ 很小 (t=0.1): $\min 0.1 f_0(x) + \phi(x)$
  - “力场” $\phi(x)$ 占主导! 你根本不敢靠近“围栏”, 只会待在山谷最“安全”的正中央
- $t$ 很大 (t=100): $\min 100 f_0(x) + \phi(x)$
  - “目标” $f_0(x)$ 占主导! 你为了找到更低的 $f_0(x)$, 会不惜一切地靠近“围栏”, 直到被“力场”死死顶住

B. 中心路径

定义: 对于每一个 $t > 0$, 此“近似问题”都有一个唯一的解 $x^*(t)$
"中心路径"就是所有这些解 $x^*(t)$ 连起来的轨迹
生动理解: 这条路径, 就是当你慢慢调大“旋钮” $t$ (从0到 $\infty$) 时, 你（算法）在山谷中走过的轨迹

C. 障碍法算法

这个算法就是“爬行”在中心路径上的方法:

开始 (k=0): 找一个严格可行的 $x$ (在“围栏”内), 设置 $t = t^0$， $\mu > 1$ (比如 $\mu=10$)
中心点步骤:
- 求解当前的“近似问题”: $x^*(t) = \text{argmin}_x \ (t f_0(x) + \phi(x)) \ \text{s.t.} \ Ax=b$
- 怎么解？用我们第4章学的牛顿法! 这是一个内部循环
更新: $x := x^*(t)$
停止准则:
- 我们发现，在 $x^*(t)$ 这一点, 原问题的“对偶间隙” (Duality Gap) 恰好是 $\frac{m}{t}$ ($m$ 是不等式约束的个数)
- 如果 $\frac{m}{t} \le \epsilon$ (比如 $10^{-8}$), 说明“近似解”和“真实解”的差距已经足够小了。退出
增加难度: $t := \mu t$ (比如 $t = 10 \times t$)
回到步骤2

障碍法的优点: 思想简单，把“不等式”问题转化成了我们已经会解的“等式”问题

障碍法的缺点: 太慢了! 它的“中心点步骤”（第2步）是一个完整的牛顿法

2. 原对偶内点法¶

“障碍法”太慢了, 因为它坚持每一步都要完美地回到“中心路径” $x^*(t)$ 上

原对偶内点法说: “我为什么要完美地求解 $x^*(t)$？反正我下一步就要移动 $t$ 了...”

生动形象地解释一下:

障碍法: “我（在 $x$）要精确瞄准中心路径上的 $x^*(t)$,（花10步）走到那里. 然后 $t$ 变了, 我又（花10步）精确瞄准下一个 $x^*(\mu t)$ ...”
原对偶法: “我（在 $x$）只朝着 $x^*(t)$ 的方向, 迈出一步。然后我立刻更新 $t$, 瞄准新的 $x^*(\mu t)$, 再迈一步, 这岂不美哉?”

“原对偶法”的策略是“一步到位”。它不去解“障碍问题”，而是直接去解 “中心路径KKT条件”

(1) 目标:

找到一组完美的 $(x, \lambda, \nu)$，使其同时满足以下三个方程:

$r_{dual}(x, \lambda, \nu) = \nabla f_0(x) + \sum_{i=1}^m \lambda_i \nabla f_i(x) + A^T \nu = 0$
- 这是“力的平衡”：目标函数的“重力” + 不等式约束的“排斥力” + 等式约束的“支持力” = 0
$r_{pri}(x, \nu) = Ax - b = 0$
- 这是“在铁轨上”：必须满足等式约束
$r_{cent}(x, \lambda) = - \text{diag}(\lambda) f(x) - (1/t) \mathbf{1} = 0$
- 这是"在中心路径上": 即 $-\lambda_i f_i(x) = 1/t$
- ⚠️: 我们不再强求 $\lambda_i f_i(x)=0$，而是让它们等于一个很小的正数 $1/t$

(2) 现状:

我们的现状: 三个“残差”

在 $(x, \lambda, \nu)$ 这一点，这三个方程不等于 0。它们的值就是“残差”:

$r_{dual} = \nabla f_0(x) + \sum \lambda_i \nabla f_i(x) + A^T \nu \quad (\ne 0)$
$r_{pri} = Ax - b \quad (\ne 0)$
$r_{cent} = - \text{diag}(\lambda) f(x) - (1/t) \mathbf{1} \quad (\ne 0)$

我们想找到一个“步长” $\Delta y = (\Delta x, \Delta \lambda, \Delta \nu)$, 使得我们的新点:

$(x+\Delta x, \lambda+\Delta \lambda, \nu+\Delta \nu)$ 更接近 0

(3) Newton法解巨型"KKT矩阵":

\[ \begin{bmatrix} \nabla^2 f_0(x) + \sum \lambda_i \nabla^2 f_i(x) & Df(x)^T & A^T \\ -\text{diag}(\lambda) Df(x) & -\text{diag}(f(x)) & 0 \\ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta \nu \end{bmatrix} = - \begin{bmatrix} r_{dual} \\ r_{cent} \\ r_{pri} \end{bmatrix} \]