本笔记不关注证明过程P2无约束优化的基础_数值优化
本笔记不关注证明过程
P2 无约束优化的基础
从初始点一步一步到最优点：
终止条件：
全局收敛：起始点x0任意，收敛到x*
局部收敛：x0∈N(x*)，收敛到x*
线搜索方法：x0=xk，方向pk，步长αk，xk+1=xk+αkpk
选方向：
最速下降法：pk=-▽f(xk)
牛顿方向：pk=-▽^2 f(xk)^(-1)▽f(xk)
拟牛顿方向：pk=-Bk·▽f(xk)
共轭梯度法：
信赖域方法
在xk附近构造二次函数
P3 线搜索方法
φ(α) :=f(xk+αkpk)
方法：xk+1=xk+αkpk
最速下降：pk=-▽f(xk)
步长：αk=argmin φ(α) = argmin f(xk+αkpk)
wolfe条件是一种选取合适步长α的准则
保证下降得比较快
下图第二个不等式：忽略分母||pk||，左侧为曲线上任意一点与最左侧点连线的斜率，右侧为选定斜率，两斜率要满足不等式关系。
第一个不等式由第二个推导而来（个人猜测）。
下面右图中加粗的段就是满足wolfe条件的区域，
保证步长α不会太小，取值在蓝色区域
下图第一个式子表明曲线上任意点的斜率应大于某值，这就让α的取值在平移后的蓝色直线的右侧，保证了α不会太小。
第二个式子左侧应乘pk（应该是笔误了）
满足wolfe条件的α是存在的
此函数为关于α的函数φ。
P4 线搜索方法的收敛性和收敛速度
紫色区域比初始值小，其值f(x)称为下水平集
定理中的Σ<∞，也就是其中的每一项趋向于0
(L>0)
下图中λ为特征值，Κ为条件数
P5 算法收敛性
Zoutendijk定理加上以下条件，则拟牛顿法收敛。
因为当xk离x*比较远时：
二阶梯度有可能不正定，方向也就不一定是下降方向
αk不一定能满足wolfe条件
所以要对牛顿法进行修正
当上图中λi全为正，二阶梯度正定。
一般情况下不全为正，所以需要用其他矩阵来将λi变为正或者0
方法1，正数对应的位置为0，其他位置按λi'=ε-λi得出，但其中的矩阵不是对角阵。
方法2，把所有位置加上同一个λ，需要试探。
P6 正定矩阵的cholesky因子分解
信赖域方法在当前的迭代定义一个区域，在此区域内能够相信(trust)模型可以充分代表目标函数。然后选择步(step)作为当前区域的近似极小值点。
如下图所示，尽管用到了最优步长，（基于模型）由线搜索方法找到的极小值点只会使f减小很小的一部分；而由信赖域方法找到的步则可以造成f的大大减少。（越靠近中心越小）
算法4.1
下图中的mk是f在xk的二阶泰勒展开，通过最小化mk求得p，用相应的p作为步迭代f。
ρ的分母一定是非负的。
根据ρ来选择信赖域范围Δk和xk
P7 基于Cauchy点的方法
||p(τ)||是τ的上升函数
m(p(τ))是τ的下降函数
引理4.3
P17 最小二乘方问题
数值优化 复旦大学吴立德教授