Notes for Numerical Optimization 2nd, Jorge Nocedal, Stephen J. Wright
Chapter 1, 2, 3, 14
Chapter 1 简介
连续vs离散：离散优化问题需要考虑完整性约束，未知的参数$x$取自有限（通常非常大）的集合，具有非凸性（任何两个可行点的凸组合不一定可行）；连续优化问题更容易解决，因为函数具有光滑性，可行集一般是不可数无限集。
有约束vs无约束：当目标函数和约束条件都是线性函数时，问题被称为线性规划问题。
全局vs局部：在凸规划（包含线性规划）中，局部解就是全局解。
随机vs确定：随机优化会用不确定性的概率来优化模型的预期表现。
凸性
凸集：凸集中任意两点连线上的每一点都属于这个集合，e.g. 单位球，多面体（用线性等式与不等式就可以定义）。
凸函数：函数域是凸集，并且对于任何两点$x, y\in S$, 下面的性质成立
e.g. $f(x)=c^Tx+\alpha, f(x)=x^THx$，其中$H$是对称半正定矩阵.
如果当$x \neq y,\forall \alpha \in (0,1)$时，不等式严格成立，则$f$是严格凸函数。如果$-f$是凸的，则$f$是凹的。
凸规划：满足下面条件的优化问题
目标函数是凸函数，
等式约束是线性函数，
不等式约束是凹的。
优化算法
优化算法是迭代的，从一个初始值开始，通过一系列改进，直到终止。终止的两种情况：
不能做出更多改进；
近似求得一个足够准确的解.
好的优化算法：robustness, efficiency, accuracy. 这些目标可能是矛盾的：
收敛速度和内存需求之间的矛盾
鲁棒性和速度之间的矛盾
Chapter 2 无约束优化
什么是解？
全局最小：在所有$x$中，$f(x^*)\leq f(x)$.
局部最小：在$x^*$的邻域中，$f(x^*) \leq f(x)$.
孤立局部最小：如果存在一个$x^*$的邻域，使得$x^*$是唯一的局部最小。
一阶必要条件
如果$x^*$是局部最小点，$f$在$x^*$的某个开邻域上连续可导，那么$\nabla f(x^*)=0$.
对于满足$\nabla f(x^*)=0$的点$x^*$，我们称为驻点。
二阶必要条件
如果$x^*$是局部最小点，并且$f$在$x^*$的某个开邻域上的二阶导存在并且连续（即光滑），那么$\nabla f(x^*)=0$，并且$\nabla^2 f(x^*)$半正定.
对于任何$p \neq 0$，如果矩阵$B$满足$p^TBp > 0$，我们称$B$正定；$p^TBp \geq 0$，我们称$B$半正定。
二阶充分条件
如果$f$在$x^*$的某个开邻域上的二阶导连续，并且$\nabla f(x^*)=0$，$\nabla^2 f(x^*)$正定，那么$x^*$是$f$的严格局部最小点.
定理
如果$f$是凸的，任何局部最小点$x^*$是全局最小点。在此之上，如果$f$可微，那么任何驻点$x^*$是全局最小点。
算法概述
线性搜索：选择某个方向，从当前迭代值出发，在这个方向上找到一个使得函数值更小的新的迭代值。步长可以用一维最小化方法来近似求解。
信赖域：建模函数$m_k$，在邻域中近似$f$，也就是求目标函数$\min \limits_{p}m_k(x_k+p)$，其中$x_k+p$在信赖域中。信赖域一般是一个球$||p||_2 \leq \Delta$，标量$\Delta > 0$被称为信赖域半径。$m_k$一般被定义成四元函数：$m_k(x_k+p)=f_k+p^T\nebla f_k+\frac{1}{2}p^TB_kp$，其中$\nebla f_k$是$f$的一阶导，矩阵$B_k$是Hessian $\nebla^2f_k$或它的近似。先选定一个candidate step $p_k$，然后找到某个最优方向；如果都不满足，再减小$p_k$。
这两种方法的差异：选定distance和direction的顺序不同。
线性搜索的方向：steepest descent direction，沿着梯度的反方向$p_k=-\nebla f_k$移动，但面对复杂问题时非常慢；Newton direction，当$\nebla^2 f_k$正定时，$p_k^N=-(\nebla^2 f_k)^{-1}\nebla f_k$，局部收敛更快，缺点是二阶导难以计算；Quasi-Newton是Newton方法的变种，不需要计算Hessian但收敛速率相似，用$B_k$代替$\nebla^2 f_k$，每一步之后更新$B_k$，实践中，许多方法更新的是$B_k^{-1}$。