实用最优化 （二）

Convex optimization 算法一篇中，介绍了无约束，等式约束，约束最优化。Newton 方法占主要地位。

注意凸优化的标准形式中，等式约束是线性的，Ax=b

Newton 方法最先是用于无约束最优化。其一重要步骤是求 newton step，它可以理解为对目标函数做泰勒二次近似，然后求使得近似函数最小的增量，这个增量 v 是有解析解的。
Newton 方法可以推广到等式约束最优化，同样对目标函数做泰勒二次近似，然后求使得近似函数最小的可行增量v(即 x+v 为可行解). 同样的，这个增量也是有解析解的。



参考 p560，算法的层次
1. 等式约束二次问题，是有解析解的
2. 等式约束凸优化，是在每一点用二次近似，因此转化为一系列“等式约束二次问题”
3. 一般凸优化问题（不等式约束和等式约束） ，内点法是将问题转化为一系列“等式约束凸优化”

牛顿法步骤 p487
1. 需要梯度和Hessian。一般来说，梯度必须可以被 evaluate, 而 Hessian 如果不能被 evaluate 可以通过 Quasi-newton 方法来近似
2. Newton step
3. Newton decrement，用来作中止条件，以及用在 backtracking ( line search) 中，它是一个常量
4. line search: 可以用 backtracking


等式约束凸优化中牛顿法：
1. 算法描述同于无约束优化的牛顿法
2. 不同在于 newton step 和 newton decriment 的计算
3. 每一点都做二次近似，转化为等式约束二次问题，其解析解即为 newton step。