最优化理论与算法(第二章)

《最优化理论与算法(第二章)》由会员分享，可在线阅读，更多相关《最优化理论与算法(第二章)（27页珍藏版）》请在金锄头文库上搜索。

1、1第二章 一维搜索2.1. 引言一、精确与非精确一维搜索如前所述，最优化算法的迭代格式为： 1kkxd因而算法的关键就是选择合适的搜索方向，然后再确定步长因子 。若设k()kfx现在的问题是从 出发，沿 方向搜索，希望找到 ，使得 ，这就是所谓的一维搜kxkdk()0k索或称为线搜索(line search )问题。 若求得的 ，使目标函数沿方向 达到最小，即使得kk0()min()kkfxdfxd或 ，则称为最优一维搜索，或精确一维搜索。相应的 称为最优步长因子。k 如果选取 ，使目标函数获得可以接受的改善，即k，()0kkkfxfd则称之为近似一维搜索，或非精确一维搜索。注：精确搜索与非精

2、确搜索在最优化算法中均广泛应用，它们存在各自的优缺点。二、一维搜索的基本框架一维搜索实际上是一元函数的极值问题，其基本的解决框架是： 确定包含最优解的初始搜索区间； 采用某些区间分割技术或插值方法不断缩小搜索区间，最后得到解。注：值得注意的是，这样得到的解大多数情况下均为近似解。因此，即便采用精确一维搜索策略，只要应用了数值方法，最终得到的结果都不一定是真正数学意义上的最佳步长因子。初始搜索区间的确定2定义 2.1 设 ， 是函数 的最小值点，即 。若存在:R*0,)()*0()min()闭区间 ，使 ，则称 为一维极小化问题 的搜索区间。,0,)abab,0i确定初始搜索区间的进退法基本思想

3、：从一点出发，按一定步长探测，试图找到函数值呈高低高变化的三点。具体地，从初始点 出发，取初始步长为 。若 ，则下一步从新点 出发，加大步00h00()(h0h长，再向前搜索。若 ，则下一步仍从 出发，沿反方向搜索，直到 上升，() ()即 为止。0()在确定了初始搜索区间后，剩下就是采用具体的一维搜索方法确定出 。后面将分别介绍几*种常用的一维搜索方法，这些方法主要是针对所谓单峰函数设计的。单峰函数的定义定义 2.2 设 ， 。若存在 ，使得函数 在 上单调下降，:R,abR*,ab()*,a而在 上单调上升，则称 是函数 的单峰区间， 是 上的单峰函数（准确*,b()b地说应是单谷函数）

4、。单峰函数还可以等价地定义如下定义 2.3 如果存在唯一的 ，使得对于任意的 且 ，有*,ab12,ab12 若 ，则 ；212() 若 ，则 。*1则称 是 上的单峰函数。(),ab下面定理表明，对单峰函数，可以通过简单地比较函数值，缩小搜索区间。定理 2.4 设 是 上的一个单峰函数， ，且 。(),12,ab12 若 ，则 是 的单峰区间；12()2,a() 若 ，则 是 的单峰区间。1b证明：略 32.2. 精确一维搜索的收敛理论一、基于精确一维搜索的极小化算法无约束最优化问题算法的基本框架： 给出初始点 ，允许误差 ，置0nxR0:k 计算下降方向 kd 利用一维搜索，确定步长因子

5、，使k0()min()kkkfxdfxd 令 ，若 ，则停止，输出最优解 。1kkx1()kf*1k否则，置 ，转。:在上面算法中，采用了精确一维搜索。下面证明基于精确一维搜索的极小化算法的收敛性。二、算法收敛性定理 2.5 设 是 的解，若 ，则有：k0min()kfxd2() (0)kfxdM21) cos,k kkfx证明：由定理假设，有，22()()Tkkkkfxdfxfd(0)令 （若要 ，则必须 ，即 与 成锐角） ，2TkfM0()Tkfxkd()kfx22()()()TkkkkkkkfxfdfxfdfM，2 22 2(111() ()cos,()T Tk kk kkkkdf f

6、xf fxdfx定理证毕。注： 由证明过程可以看出， 必须和 成锐角。kd()kfx 给出了精确搜索前提下，每步迭代所得改进量的估计式，显然与 有关。kd定理 2.6 设 是开集 上的连续可微函数，若某一极小化算法满足：()fxnDR4， ，1()(kkfxf()0Tkfxdk又设 是序列 的聚点， 是满足 的指标集。假定存在 ，使得 ，xD1K1limxK0M1kK有 ，又设 是序列 的任意聚点，则kdMdk()0Tfx进一步，若 在 上二次连续可微，则还有()fD。2()TTdfx证明：设 是满足 的指标集，下面用反证法证明。若定理结论不成立，21K2limkKd即 ，()0Tfx由于 ，

7、kd注意到 时， ，2kK2Kx2kKd则有 ，()0Tf因而必有 。 （）xd于是存在 的邻域 和指标集 ，使得当 ， 时，有x()N32K()xN3kK， （由（）式可得）0Tkfx设 是一个充分小的正数，使得对所有 ，及所有 ，都有3k， （由 ， 有界可得）()kxdNxkxkd则 3011()()(kkkkk Kfffffx3 3 () )TkkkkkKfxdfxfd(01)k，32k与 为有限值矛盾，故必有 。0()fx()0Tfxd同样地，若 2()0Tdfx5不成立，则必有 。2()0Tdfx类似地，有 30()(kkkKfxdfx32)()()TTkkkkkKfxdfd(01

8、)k3 32 2()()Tkkkk kKfd此矛盾表明必有： ，定理证毕。2()0Tdfx定理 2.7 设 在水平集 上存在且一致连续，算法产生的方向 与0()Lfx kd的夹角 满足： ()kfxk， （ 是某个正数）2k则或者对某个 ，使 ，或者有 ，或者有 。k()0fxkf()0kfx证明： 若有某个 ，使 ，则结论已证。因此，可设 ， 。又由于()f()0kfx是一个下降序列，若其无下界，则有 ，结论也成立。故可设 有下()kfx lim()kkfxk界，因此 存在。从而有： 。lim()kkf1()0fx下证 。反证：若 ，那么 ，不论 多大，都存在 ， ，0xkNkN使得 。()

9、kf从而 1()cos()sin2Tkkkxdfx由 （ 位于 与 之间）()Tkffdkkxkd()()TTkkxff，)()kk kkkfxfdffx注意到 在 上一致连续，故存在 ，使得当 时，有fxL0kd1()()2kkffx6若在上面的不等式中取 ，则得kd1()()()2Tkkkkfxdfxfx1(2kfx故有 1 1()()(kkkkdfff 这与 矛盾。故必有 。1()0kkfxf0kfx注： 上述收敛定理不仅仅针对某一个特定算法。实际上，前述算法模式中任意算法只要满足定理所需条件中，就都是收敛的。 ，意味着 的任何极限点均为稳定点，但它并不保证 本身收敛。()0kfxkx

10、kx三、采用精确搜索的极小化算法的收敛速度引理 1 设函数 在闭区间 上二次连续可微，且 。若 在 上的极小点()0,b(0)()0,b，则 。其中 满足 ， 。*(0,)b*()M0M,证明：构造辅助函数，()0它有唯一零点 。注意到 00()()()()dMd即 的图像总位于 之下，再由 是单调上升函数，由此可得： 的零点 必位()*于 零点 的右边。即 *(0)M事实上，在 零点的左边， 。由 ，有 。故 的零点()()()0()不可能位于 的左边。故必有 。*引理 2 设 在 上二阶连续可微，则对任意向量 ， 和任意实数 ，有：()fxnRxndR.1220()()()()TTdffx

11、dtftdt7证明： （ 为积分变量）10()()fxdfxdftt（再分部积分）10Tt10()()()()Ttfxtfxtd.1220TTdfxd引理 3 设 在极小点 的邻域内二阶连续可微，且存在 ，和 ，()fx* 0mM使得当 时， *， .222()TmyfxyMnyR那么当 时，有*x，2 2*11()xfxx.*()fm证明：在引理 2 中取 ，再令 ，则*xxd*x1*2*0()()()(1)()Tfftfttxdt注意到 及引理条件即得:0x.2 2*1()mxfxMx又由 ，12*0() ()()f fttdt因此有 *()Txx12*0()1()Tfttxdt 2*mx

12、由此即得 .*fxm利用上述引理，可得下面的收敛速度定理。定理 2.8 设极小化算法产生的序列 收敛到 的极小点 ，若 在 的某一邻域内二阶kx()fx*()fx*连续可微，且存在 ，和 ，使得当 时，有0M，222()TmyfxynyR8则 线性收敛。kx证明：由 。故当 充分大时，有*limkxk， ，2k*12kx因而，存在 ，使得0*1()kkkkxdxd(这是由于在每次迭代中，搜索方向 可取为单位向量，故有界)。记 ()kfx由于 ，*kd*kx故当 时，有0* *() (0,1)()1()(1)kkkkkkkxxdxd又注意到 00Tkfx， 22()()kkddM (0,)k由引

13、理 1 知 在 上的极小点 满足kfx,22()(0)Tkkkfxd（其中 为夹角 ）2()coskkfxMk,()kkdfx（ 为 的下限）()kfdcosk若记 ，() 0kkfx则有 。k9令 kkxd由于 位于 与 决定的线段上，因而 到 的距离不会超过 到 与 到kx1 kx*xk*中距离的最大者，即1 *1max,kkkxx由引理 2， ()()(k kfdffdfx1220)TTk kkxttdt()kfM2coskkkxd21()kfd22()()kkkxfxfxdMdM（由 的取法）22()kfk（由引理 3）22*kmx2*()kffxM（由引理 3）2*()kfxf因此， * *2*11()()(1()()k kk kmfxxffxfxfM