高数基础---线搜索

高数基础---线搜索 1，无约束优化问题（unconstrained optimization）

无优化约束问题：即找函数在上的最小化的最优解，问题

（1）如果且，则为全局最优点---最小值点 （2）如果存在的一个邻域，使得且，则称为局部最优点---极小值点

Theorem.1：局部极小值点，一阶导为0

Theorem.2：，海瑟矩阵半正定（positive semidefinite）

Theorem.3：（二阶充分条件）若， is positive definite，则是局部极小值点---判断最优解的法则

Theorem.4：若为凸函数，则任意一个极小值点为全局极小值点

note：非凸函数---遗传算法/离子群算法（启发式方法，无理论）

期待跳出局部极值，达到全局极值

2，线搜索方法（line search） （1）概念：

构造一系列收敛序列收敛到最优点，每次对于当前的状态，选择优化方向，以及最优步长，最终使得 0}{min}f(x_{k}+alpha P_{k})" src="https://latex.codecogs.com/gif.latex?%5Cunderset%7B%5Calpha%20%3E%200%7D%7Bmin%7Df%28x_%7Bk%7D+%5Calpha%20P_%7Bk%7D%29" />

                                                                                                                                                                       

（2）方法：

在线搜索（line search）方法中，主要的迭代为

 

成功的线搜索方法取决于方向和步长（step length）的选择。

大多数线搜索算法中，要求是一个下降方向（descent direction），即（梯度与点积小于0），一般而言，要求线搜索的方向有下述形式

其中是一个对称正定的满秩矩阵（symmetric and nonsingulear），是梯度（梯度是上升最快的方向）

【1】steepest descent method：I（单位矩阵）   --- 最速下降法

【2】Newton's method：the exact Hessian   --- 海瑟矩阵估计法

【3】Quasi-Newton method：an approximation to the Hessian that is updated at every iteration by means of a low-rank formula. --- 拟牛顿法（为了避开海瑟矩阵求逆）

note：点积 ，正负取决于 ，的夹角（象限左边为负，右边为正）

          所以与梯度夹角以内为上升方向，与梯度夹角 90^{circ}" src="https://latex.codecogs.com/gif.latex?%3E%2090%5E%7B%5Ccirc%7D" />为下降方向

（3）线搜索步骤：

【1】计算搜索方向 from 

【2】确定为下降方向，

【3】确定步长0" src="https://latex.codecogs.com/gif.latex?%5Calpha_%7Bk%7D%3E0" />，

【4】computation of  is the linesearch -- may itself be an iteration

【5】generic linesearch method： 

3，置信域方法（trust region）

在附近构造一个模型函数（model function）作为在附近的一个估计，当然这个估计只能在局部是比较好的，然后我们去求解下述子问题

 where  lies in the trust region.

把函数分区，在每一区域用模型函数估计一个近似函数 --- 泰勒展开，海瑟矩阵