不清楚 Lagrange 乘子法本质和对偶方法的请移步：https://kirigaya.cn/blog/article?seq=155
封面作者：Ar極光
一个约束优化问题（constraint optimization problem，简称 COP）往往被如下定义：
是优化的定义域 Domain
是等式约束 equality constraints
是不等式约束 inequality constraints
满足上述约束条件且在定义域的点被称为 可行点，所有可行点构成该优化问题的 可行域。
当前寻得的极值点记作 ，倘若对于满足
的所有
构成的集合称为激活不等式约束，所有 激活不等式约束 和 等式约束 的并集称为激活约束，记作
花写的 A，是 active inequality constraints 的第一个字母
显然，激活约束 是关于可行点而言的。
含不等式的 COP 仍然可以通过 Lagrange 进行求解： 其中
。化成 Lagrange 乘子法是需要满足一些条件的，这些针对
和
的条件统称为 KKT 条件：
- 平稳性（Stationarity）：
- 原问题可行性（Prime feasibility）：
- 对偶问题可行性（Dual feasibility）：
- 互补性（Complementary）：
满足 KKT 的点不一定是原问题的最小值点。
LICQ 是 线性无关约束条件（Linear independence constraint qualification）的简称。它是一个比 KKT 条件更强的条件，满足 KKT 的可行点不一定满足 LICQ 。
对于可行域中的一个点 ，如果它满足：
是线性无关的，那么就称
这个点 满足 LICQ 。
如果满足 Slater 条件，那么 满足 KKT 条件 对于凸优化（后面会讲）的最优点而言是充要条件。
对于可行域内的一个点 ，如果它满足如下条件，那么就称满足 Slater 条件：
Slater 条件对于 KKT 而言是一个很强的条件，在求解 Lagrange 时，非常容易把干到等于零。
Lagrange + 惩罚项：
如果只有等式约束： 如果含有不等式约束，引入互补松弛（Complementary Relaxation）变量
：
此时的 增广拉格朗日方法 写成：
ADMM (Boyd, Parikh, & Chu, 2011) 在解决如下形式的 COP 时有奇效： ADMM 会解决该问题的 增广拉格朗日问题：
ADMM 在第
轮，每次只优化问题一组变量，拿优化得到的极值点带入目标函数继续优化下一个变量，所有变量全部得到优化后，
轮才算结束：
.
.
其中 ，
时上述方法和增广拉格朗日一致。
收敛速率：未知。但是实验表明似乎是一次收敛。
设点集 ， 如果
和
，下式成立：
则称
是一个凸集。
如果点 可以写成有限个点的线性组合（在有限个点组成的单纯形开集内）：
其中
代表是单纯形。则称
是 点集
的凸组合。
设点集 ， 我们称
所有可能的凸组合构成的集合为 凸包，记作
.
- 凸包和凸集的区别：凸包是定义在
个点上的，凸集是定义在任意两个点上的
- 通过定义可以证明，凸包一定是凸集
是包含
的最小凸集
一个函数 被称为凸函数，需要满足两个条件：
的定义域
，下式成立：
假设我们现在有一个约束优化问题： 这个约束优化问题在满足如下两个条件的情况下被称为凸优化：
- 函数
- 每一个约束条件都是一个凸函数，这个条件等价于说集合
是凸集
凸优化隐含了许多的结论：
- 等式约束必然是仿射变换：对于约束条件
而言，如果
，显然，为了让
- 局部极小值为全局最小值
- Hessian 矩阵必然半正定（SPD）
详细博客：最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确线搜索（推导+程序）。
是当前这步的步长，确定方法为精准线搜索和非精准线搜索：
精准线搜索： 代价太大，一般不用。非精准线搜索有几个渐进式的经典方法。后面会讲。
在二次型上的最坏收敛速率： 一般情况下，梯度下降法收敛速率为线性（一次收敛速率）证明请移步 最优化方法复习笔记（二）梯度下降法的全局收敛与收敛速率。
详细博客：最优化方法复习笔记（三）牛顿法及其收敛性分析。 牛顿法局部收敛性（2018年证明）：
所以牛顿法靠近最优点时是二次收敛的，这与在数值分析中的结论一致。
没学过的同学可以在复习完后学习一下数值分析，对于计算机类的学生而言，数值分析还是很重要的一门课。不要牛顿法学完了，连怎么编程实现根号2的计算（只能用加减乘除）都不会
优点：
- 在最优点附近二次收敛，一般情形下收敛得也很快。
- 牛顿法具有仿射不变性，所以对坐标系的选择不敏感。
- 牛顿法不会随着问题维度的增大而大幅增加所需的迭代次数。
- 不需要通过线搜确定迭代更新的步长。
缺点：
- 无法保证 Hessian 矩阵是可逆的，同时也不能保证矩阵是正定的。
- 牛顿法得到的搜索方向不一定是下降的。
- 求 Hessian 矩阵的逆的时间复杂度太高了，时间复杂度为
- 存储 Hessian 矩阵非常消耗内存
详细博客：最优化方法复习笔记（四）拟牛顿法与SR1,DFP,BFGS三种拟牛顿算法的推导与代码实现。
SR1（全称 Symmetric Rank-One，William C. Davidon 1956）算法： DFP（Davidon, Fletcher, Powell 1959）算法：
BFGS（Broyden，Fletcher, Goldfarb, Shanno 1970）算法：
- SR1 是自对偶的
- DFP 和 BFGS 互为对偶
优点：
- 相比于牛顿法计算复杂度更低（不需要求逆）
- 拟牛顿法是
下的最速下降法，收敛速率是超线性的，证明看这篇文章：最优化方法复习笔记（五）拟牛顿法的收敛性分析
缺点：
- 仍然需要大量内存存储 Hessian 矩阵
- 得到的不一定是下降方向
- 拟牛顿产生的
往往是稠密的矩阵，但是真正的Hessian矩阵有可能是稀疏的。
详细博客：最优化方法复习笔记（六）共轭梯度法。
基于 Fletcher-Reeves 公式的共轭梯度法（FR-CG）： 在二次型下共轭梯度法的收敛速率为：
其中
为条件数。可以看出来，共轭梯度法是线性收敛的。而且在相同条件数下，比梯度下降法的速度快。
假设当前已经得到了一个下降方向 ，在不暴力求解的情况下如何获取一个合适的步长
来进行更新呢？下面的准则给出了判断一个步长
是“好步长”的条件。
直观理解：最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确线搜索（推导+程序）
下面三个方法的本质都是在建立曲线和直线的不等式，看一眼图并将式子化为 和它的导数的形式就能快速看懂。
缺点： 也满足 Armijo 准则，容易卡住不动。
缺点：会卡在局部极大值和鞍点上。
考虑 n 个样本 的优化问题。样本学习可以抽象成每一个样本对应于一个单独的学习器
，
对应样本，
对应学习参数。目标在于最小化所有学习器的平均值：
是从
中随机采样的数字，一般情况下，不放回抽样，服从均匀分布。
下面开始是在 torch 中常用的优化器合集。都是基于 SGD 开发的。
torch 中 optim.SGD 的实际实现方式。 其中
是从
中随机采样的数字，一般情况下，不放回抽样，服从均匀分布。
m 是 batch size 。当 ， MBGD=SGD，当
时， MBGD=GD
torch.optim.SGD 的 momentum 参数的实现，默认为 0。
带上历史信息，从而逃出局部最小值：
torch.optim.SGD 的 nesterov 参数的实现，默认为 False。
提前估计动量调转后的梯度，更加灵活地适应优化问题的几何特性，从而在某些情况下取得更快的收敛速度。
torch.optim.Adagrad 的实现。
通过引入衰减因子自动在优化后期减小学习率，从而收敛 优点：在 BP 的梯度比较稀疏（很多情况都是这样）时很管用。
缺点：容易提前收敛
torch.optim.RMSprop 的实现。
不对衰减因子进行梯度累计，因为容易提前中止，转而对衰减因子进行实时更新： 默认情况下
动量法和 RMSProp 的结合，torch.optim.Adam 的实现. 其中 m 是动量项， v 是衰减因子项，两者定义分别参考了 SGDM 和 RMSProp：
torch 中， 权重项的默认值为： .
