ch05常用无约束最优化方法

1、第5章 常用无约束最优化方法 15.1 无约束问题的最优性条件 考察最优化问题 (5.1) 其中f(x)是定义在Rn中的实函数, 最优化问题(5.1)是求函数f(x)在Rn中的极小值点。称之为无约束最优化问题(Unconstrained Optimization)。当n=1时, (5.1)就是一元函数的极小值问题； 当n1时, (5.1)就是多元函数的极小值问题。 2定理5.1 设f(x)可微，若向量p在x(k)处满足则p是f(x)在x(k)处的下降方向。 3定理5.2(一阶必要条件) 设f(x)在x*的某个邻域内具有连续的偏导数, 则x*是f(x)的局部极小值点(Local minimum)

2、的必要条件是 定理5.3(二阶必要条件) 设f(x)在x*的某个邻域内具有连续的二阶偏导数, 则x*是f(x) 的局部极小值点的必要条件是 且 半正定 定理5.4(二阶充分条件) 设f(x)在x*的某个邻域内具有连续的二阶偏导数, 若 且 正定, 则x*是f(x)的严格局部极小点(Isolated local minimum)。 4定理5.5 设f(x)在x*的某个邻域 内具有连续的二阶偏导数, 若 且 半正定, 则x*是f(x)的局部极小点。定理5.6 设f(x)是Rn上的凸函数且f(x)具有连续的偏导数, 则x*是f(x)的全局极小点(Global minimum)的充分必要条件是 例5.

3、1 利用一阶和二阶条件求解 解： 由 有 又由 有 由定理5.1和定理5.3知x(2)是局部极小点。 5求解问题(5.1)具体做法为： 给定初值x(0), 按照某一个规则构造迭代序列 使 由于x(k)是向量序列, 令向量pk和数 满足： 即 使即向量序列x(k) 使目标函数值f(x(k)是单调减小的, 具有这种性质的算法称为下降算法。 65.2 最速下降法 考察无约束最优化问题 其中f(x)具有连续偏导数。 对该问题的求解采用下降算法, 设x(k)是f(x)的极小点x*的一个近似值, 寻找下一个x(k+1)近似值满足 将f(x)在x(k)处作一阶Taylor展开有： 为使x充分接近于x(k)时

4、有f(x)0, 令k=012求出 , 取搜索方向3若f(x(k+1)f(x(k), 则x*=x(k), 停止计算, 否则转4。 4 转2。 9例5.2 取步长 , 初值 , 求解 解： , 该问题的准确解为2 0.001598082-0.040008249 0.953703372-0.0463493622 1.920063924-0.079503257 0.078970629-0.075736864 0 1 2 3 4迭代次数 10计算结果见下表 5.2.2 最速下降法 1847年Cauchy给出了最速下降法。 即 的取值由f(x)从x(k)出发沿方向 的整体极小点来确定。 1944年Curr

5、y对该方法进行了改正, 取 k为f(x)从x(k)沿方向 的第一个极小值点作为x(k+1), 这样施行起来比Cauchy方法容易得多。 11算法5.2.2(最速下降法) 给出初始点x(0)及误差精度0。 12求 , 若 , 停止计算并输出x*=x(k)3一维搜索求最优步长 取 4若 得最优解x*=x(k+1) , 停止计算, 否 则令 转2。 12例5.3 取 。用最速下降法求解 解： , 在算法的第三步使用一维搜索方法求步长 , 计算结果如下表: 迭代次数x1(k)x2(k)kf(x(k)0220.0200307210411.919877-0.307178510-20.481538703.6

6、8614420.708869110-1 0.708873810-10.020030720.13065030.680470810-1-0.108875310-30.481538500.4630710-240.251250710-2-0.385905110-50.020030720.1641310-350.241185310-2-0.385905110-50.481537600.5817410-560.890569110-40.890548810-40.020030720.2062010-670.854891610-4-0.136784410-60.480768700.7308410-880.32

7、8812510-50.3151298910-50.020.2482710-990.315660010-500.50.9964110-11100000 使用最速下降法计算时, 在开始几步迭代计算中, 步长比较大, 而且自变量的改变和函数值的下降幅度也较大, 但当接近收敛时, 步长很小, 自变量的改变量也很小, 所以目标函数值下降得很慢, 也即在最优解附近迭代点是以锯齿形状在前进。其理论依据为: 迭代公式中的步长 是函数 的极小点, 所以有 由复合函数的求导公式有 14即相邻两个迭代点处函数f(x)的梯度向量是正交的, 这就使得迭代过程是沿锯齿状行进的而且越接近收敛, 步长就越小, 迭代点的移动越

8、慢。梯度是函数的局部性质, 从局部看在x(k) 处函数值下降得最快, 但从整体上看是走了很多弯路。 实用中为了避免出现锯齿行进的情况, 常采用两种避免方法。第一, 选择较好的初始点。第二, 迭代到一定的步数后采用非精确的一维搜索, 即用一维搜索求出最优步长 后取 这样可避免相邻两个迭代点的梯度向量正交的情况。 155.3 Newton法 Newton法的基本思想是用二次函数来逼近f(x), 并求出二次函数的极小值点作为f(x)的近似最优解。 假设f(x)二阶连续可微, 在第k次近似解x(k)处进行二阶Taylor展开有 在 是非奇异的情况下, 略去高阶无穷小就有近似公式： 165.3.1 Ne

9、wton法 Newton法的迭代公式为： 算法5.3.1(Newton法) 给出初始点x(0)及误差精度0。 1 2求 , 若 , 停止计算并输出x*=x(k)3计算4迭代计算 5若 则停止计算, 输出 否则令 转2。 17 18 前面介绍的最速下降法本质上是用线性函数去逼近f(x), 而Newton法是用二次函数去逼近f(x), 所以Newton法的收敛速度比最速下降法快。理论上已经证明最速下降法具有线性收敛性, 而Newton法却具有二阶收敛性。特别当f(x)是二次函数时, Newton法具有整体收敛性。即对任一初值x(0), 用Newton法迭代一次就可得到最优解。当f(x)是非二次函数

10、时, Newton法虽然是二阶收敛的, 但只具有局部的收敛性, 也即当初值x(0)充分接近最优解时, Newton法才是收敛的。例5.4 求解 解: 取初值 有 在实用中算法的第4步常改写为解方程组 此时第5步的终止条件为 。 19例5.5 用Newton法求解 准确解为 。 解：取初值第一轮迭代： 20第二轮迭代： 21计算结果如下表： 22迭代次数01111-0.521.3913043-0.6956521731.7459441-0.9487980941.9862783-1.0482081051.9987342-1.0001700061.9999996-1.000001905.3.2 阻尼N

11、ewton法 阻尼Newton法是将Newton法中的 看成一个搜索方向, 并且用一维搜索方法求出最优步长的方法。 算法5.3.2(阻尼Newton法) 给出初始点x(0)及误差精度0。 12求 , 若 , 停止计算并输出x*=x(k)3求 并计算4求 , 其中 满足 23 245若 则停止计算, 输出x*=x(k+1)否则令 转2。 阻尼Newton法也有无法克服的缺点。 第一、Hesse矩阵可能出现奇异的状况。 第二、即使Hesse矩阵非奇异, 但无法保证Hesse矩阵的正定性, 为克服这两个缺点, 将迭代公式取为： 其中 是充分大的正数, 以保证 是对称正定矩阵。 使用阻尼Newton法

12、可以克服Newton法的局部收敛性的缺点, 从而可以适当地放宽对初始点x(0)的要求。 5.4 拟Newton法(变尺度法) Newton法成功的关键是利用了Hesse矩阵提供的曲率信息, 而计算Hesse矩阵的工作量大, 有的目标函数的Hesse矩阵不好求出, 需要一种仅用目标函数梯度的方法, 拟Newton法就是利用梯度 的信息, 构造出目标函数的曲率近似, 而且不必形成明显的Hesse矩阵, 同时还具有收敛速度快的优点。 Davidon于1959年提出了一个设想, 其核心是仅用在每次迭代中得到的梯度信息来近似Hesse矩阵, 该设想导致了一类非常成功的算法-拟Newton法, 包括两个最

13、著名的算法: DFP算法和BFGS算法。 255.4.1 拟Newton法的基本思想:最速下降法和阻尼Newton法的迭代公式统一为：其中 为步长, Hk为n阶对称矩阵。若Hk=I, 则是最速下降法；若 , 则是阻尼Newton法; 26 前者有较好的整体收敛性, 但收敛太慢, 后者收敛快, 但整体收敛性差, 要计算二阶导数, 工作量大, 现期望Hk的选取既能逐步逼近 , 又不计算二阶导数, 为此, 对Hk附加条件。1). Hk是对称正定矩阵;2). Hk+1由Hk经简单修正而得到 27为使算法有下降性质, 显然, 当Hk正定时, 从而方向 为下降方向。其中 称为修正矩阵(也应为对称阵), (

14、5.4.1)式称为修正公式。3). Hk满足拟Newton条件:常用的无约束方法其中事实上，由有取 29 拟Newton法的基本思想是:先取H0为某一对称正定矩阵, 然后在每一次迭代中利用关系式(5.4.2)产生修正矩阵, 再由关系式(5.4.1)产生迭代矩阵Hk, 并确定出相应的搜索方向。 由于修正矩阵Hk的选取不唯一, 因此使用不同的方法产生的修正矩阵Hk , 便可产生不同的矩阵序列Hk。由于这种方法产生的搜索方向在每一次迭代中都作改变度量矩阵意义下的最速下降方向, 因此这类方法统称为变尺度法。这里只介绍两种常用的变尺度法, DFP法和BFGS法。 30 DFP方法是由Dividon于19

15、59年首先提出, 后在1963年又由Fletcher和Powell作了改进简化而形成的, 故常称之为DFP方法。在目前是无约束非线性规划方法中最有效的算法之一。由于拟Newton法要求Hk满足设其中 为待定向量。在（2）两端同乘 有5.4.2 DFP方法 31为了使（1）成立，必须要为了保证 及（2）的右边为对称矩阵，取 32此时有故此时修正矩阵为：DFP算法的矩阵迭代公式为：算法5.4.1 (DFP法)1. 任取 和H0(一般取H0=I)2. 若 则停; 否则令 k由一维搜索求得;3. 计算4. kk+1, 转2。 33例5.6 用DFP算法求解取解: 取H0=I时, DFP法的第一步与最速

16、下降法相同。 34第二轮迭代：先计算 35得:令： 利用：求得：因 停止, x(2)即为最优解。 36 37 BFGS方法是由Broyden, Fletcher, Goldfarb和Shanno于1970年共同研究的成果。5.4.3 BFGS方法由于拟Newton法要求 满足取其中 是一个实数。满足 38取 变得DFP公式。若取迭代公式 BFGS法比DFP法更具有实用性, 其原因是BFGS法对一维搜索的精度要求不高, 并且由BFGS法产生的矩阵Hk不易于变为奇异矩阵。而对于DFP法, 由于一维搜索的不精确和计算误差的累积可能导致某一步的 Hk为奇异矩阵。 5.5 共轭梯度法 定义5.5.1 设

17、H为n阶对称正定矩阵, 若n维非零向量pi, pj满足 , 则称向量pi, pj是 H-共轭的。 特别当H=I时有 , 此时H-共轭就变成了向量正交的概念。所以, H-共轭实质上是向量正交的推广, 而且将对称正定矩阵H进行分解H=QTQ ,此时就有： , 对向量pi, pj施行线性变换y=Qp, 则有 ; 即向量yi和yj是正交向量。 39定义5.5.2 对m个n维非零向量p1, p2, , pm; 若有 称向量组p1, p2, , pm是H-共轭向量组, 也称彼此H-共轭。 显然H-共轭向量组是线性无关的向量组, 而且由于Rn中有且仅有n个彼此H-共轭的向量, 所以Rn中的H-共轭向量p1,

18、 p2, , pn构成Rn的一组基。 40 实用中常常需要从一组线性无关的向量组中, 构造出彼此H-共轭的向量组, 称它为H-共轭化方法。设向量组g1, g2, , gm线性无关。令 则向量组p1, p2, , pm是H-共轭向量组，在实用中还可以将其单位化。 41 42 设x*为f(x)最优点, x(0) 为任一给定的初始点, 若p0, p1, , pn-1是H-共轭的, 则它们可以构成Rn中的一组基, 因此向量x*-x(0) 就可由p0, p1, , pn-1线性表示。设则 这样求f(x)的最优解x*就转化为求系数 的问题。设x(k)为一个迭代点, 令是 的极小点, 则有 , 从而有 43

19、记 有 当f(x)是二次函数 时, 有此时有 得 由于x*是f(x)的极小点, 故有 44在(5.5.1)式的两端同时左乘 有同理, 记 , 则两端左乘 , 并由H-共轭得 45即k是从迭代点x(k)出发沿方向pk求二次函数的极小点的步长。 因此, 若有了n个彼此H共轭的方向p0, p1, , pn-1则无论初始点x(0)是如何选取的, 从该初始点出发 分别沿p0, p1, , pn-1作一维搜索, 最多作n次一维搜索便可得二次函数f(x)的极小点x*, 这个性质称为二次截止性。而且共轭方向的选取有很大的随意性, 由此就有不同的共轭方向法。5.5.1 自然共轭方向法 该方法是从n个单位向量ei(i=1,2,n)出发, 利用共轭化过程产生共轭方向p1, p2, , pn, 从而建立起相应的共轭方向法。 算