====== 第十六课 ======
**最优化方法 4**

**内容
**非线性优化     

**主要参考书：
**最优化理论与方法，袁亚湘，孙文瑜，科学出版社

**1.插值法**
插值法是一类重要的搜索方法，其基本思想是:
在搜索区间中不断用低次(通常不超过三次)多项式来近似目标函数，并逐步用插值多项式的极小点来逼近一维搜索问题的极小点。当函数具有比较好的解析性质时，插值方法比直接方法(0.618法或Fibonacci法)效果更好。  

**1.1一点二次插值（牛顿法）**
利用一点处的函数值、一阶和二阶导数值构造二次插值函
数.迭代形式：{{:keynote:16-1.png|}}

  牛顿法的优点是收敛速度快，具有局部二阶收敛速度。
**1.2二点二次插值法
**
给出两点的函数值和其中一点的导数值，构造二次插值函
数。迭代形式为：{{:keynote:16-2.png|}}
   可证明二点二次插值法的收敛阶为1.618，超线性收敛。
**1.3三点二次法（抛物线法）**
{{:keynote:16-3.png|}}
   迭代时，从α1，α2，α3，α¯中选择目标函数最小的点及其左右两点，
进行下一步的迭代。
   超线性收敛，收敛阶近似为1.32。
**   1.4二点三次插值法**
用三次多项式来逼近。比二次插值法有较好的收敛效果，
但通常要求计算导数值，且计算量较大。一般当导数易求
时，用三次插值法较好。
{{:keynote:16-5.png|}}
   收敛速度为2阶，一般优于抛物线法。
**2.不精确的一维搜索方法**
  * 精确一维搜索往往需要花费很大的时间。* 
  当迭代点远离问题的解时，精确求解通常不十分有效。很多最优化方法，如牛顿法和拟牛顿法，其收敛速度并不依赖于精确一维搜索过程。
  * 只要保证目标函数有满意的下降，可大大节省计算量。* 
**2.1Armijo-Goldstein准则
**
{{:keynote:16-6.png|}}
**2.2Wolfe-Powell准则
** Armijo-Goldstein准则有可能把最优步长因子排除在可接受区间外，因此更改第二个条件为
{{:keynote:16-7.png|}}
**3.牛顿型方法**


**3.1最速下降法**
  * 以负梯度方向作为极小化算法的搜索方向
  * 具有总体收敛性
  * 最速下降方向仅是局部性质
        对于许多问题并非下降方向，而且下降非常缓慢。接近极小点时，步长越小前进越慢
  * 线性收敛
**3.2牛顿法**
  * 牛顿法的基本思想是利用目标函数的二次Taylor展开，并将其极小化。
{{:keynote:16-8.png|}}
  * 对于正定二次函数，一步即可得最优解。
  * 由于目标函数在极点附件近似于二次函数，故在初始点接近极小点时，牛顿法收敛速度较快。
  * 牛顿法具有局部收敛性，为二阶收敛。
**3.3改进牛顿法**
牛顿法的主要困难在于Hesse阵Gk不正定。这时二次型模型不一定有极小点，甚至没有平稳点。
Goldstein and Price (1967)当Gk非正定时，采用最速下降方向结合方向，给出

{{:keynote:16-9.png|}}
**3.3.1Goldfeld修正牛顿法**
{{:keynote:16-10.png|}}
**3.3.2Gill-Murray稳定牛顿法**
{{:keynote:16-11.png|}}
**3.3.3Levenberg-Marquardt方法
**
{{:keynote:16-12.png|}}
**3.3.4信赖域方法
**
  * 不仅可以用来代替一维搜索，而且也可以解决Hessen矩阵不正定等困难
  * 主要思想：首先选择一个步长r，使得在||x-xk||<r范围内(信赖域)；
  目标函数用n维二次模型来逼近，并以此选择一个搜索方向sk，取xk+1=xk+sk。

  * 具有牛顿法的快速局部收敛性，又具有理想的总体收敛性。
<note important> --- //[[you@zju.edu.cn|刘振广]] 2011/07/02 12:11//</note>