第 9–11 章 · 算法与落地（选读）

最后一段是"怎么算"：无约束的下降法（梯度、牛顿）、约束问题的等价求解（消元、罚、增广拉格朗日）与内点法的主线。理解算法的性格，才能选对工具。

无约束优化：梯度法与牛顿法

• 梯度下降 + 回溯线搜索：每步 $O(n)$，线性收敛（病态问题慢——条件数 $\kappa$ 出现在收敛率 $((\kappa-1)/(\kappa+1))^k$ 里）；
• 牛顿法：用二次模型 $\nabla^2 f\,\Delta x = -\nabla f$：二次收敛（几十步到机器精度），代价是海森 $O(n^3)$；阻尼牛顿（线搜索）保证全局收敛；自和谐（self-concordance）理论给内点法的步数与问题无关的界——牛顿法在凸世界的理论地位由它加固；
• 拟牛顿（BFGS）与 L-BFGS：免海森的超线性收敛——大规模无约束的主力。

等式约束与内点法

• 消元与对偶法处理等式约束；牛顿法推广到等式约束（KKT 系统求解）；
• 不等式约束的两条路：罚函数/障碍法（barrier：$-\sum\log(-f_i)$ 把可行域"围栏化"，随 $t$ 增大逼近解——中心路径）与原始-对偶内点法（同时更新原始与对偶变量，工程求解器的标准实现）；内点法的复杂度 $O(\sqrt m\log(1/\epsilon))$ 牛顿步——多项式时间的现实兑现；
• 数值纪律：KKT 系统的对称结构化求解、步长控制、退化与不可行检测。

应用地图与工程实践

• 机器学习：SVM（QP 对偶）、logistic 回归（凸光滑 + L-BFGS）、Lasso（$\ell_1$，次梯度/坐标下降/ADMM）、正则化路径；
• 信号与图像：压缩感知（$\ell_1$ 最小化恢复稀疏信号）、去噪（TV 正则）；
• 金融与控制：投资组合 QP、模型预测控制（MPC = 每步解一个 QP）；
• 建模层（CVXPY 等）与求解器层的分工：建模 DSL 做凸性检查与规范形，求解器（ECOS/MOSEK/SCS）做内点/一阶求解——现代凸优化的工程栈。

老师的提醒

• 求解凸问题的选型直觉：$n \lesssim 10^4$ 且要高精度 → 内点法；$n$ 巨大或在线场景 → 一阶/ADMM/坐标下降。
• 读解的自律：检查 KKT 残差（约束违反与平稳性）——求解器返回"已解"不等于数值上满足 KKT。

自检

• 梯度法收敛率与条件数的关系？
• 障碍法/内点法的中心路径是什么？
• Lasso 的模型与主流解法？

更深一层：内点法是"多项式时间的现实兑现"

内点法的历史意义值得理解：它把凸优化从"单纯形法的指数最坏情况"带入多项式时间（$O(\sqrt m\log(1/\epsilon))$ 牛顿步）——理论上的突破（Karmarkar 1984）+ 实践上的成功（与单纯形竞争并胜出大 problem）。中心路径（参数化障碍问题的解轨迹）是它的几何心脏：障碍函数 $-\sum\log(-f_i)$ 把可行域"围栏化"，参数 $t$ 增大时路径逼近解——路径跟随的每一步都是一次牛顿迭代。自和谐（self-concordance）理论给步数与问题无关的界——牛顿法在凸世界的理论地位由它加固。

推导细读：梯度法 vs 牛顿法的"病态敏感性"

梯度下降的病态敏感性值得用条件数量化：线性收敛率 $((\kappa-1)/(\kappa+1))^k$——$\kappa = 100$ 时每步只降 2%，椭圆等高线越扁（条件数大）梯度法越 zigzag。牛顿法用二次模型（曲率信息）一步对准——二次收敛（几十步到机器精度），代价是海森 $O(n^3)$。拟牛顿（BFGS/L-BFGS）免海森的超线性收敛——大规模无约束的主力。"用曲率信息换收敛速度"是优化算法的通用贸易——梯度法（零曲率、慢）、牛顿（全曲率、快但贵）、拟牛顿（近似曲率、折中）。

在真实世界里：凸优化的"工程栈"

现代凸优化的工程栈值得画清：建模层（CVXPY/CVX——建模 DSL 做凸性检查与规范形）、求解器层（ECOS/MOSEK/SCS——内点/一阶求解）、应用层（ML 的 SVM/Lasso、金融的组合优化、控制的 MPC）。建模 DSL 与求解器的分工是现代凸优化的工程美学——你只写"数学问题"，DSL 翻译成标准形，求解器执行。"凸优化的可及性"（从理论到 pip install）是它统治应用数学的直接原因——这本书教你识别凸问题，工具链帮你解它。

专题深入：无约束算法的"下降哲学"完整版

第九章-第十章的算法谱系按信息使用量分级：梯度下降（一阶信息 + 线搜索：最速下降的锯齿病（相邻方向正交、病态条件数下 zigzag——收敛率 $(\frac{\kappa - 1}{\kappa + 1})^2$ 由条件数 κ 决定——"病态问题惩罚一阶法"的定量出处）；牛顿法（二阶信息 + 二次模型：二次收敛（"位数翻倍"的收敛）但每步 $O(n^3)$ 与 Hessian 求解——"快但贵"的汇率；阻尼牛顿（线搜索保全局收敛）；拟牛顿（BFGS 用梯度差更新 Hessian 近似——"不用二阶导、逼近二阶效率"的折中，L-BFGS 的有限内存版是大规模问题的常青树）；自和谐理论（Nesterov/Nemirovski 的内点法复杂性理论——"自和谐函数上牛顿法有全局复杂度保证"是凸优化独有的算法学红利）。非导方法（Nelder-Mead、坐标下降的岗位：不可导目标与超大规模稀疏问题——坐标下降在 lasso 上的统治）。

推导细读：等式约束的牛顿与内点法完整版

第十章-第十一章的约束算法解剖：等式约束牛顿法（KKT 系统的牛顿步：$\begin{bmatrix}\nabla^2 f & A^T\\ A & 0\end{bmatrix}$ 的线性求解——消元/拉格朗日/Schur 补三种实现）；不等式的两难与内点法的破局（活动集法逐约束处理 vs 障碍法把不等式"软化"进目标：$\phi(x) = -(1/t)\sum\ln(-f_i(x))$——对数障碍的光滑逼近）；中心路径（$t \to \infty$ 时障碍解趋原最优——"沿中心路径走牛顿"：外层 t 几何增长 × 内层牛顿 5-10 步 = 多项式复杂度的实践胜利——"约束数一千的问题秒级求解"是 1990 年代内点法革命的战果）；原对偶内点法（对 (x, λ, ν) 三变量同时牛顿——Mehrotra 预测-校正是现代求解器（MOSEK/Gurobi/Clarabel）的标配内核）。收敛判据的工程语言（对偶间隙 $\|x - x^*\| \le$ 证书："解自带误差收据"是凸优化独有的售后服务）。

工程案例细节：求解器生态与"落地工艺"工程版

九-十一章的工程出口：求解器生态地图（开源：ECOS/Clarabel（内点）、OSQP（ADMM 的 QP 专精）、SCS；商用：MOSEK/Gurobi/CPLEX——选型表：问题族 × 规模 × 实时性；嵌入式 MPC 用 OSQP/qpOASES 的毫秒级 QP）；MPC 的实时化工艺（显式 MPC（参数化预解）、warm start（上一拍解作初值——轨迹平滑且迭代数骤降）、代码生成的求解器（CVXGEN/ FORCES——"为固定结构问题编译专用求解器"：火箭着陆（SpaceX 公开过凸引导 + NPSCP）与姿态控制）；大规模的一阶复兴（ADMM 的并行分解（"分而治之 + 对偶协调"：分布式统计学习、共识优化、电网分区调度）；FISTA 加速梯度在压缩感知的普及）；建模语言的工艺纪律（DCP 规则检查（CVXPY 编译期验证凸性——"写错凸性当场报错"的防呆设计）、问题缩放与数值检查清单）。第十一章的收束语：凸优化从"教科书数学"变成"基础设施"——每台手机、每条电网、每个投资组合的日常运算里都有内点法在走中心路径。