凸优化深度指南

文档概述

凸优化是现代机器学习与统计推断的理论支柱。本指南系统介绍凸集与凸函数的基本理论、典型优化问题（LP、QP、SOCP、SDP）、对偶理论与KKT条件、梯度下降法及其收敛性分析、投影方法与约束处理、以及各类一阶二阶优化方法的深入讨论。附录包含变分不等式、分散式优化、凸优化的计算复杂性等高级专题。

---

零、凸优化入门：为什么”凸”如此重要？

0.1 一个故事：从爬山说起

想象你在爬山，想找一座山的最低点。你站在山坡上，四周都是雾，什么也看不清。你能做的，就是用手摸一摸脚下，感受坡度往哪个方向倾斜，然后往那个方向走一小步。

这个”感受坡度、往下走”的过程，就是梯度下降的基本思想——优化算法的老祖宗。

但问题来了：如果这座山有很多山谷，你怎么能保证自己走到的是最低的那座山谷，而不是被困在半山腰的小坑里？

这就是”凸优化”登场的原因。凸函数的山只有一座山谷，不管你怎么走，最后都会到达同一个最低点。这听起来很简单，但它的意义重大：在凸优化里，找局部最优就等于找全局最优，不需要担心被困在某个山坳里出不来。

0.2 凸优化为什么是ML的基础？

搞机器学习的人天天跟凸优化打交道，不是因为ML的问题都是凸的，恰恰相反——神经网络本质上是非凸的。那为什么要学凸优化？

原因有三个：

第一，ML的很多核心问题确实是凸的。 SVM、Logistic回归、线性回归、LASSO——这些你天天用的算法，底层的优化问题都是凸的。你不理解凸优化，就不理解为什么这些算法理论上”保证”能work。

第二，凸优化是理解非凸优化的起点。 神经网络虽然是非凸的，但理解它的训练过程需要凸优化的直觉。为什么SGD能收敛？学习率怎么调？为什么有时候会发散？这些问题在凸优化的框架下更容易理解。

第三，凸优化给了我们理论保证的”锚点”。 当我们分析一个非凸问题时，经常会先问：如果这个问题是凸的，结果会是什么？然后再考虑非凸性带来的额外复杂性。

所以，凸优化不是ML的终点，而是起点。

---

一、凸集直观理解：圆形、立方体、椭圆——什么样的集合是凸的？

1.1 凸集的几何直觉

凸集的定义很简单：集合里任意两点，用直尺连起来，整条线段都在集合内。

这个定义看起来平平无奇，但它背后的几何直觉非常强大。

拿一个圆形打比方。圆盘是凸的，因为你在圆盘里随便找两个点，连接它们的线段永远不会”跑出去”。但一个圆环（甜甜圈形状）就不是凸的——你从外圈选一个点、内圈选一个点，连接它们的线段会穿过中间的空洞。

立方体呢？当然是凸的。三角形？凸的。椭圆？凸的。任何”实心”的、没有”洞”和”凹进去”的部分的形状，都是凸的。

有个更数学的定义：

凸集：集合 $C\subseteq {\mathbb{R}}^n$ 是凸的，当且仅当对任意 $x,y\in C$ 和 $\theta \in [0,1]$，有： $\theta x+(1-\theta )y\in C$

这里的 $\theta x+(1-\theta )y$ 就是 $x$ 和 $y$ 的凸组合——按比例 $\theta$ 和 $1-\theta$ 加权平均。$\theta =0.5$ 时就是中点，$\theta =0$ 时就是 $y$，$\theta =1$ 时就是 $x$。

1.2 常见的凸集有哪些？

搞ML的人要认识下面这些”常客”：

超平面：$\{x:a^{T}x=b\}$，可以理解为 $n$ 维空间里的”平板”，维数比空间低1。比如在3D里，$a_1{x}_1+a_2{x}_2+a_3{x}_3=b$ 就是一个平面。

半空间：$\{x:a^{T}x\le b\}$，就是超平面”切一刀”后的一边。半空间是凸的，这个要记住。

多面体：有限个半空间和超平面的交集。听不懂没关系，你把它想象成一个被很多刀切出来的多面体就行。比如立方体就是6个平面的交集。多面体是凸的——这个结论非常有用。

范数球：$\{x:\Vert x\Vert \le 1\}$，不管你用 $L_1$ 范数、$L_2$ 范数还是 $L_{\infty }$ 范数，球都是凸的。

概率单纯形：${\Delta }_n=\{x\in {\mathbb{R}}_{+}^n:{\sum }_i{x}_i=1\}$。这就是所有概率分布的集合，每个分量代表一个事件的概率，非负且加起来等于1。

正定锥：${\mathbb{S}}_{+}^n=\{X\in {\mathbb{R}}^{n\times n}:X=X^T,X⪰0\}$，所有半正定矩阵的集合。这个在协方差矩阵、最小二乘、PCA里经常出现。

1.3 凸集有哪些运算规律？

记住这几个就够了：

• 交集：凸集和凸集相交，还是凸集。比如多面体就是无数半空间的交集。
• 仿射变换：把凸集拉伸、压缩、平移、旋转（仿射变换），凸性不变。
• 直积：两个凸集的”乘积”还是凸的。

1.4 分离定理：一个深刻的几何结论

如果两个凸集不相交，那么一定存在一张”超平面”把它们分开，就像两张纸之间可以塞进去一张透明的薄片。

这个分离定理听起来简单，但它是对偶理论、KKT条件、SVM的支撑向量理论的基础。后面讲对偶的时候会再遇到它。

---

二、凸函数：为什么碗形函数容易优化？

2.1 从几何上理解凸函数

如果说凸集是”实心的”形状，那凸函数就是”碗形的”函数。

凸函数的定义：对函数上任意两点，连线永远在函数图像上方。用数学话说：

$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$

左边是函数在凸组合处的值，右边是函数值的凸组合。连线在上，意味着函数图像是”向上弯”的。

二次函数 $f(x)=x^2$ 就是一个标准的凸函数。你想象一个碗，底部是最低点，两边往上翘。

指数函数 $e^x$ 是凸的。对数函数 $\log x$ 在正数区间是凹的（向下弯）。

2.2 凸函数为什么好优化？

凸函数有一个全局最优性的保证：局部最优就是全局最优。

这句话是凸优化最核心的性质。普通函数可能有多个局部最优，比如正弦函数 $y=\sin (x)$，有无数个波峰和波谷，找到一个局部最优不等于找到全局最优。

但凸函数没有这个问题。在凸函数里，每一个局部最小点都是全局最小点——因为它只有一个”山谷”。

这也是为什么我们学凸优化的原因：有了凸性，优化变得”安全”了。

2.3 凸函数判定：二阶条件与Jensen不等式

怎么判断一个函数是不是凸的？

二阶条件：如果函数二阶可微，那么凸的充要条件是Hessian矩阵半正定：

${\nabla }^{2}f(x)⪰0,\forall x\in \text{dom}(f)$

“半正定”是什么意思？简单说，就是Hessian矩阵的所有特征值都大于等于零。这意味着函数在各个方向上的曲率都是非负的——函数图形处处向上弯曲。

Jensen不等式：这是凸函数的期望形式，也是很多”加权平均”不等式的源头：

$\varphi (\mathbb{E}[X])\le \mathbb{E}[\varphi (X)]$

其中 $\varphi$ 是凸函数。这个不等式有个经典推论：AM-GM不等式（算术平均大于等于几何平均）。你可以试试把 $\varphi (x)=-\log x$ 代入。

---

三、典型优化问题

3.1 线性规划（LP）

线性规划是凸优化里最简单、最经典的问题形式：

$\min c^{T}x$ $\text{s.t.}Ax=b,x\ge 0$

目标函数是线性的，约束也是线性的。

线性规划的应用场景太多了：运输问题（怎么把货物从仓库运到商店成本最低）、资源分配（怎么分配有限的工人完成多项任务）、食谱优化（怎么用最低成本满足营养需求）……

3.2 二次规划（QP）

如果目标函数是二次的，约束是线性的，就是二次规划：

${\min }_x\frac{1}{2}{x}^{T}Qx+c^{T}x$ $\text{s.t.}Ax\le b$

当 $Q$ 是半正定矩阵时，问题就是凸的。

最小二乘回归就是QP的特殊形式：

${\min }_x\Vert Ax-b{\Vert }^2+\lambda \Vert x{\Vert }^2$

这就是带正则化的线性回归。展开后你会发现 $Q=2(A^{T}A+\lambda I)$，是半正定的，所以问题是凸的。

3.3 二阶锥规划（SOCP）

SOCP是LP和QP的推广，约束形式是：

$\Vert A_{i}x+b_i{\Vert }_2\le c_i^{T}x+d_i$

听起来复杂，但它是鲁棒优化的标准形式。金融里的投资组合优化、天线阵列设计、滤波器设计都用得上。

3.4 半定规划（SDP）

SDP把向量换成了矩阵，是最”高级”的锥规划：

${\min }_{X⪰0}C\bullet X$ $\text{s.t.}{A}_i\bullet X=b_i$

SDP的应用包括：MAX-CUT问题的近似算法（Goemans-Williamson算法）、控制理论里的LMI问题、传感器网络定位等。

---

四、梯度下降：最朴素的优化方法

4.1 梯度下降的直观理解

回到爬山的例子。你站在山坡上，想往低处走。最直接的方法就是看脚下最陡的方向——这就是梯度。梯度指向函数上升最快的方向，所以往梯度的反方向走，就是下坡最快的方向。

梯度下降的迭代公式：

$x_{k+1}=x_k-{\eta }_k\nabla f(x_k)$

这里 ${\eta }_k$ 是步长（学习率），$\nabla f(x_k)$ 是梯度。

4.2 步长选择：走快了会摔，走慢了浪费时间

步长 $\eta$ 的选择是个技术活。

太大了会”越过”最低点，甚至发散；太小了收敛极慢。

固定步长：对于Lipschitz连续的梯度，步长 $\eta \le 1/L$ 可以保证收敛（$L$ 是梯度Lipschitz常数）。

线搜索：动态调整步长。Armijo线搜索从大步长开始，如果步子迈得太大（函数值没下降）就缩小步长。

4.3 收敛速度：凸vs强凸

梯度下降的收敛速度取决于函数的”难度”：

一般凸函数：收敛率 $O(1/\sqrt{k})$。精度从 $ϵ$ 提高到 $ϵ/2$，需要4倍的迭代次数。

强凸函数：收敛率 $O((1-\mu /L{)}^k)$，这是线性收敛——每一步误差乘以一个常数因子。这意味着达到 $ϵ$ 精度只需要 $O(\log (1/ϵ))$ 次迭代。

“强凸”是什么意思？简单说，就是函数底部不是平的，而是有”二次下界”的。强凸性保证了梯度下降有明确的”归宿”——越接近最低点，梯度越小，但曲率帮助你更快收敛。

4.4 收敛率一览

函数类型	收敛率	达到 $ϵ$ 精度需要
一般凸+Lipschitz	$O(1/\sqrt{k})$	$O(1/{ϵ}^2)$ 次迭代
强凸+平滑	$O((1-\mu /L{)}^k)$	$O(\kappa \log (1/ϵ))$
强凸+平滑+加速	$O(1/k^2)$	$O(1/\sqrt{ϵ})$

---

五、动量梯度下降：为什么惯性能加速收敛？

5.1 动量：从物理世界借来的思想

想象一个球从山坡滚下。普通梯度下降就像”点一下走一步”——你给一个力，球动一下，再给一个力，再动一下。

但真实的物理世界有惯性。球会记住之前的运动方向，积累动量，往一个方向滚得越来越快。

动量法就是这个思想：

$v_{k+1}=\beta v_k+\nabla f(x_k)$ $x_{k+1}=x_k-\eta v_{k+1}$

$v_k$ 是”速度”，$\beta$ 是动量系数（通常取0.9）。梯度不再直接更新位置，而是更新速度，速度再更新位置。这相当于对历史梯度做了指数加权平均。

5.2 动量为什么有效？

动量能抑制震荡、加速收敛。

在高曲率方向（函数变化剧烈），梯度时正时负，动量会让这些波动相互抵消。在低曲率方向（函数变化平缓），梯度方向一致，动量会让速度累积，走得更快。

简单说：动量帮你”顺着”一致的趋势走，忽略”噪声”。

5.3 Nesterov加速：看得更远的智慧

Nesterov动量更进一步——先看一步再决定。

普通动量：先算梯度，然后更新速度。

Nesterov动量：先借助动量”预测”未来位置，在那个位置算梯度，再更新速度。

$v_{k+1}=\beta v_k+\nabla f(x_k-\eta \beta v_k)$ $x_{k+1}=x_k-\eta v_{k+1}$

这个”提前看”的思想带来了更好的收敛率：

• 一般凸函数：从 $O(1/k)$ 提升到 $O(1/k^2)$
• 强凸函数：从 $O((1-1/\kappa {)}^k)$ 提升到 $O((1-1/\sqrt{\kappa }{)}^k)$

Nesterov加速梯度（NAG）是最优一阶方法——在只用梯度信息的算法里，它是最快的。

---

六、牛顿法：二阶信息如何加速？

6.1 梯度下降的问题

梯度下降只看当前坡度，不知道”弯得多厉害”。

如果函数很”窄”（Hessian条件数大），梯度下降会”锯齿”前进——虽然方向没错，但要走很多步才能到达最低点。

6.2 牛顿法的思路

牛顿法用二阶信息——Hessian矩阵——来修正方向：

$x_{k+1}=x_k-({\nabla }^{2}f(x_k){)}^{-1}\nabla f(x_k)$

几何直观：把函数在当前点做二阶泰勒展开（用Hessian捕捉曲率），然后跳到那个二次近似的最低点。

6.3 牛顿法的收敛速度

对于强凸函数，牛顿法是二次收敛的——每一步有效数字位数大约翻倍。这个速度比梯度下降的线性收敛快得多。

但牛顿法有三个问题：

1. 计算贵：需要求Hessian的逆，$O(n^3)$
2. 存储难：Hessian是 $n\times n$ 矩阵，$n$ 大时存不下
3. 可能不正定：对于非凸问题，Hessian可能有负特征值

6.4 拟牛顿法：省钱的替代方案

BFGS和L-BFGS是一类”不直接算Hessian但能近似它”的方法。

BFGS通过对梯度差的观测，逐步构建Hessian的近似。L-BFGS（Limited-memory BFGS）只存储最近几步的梯度差，把存储从 $O(n^2)$ 降到 $O(mn)$，其中 $m$ 是内存中存储的步数（通常10-20）。

---

七、共轭梯度法：为什么比普通梯度下降更快？

7.1 共轭是什么？

“共轭”听起来吓人，但概念不复杂。在欧氏空间里，两个方向 $p$ 和 $q$ 关于正定矩阵 $A$ 共轭，意思是 $p^{T}Aq=0$。

共轭可以理解为”在某种意义下正交”。普通正交是在单位矩阵意义下，共轭是在 $A$ 意义下。

7.2 共轭梯度法的妙处

共轭梯度法（CG）能在 $n$ 步内精确求解 $n$ 维正定二次函数的最小化问题。这叫”$n$ 步收敛”。

对于一般凸函数，CG会迭代收敛，但理论上也能比普通梯度下降更快。

CG不需要存储完整的Hessian，只需要能计算Hessian-vector积 ${\nabla }^{2}f(x)v$。这对于大规模问题非常重要——你不需要构造 $n\times n$ 的矩阵，只需要能算它和向量的乘积就行。

7.3 Hessian-free优化：深度学习的标配

深度学习里计算完整Hessian是不可能的，但可以用Hessian-free方法：用共轭梯度法求解牛顿步长，只算Hessian-vector积，不显式构造Hessian。

---

八、约束优化：拉格朗日乘子与KKT条件

8.1 为什么约束优化更复杂？

无约束优化：你随便走，只要往低处走就行。

有约束优化：你只能在某个”允许的区域”里走，不能越过边界。

约束把问题变得更复杂，但很多实际问题都有约束——SVM里间隔不能小于1，投资组合里权重不能为负。

8.2 拉格朗日函数：把约束”吸”进来

考虑标准优化问题：

${\min }_x{f}_0(x)$ $\text{s.t.}{f}_i(x)\le 0,i=1,\dots ,m$ $h_j(x)=0,j=1,\dots ,p$

拉格朗日函数：

$L(x,\lambda ,\nu )=f_0(x)+{\sum }_{i=1}^m{\lambda }_i{f}_i(x)+{\sum }_{j=1}^p{\nu }_j{h}_j(x)$

约束被”乘上”拉格朗日乘子，加到了目标函数里。如果约束被满足，拉格朗日函数等于原目标函数；如果约束被违反，拉格朗日函数会”惩罚”你。

8.3 KKT条件：最优解必须满足的方程组

对于凸优化，在一定条件下（Slater条件），$x^{\ast }$ 是最优解的充要条件是存在乘子 ${\lambda }^{\ast },{\nu }^{\ast }$ 使得：

1. 原始可行性：$f_i(x^{\ast })\le 0$，$h_j(x^{\ast })=0$
2. 对偶可行性：${\lambda }_i^{\ast }\ge 0$
3. 互补松弛：${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$
4. 拉格朗日平稳性：$\nabla f_0(x^{\ast })+{\sum }_i{\lambda }_i^{\ast }\nabla f_i(x^{\ast })+{\sum }_j{\nu }_j^{\ast }\nabla h_j(x^{\ast })=0$

互补松弛 ${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$ 很有趣：如果约束 $f_i$ 在解处不活跃（$f_i(x^{\ast })<0$），乘子 ${\lambda }_i^{\ast }$ 必须为零；如果乘子 ${\lambda }_i^{\ast }>0$，约束必须在边界处（$f_i(x^{\ast })=0$）。

这意味着：只有”绑住”你的约束才需要付”代价”（非零乘子）。

---

九、内点法：从屏障函数到现代优化器

9.1 外罚函数法的局限

传统的惩罚函数方法把约束放到目标函数里，但会导致病态条件数——越接近约束边界，函数变化越剧烈，数值不稳定。

9.2 障碍函数法：待在可行域内部

内点法（也叫障碍函数法）反其道而行之：在可行域内部走，用一个”障碍函数”惩罚接近边界的趋势。

对数障碍函数：

$\varphi (x)=-\frac{1}{t}{\sum }_i\log (-f_i(x))$

当 $x$ 接近约束边界时，$-f_i(x)\to 0$，$\log (-f_i(x))\to -\infty$，$\varphi (x)\to +\infty$。这就像在边界处立了一堵隐形的墙。

把障碍函数加到目标函数里：

${\min }_x{f}_0(x)-\frac{1}{t}{\sum }_i\log (-f_i(x))$

9.3 中心路径：从可行到最优

随着参数 $t$ 增大，障碍问题的解会沿着一条叫中心路径的曲线，从可行域内部逐步逼近原问题的最优解。

原始-对偶内点法同时追踪原始变量和对偶变量，通过牛顿法沿中心路径迭代，是现代LP/QP/SDP求解器的核心算法。

---

十、SVM与凸优化：对偶问题与支持向量

10.1 SVM原问题

支持向量机的目标是找到一个超平面，使得两个类别的间隔最大：

${\min }_{w,b}\frac{1}{2}\Vert w{\Vert }^2$ $\text{s.t.}{y}_i(w^T{x}_i+b)\ge 1$

这是一个凸二次规划——目标函数是二次的（且正定），约束是线性的。

10.2 SVM对偶问题

通过拉格朗日对偶，可以得到对偶形式：

${\max }_{\alpha }{\sum }_i{\alpha }_i-\frac{1}{2}{\alpha }^{T}YX{X}^{T}Y\alpha$ $\text{s.t.}{\alpha }_i\ge 0,{\sum }_i{\alpha }_i{y}_i=0$

这里 $Y$ 是标签对角矩阵，$X$ 是数据矩阵。

10.3 支持向量的几何意义

KKT条件里的互补松弛 ${\alpha }_i(y_i(w^T{x}_i+b)-1)=0$ 告诉我们：

• 如果 ${\alpha }_i>0$，这个样本是支持向量——它恰好落在间隔边界上
• 如果 ${\alpha }_i=0$，这个样本对分类超平面没有贡献

支持向量机的”稀疏性”就从这里来：训练完成后，只需要保留支持向量就可以表示分类器。这让SVM在高维数据上依然高效。

---

十一、Logistic回归与交叉熵：凸优化的典型应用

11.1 Logistic回归

Logistic回归是二分类问题：

$P(y=1|x)=\sigma (w^{T}x),\sigma (z)=\frac{1}{1+e^{-z}}$

对数似然函数（负损失）为：

$\ell (w)={\sum }_i[y_i\log \sigma (w^T{x}_i)+(1-y_i)\log (1-\sigma (w^T{x}_i))]$

加上 $L_2$ 正则化：

${\min }_w-\ell (w)+\frac{\lambda }{2}\Vert w{\Vert }^2$

11.2 为什么Logistic回归是凸的？

目标函数是负对数似然 + 正则项。负对数似然（交叉熵损失）是凸的，$L_2$ 正则项也是凸的，两者相加还是凸的。

所以Logistic回归保证能收敛到全局最优。

11.3 交叉熵的凸性

Logistic回归的损失函数可以写成：

$f(w)={\sum }_i\log (1+\exp (-y_i{w}^T{x}_i))$

这个函数的Hessian是：

${\nabla }^{2}f(w)={\sum }_i{\sigma }_i(1-{\sigma }_i)x_i{x}_i^T$

其中 ${\sigma }_i=\sigma (y_i{w}^T{x}_i)\in (0,1)$。因为 ${\sigma }_i(1-{\sigma }_i)>0$，所以 Hessian 是半正定的——函数是凸的。

---

十二、神经网络是非凸的：为什么仍然能work？

12.1 神经网络为什么是非凸的？

神经网络有大量的参数（权重和偏置），损失函数是这些参数的高维非凸函数。比如两层网络：

$f(x)=W_2\sigma (W_{1}x+b_1)+b_2$

展开后是高度非线性的组合，Hessian矩阵既有正特征值也有负特征值。

12.2 非凸优化的挑战

非凸函数有多个局部最优、鞍点、甚至高原区域。

理论上，找到神经网络的全局最优解是NP-hard的。

12.3 为什么实践中神经网络能work？

过参数化的奇迹：当神经网络的宽度足够大（参数量远大于样本数）时，梯度下降可以收敛到全局最优或接近全局最优。Allen-Zhu、Song等人的理论工作证明了这一点。

损失 landscape 的”好消息”：在高维空间里，局部最优和全局最优的差距可能没有想象中那么大。随机矩阵理论预测，大部分局部最优都在全局最优的某个邻域内。

SGD的隐式正则化：随机梯度下降的噪声有隐式的”平滑”效果，帮助逃离鞍点和较差的局部最优。

大量局部最优其实差不多好：实践表明，对于同一个数据集，不同的局部最优在测试集上的性能往往相近。这叫”flat minima泛化好”的现象。

---

十三、动手实验：用scipy.optimize解决实际优化问题

13.1 最小二乘回归

import numpy as np
from scipy.optimize import minimize
 
# 生成数据
np.random.seed(42)
n, d = 100, 10
X = np.random.randn(n, d)
w_true = np.random.randn(d)
y = X @ w_true + 0.1 * np.random.randn(n)
 
# 定义目标函数: ||Xw - y||^2
def objective(w):
    residual = X @ w - y
    return np.sum(residual ** 2)
 
# 初始点
w0 = np.zeros(d)
 
# 无约束优化
result = minimize(objective, w0, method='BFGS')
print(f"BFGS解的误差: {np.linalg.norm(result.x - w_true):.4f}")

13.2 约束优化：SVM的对偶问题

from scipy.optimize import minimize
 
# SVM对偶问题
def svm_dual(alpha):
    # alpha是拉格朗日乘子向量
    K = X @ X.T  # 核矩阵
    return 0.5 * alpha @ K @ alpha - np.sum(alpha)
 
# 约束: alpha_i >= 0, sum(alpha_i * y_i) = 0
constraints = {'type': 'eq', 'fun': lambda a: a @ y}
bounds = [(0, None) for _ in range(n)]
 
result = minimize(svm_dual, np.zeros(n), method='SLSQP',
                  bounds=bounds, constraints=constraints)

13.3 使用scipy.optimize做凸优化的教学示例

from scipy.optimize import minimize, rosen, rosen_der, rosen_hess
 
# Rosenbrock函数（经典的非凸测试函数）
# 全局最优在(1,1)，值为0
x0 = [0.0, 0.0]
 
# 梯度下降
res_gd = minimize(rosen, x0, method='BFGS', jac=rosen_der)
 
# 牛顿法（需要Hessian）
res_nt = minimize(rosen, x0, method='Newton-CG', jac=rosen_der, hess=rosen_hess)
 
# 比较收敛速度
print(f"BFGS迭代次数: {res_gd.nit}")
print(f"Newton-CG迭代次数: {res_nt.nit}")

---

十四、关键词速查表

序号	关键词	英文	核心概念
1	凸集	Convex Set	$\forall x,y\in C,\theta \in [0,1]:\theta x+(1-\theta )y\in C$
2	凸函数	Convex Function	$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$
3	线性规划	Linear Programming	$\min c^{T}x\text{ s.t. }Ax\le b$
4	二次规划	Quadratic Programming	$\min \frac{1}{2}{x}^{T}Qx+c^{T}x\text{ s.t. }Ax\le b$
5	KKT条件	Karush-Kuhn-Tucker	最优性的必要条件
6	对偶问题	Dual Problem	原问题的下界优化
7	梯度下降	Gradient Descent	$x_{k+1}=x_k-\eta \nabla f(x_k)$
8	收敛率	Convergence Rate	$O(1/k),O(1/k^2),\exp (-k)$
9	Lipschitz连续	Lipschitz Continuity	$\Vert f(x)-f(y)\Vert \le L\Vert x-y\Vert$
10	强凸	Strong Convexity	$f(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ 凸

---

十五、算法选择指南

15.1 按问题类型选算法

场景	推荐算法
小规模光滑无约束	牛顿法、BFGS、L-BFGS
中等规模凸问题	内点法、SCS、OSQP
大规模光滑无约束	L-BFGS、Nesterov 加速梯度
大规模稀疏约束	Frank-Wolfe、随机方法
包含 $L_1$ 正则	ISTA/FISTA、近端梯度法
分布式/联邦学习	ADMM
实时控制	定制内点法、fast MPC
黑盒/仿真优化	零阶方法、贝叶斯优化

15.2 Python工具生态

CVXPY：最推荐的凸优化建模工具，写起来像数学公式：

import cvxpy as cp
 
x = cp.Variable(n)
objective = cp.Minimize(cp.norm(A @ x - b, 2))
constraints = [x >= 0, cp.sum(x) == 1]
prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.SCS)

scipy.optimize：通用优化，小问题够用。

osqp：专门做QP的一阶求解器，MPC里用得多。

mosek/gurobipy：商业求解器，大规模问题首选。

---

十六、历史注记与延伸阅读

16.1 发展简史

• 1947：Dantzig 提出单纯形法，线性规划进入可计算时代
• 1967：KKT 条件正式提出（但 Karush 1939 年就在论文里给出了）
• 1979：Khachiyan 的椭球法首次证明 LP 是多项式时间可解的
• 1984：Karmarkar 的内点法引爆了这个领域
• 1988：Nesterov 提出加速梯度法，达到最优 $O(1/k^2)$
• 1990s：二阶锥规划和半定规划的内点法成熟
• 2000s：一阶方法成为大规模机器学习的主流
• 2010s：Adam 等自适应方法横扫深度学习

16.2 经典教材

1. Boyd & Vandenberghe (2004): Convex Optimization. 入门必读，配套公开课质量极高
2. Nesterov (2018): Lectures on Convex Optimization. 理论最深，最优算法设计的权威
3. Nocedal & Wright (2006): Numerical Optimization. 数值优化的工程视角

---

参考文献

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Nesterov, Y. (2018). Lectures on Convex Optimization (2nd ed.). Springer.
3. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
4. Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2), 223-311.
5. Allen-Zhu, Z., Li, Y., & Song, Z. (2019). A Convergence Theory for Deep Learning via Over-Parameterization. ICML.

---

相关文档

• 线性代数深度指南 - 矩阵分解在优化中的应用
• 统计学深度指南 - MLE的优化视角与EM算法
• 概率论深度指南 - 随机优化与浓度不等式