凸优化 IV · 内点法与半定规划
对标：Boyd & Vandenberghe §11 / Nesterov–Nemirovski（理论源头）｜ 前置：cvx-01–03、本科优化 IV、数值 II 凸优化收官：内点法——让"多项式时间解凸问题"成为定理的算法（本科优化 IV 提过名字，本页给机理与复杂度），及其最重要的应用疆域 SDP（半定规划：变量是矩阵的 LP，组合优化与控制论的瑞士军刀）。
1. 障碍法：把约束烧进目标
约束问题 \(\min f_0(x)\ \text{s.t.}\ f_i(x) \leq 0\)。对数障碍：
\(\phi\) 在边界处爆炸——迭代点被"电网"关在严格内部（名字的来历）。\(\{x^*(t): t > 0\}\) 称中心路径。
定理（中心路径的次优性）【证明】 \(f_0(x^*(t)) - p^* \leq \dfrac{m}{t}\)（\(m\) = 约束数）。 证：\(x^*(t)\) 的驻点条件 \(t\nabla f_0 + \sum\frac{-\nabla f_i}{-f_i} = 0\) 表明 \(\lambda_i(t) = \frac{1}{-t f_i(x^*(t))}\) 是对偶可行点，其对偶间隙 \(\sum\lambda_i(-f_i) = \frac mt\)——弱对偶收尾。\(\blacksquare\) 读法：中心路径是"带精度表的高速公路"——走到 \(t = m/\varepsilon\) 即达 \(\varepsilon\)-最优；障碍法 = 沿路开车（对递增的 \(t\) 序列各做几步 Newton——本科优化 II 的 Newton 法在此就业：障碍问题光滑无约束，正是它的主场）。
2. 自和谐：复杂度理论的钥匙
为什么 Newton 步数可以不依赖条件数地被控制？Nesterov–Nemirovski 的答案：
定义（自和谐函数） \(|f'''(x)| \leq 2f''(x)^{3/2}\)（多维沿每条直线）——"三阶导被二阶导自己控制"：Hessian 变化的速度以 Hessian 自身为尺度（仿射不变的光滑性——比 Lipschitz 梯度更适配 Newton 的几何）。\(-\ln\) 及对数障碍全家自和谐【验证一行：\((-\ln)''' = -2x^{-3}, (-\ln)'' = x^{-2}\)，恰取等】。
定理（路径跟踪复杂度）【引用】 自和谐障碍（参数 \(\nu\)；线性/二次约束的 \(\nu = m\)）的路径跟踪法达 \(\varepsilon\)-最优需
——多项式时间凸优化的正式定理（每次 Newton = 解一个线性系统，数值 II/III 的全部技术在内层服役）。工程事实：实践中几十次迭代解百万变量 LP/SOCP——"内点法迭代数几乎不随规模涨"的口碑之源；与单纯形法（顶点行走、最坏指数、实践极快）形成算法双雄（本科优化 IV 的预告闭环）。
3. 半定规划（SDP）
定义：变量为对称矩阵，约束"半正定"：
（\(\langle A, B\rangle = \mathrm{tr}(A^\top B)\)；半正定锥是凸锥——高代 VI 的判据划出的集合成为可行域。）LP 是对角矩阵特例；对数障碍 \(-\ln\det X\) 自和谐（\(\nu = n\)）⇒ 内点法通吃。对偶与 LP 平行（锥对偶：半正定锥自对偶【引用】）。
三大名应用（每个都值得知道机理）：
- Goemans–Williamson MaxCut【骨架】：把 \(x_i \in \{\pm1\}\) 松弛为单位向量（$X = $ Gram 矩阵 \(\succeq 0\)）解 SDP，随机超平面取整——期望 0.878 倍最优（比值 = \(\min\frac{\theta/\pi}{(1-\cos\theta)/2}\) 的一页微积分）：组合优化近似算法的巅峰之作，"松弛-取整"范式的旗舰；
- 控制论的 LMI：Lyapunov 不等式 \(A^\top P + PA \prec 0\)（ode-03 稳定性的矩阵版）是 SDP 可行性问题——"找 Lyapunov 函数"从艺术变成求解器调用；
- 多项式优化 / SOS：\(p(x) \geq 0\) 的"平方和证书"是 SDP——非凸多项式问题的凸层级逼近（Lasserre 层级【引用】）。
4. 凸优化四页收官盘点
| 页 | 资产 | 一句话 |
|---|---|---|
| I | 共轭 \(f^*\)、Fenchel 对偶 | 对偶的原子操作；四门课对偶的统一语法 |
| II | 势函数法、加速下界、prox | \(1/k^2\) 是一阶光速；不可微项交 prox |
| III | 增广拉格朗日、ADMM | 拆分 + 协调 = 大规模与分布式 |
| IV | 自和谐、内点法、SDP | 多项式时间的定理；矩阵变量的疆域 |
方法选型的现代地图：超大规模/低精度 → 一阶（II/III）；中规模/高精度/结构约束 → 内点（IV）；两界之间 → 混合（一阶热身 + 二阶精修）。
5. 练习与要点
例 1（中心路径亲算） \(\min x\ \text{s.t.}\ x \geq 0\)（一维 LP）：\(x^*(t) = \arg\min[tx - \ln x] = \frac1t\)——路径从内部滑向最优点 \(0\)，间隙恰 \(\frac1t = \frac mt\) ✓（定理在最小例子上的显影）。
例 2（LMI 上手） 判定 \(\dot x = Ax\)，\(A = \begin{pmatrix}-1 & 2\\ 0 & -3\end{pmatrix}\) 的稳定性：解 \(A^\top P + PA = -I\)（Lyapunov 方程，线性！）得 \(P \succ 0\) ⇒ 稳定——ode-03 的特征值判据与 SDP 路线双验证。
例 3（松弛-取整的体感） 三角形图 MaxCut：SDP 最优 = 2.25（向量排成 120°），随机超平面期望切 \(= 3\times\frac{120°}{180°}\cdot\frac{?}{}\)……亲手算这个三顶点例子（答案 2，比值 \(\frac{2}{2.25} \approx 0.889 > 0.878\) ✓）——GW 算法在最小非平凡图上走一遍。\(\blacksquare\)
下一门：数值线性代数——同样的矩阵问题，问"在浮点与有限步的现实里怎么算得又快又稳"。