运筹学非线性规划3

1、orxjtu第二章 线性规划 放松对 的要求，只要求目标函数在迭代的每一步都有充 分下降即可。这样可大大减少求 的工作量 不精确ls法。 不精确线性搜索法不精确线性搜索法kk目的目的：为克服精确线性搜索法的不足：为克服精确线性搜索法的不足在寻求目标函数的最优解时，往往没必要把ls搞得十分精确，特别是在算法的初始阶段更是如此。 精确ls法虽可使目标函数在每次迭代中下降较多，但计算工作量比较大； 非线性规划非线性规划orxjtu第二章 线性规划建立不同的具体规则，就可以构成不同的不精确建立不同的具体规则，就可以构成不同的不精确ls法法常用规则：常用规则：既不希望 取得太大而引起 的大幅度摆动也不希

2、望 取得太小而致使 在达到 之前就过早地移步不前kkkxkxx0kngoldsteingoldstein准则准则给定 ，选取 满足： （1）11,01,(0, ),( ,1)22 0() ()() ()ktkkkkkkktkkf xpf xf xpf xp 左不等式说明应选取 使 有充分的下降,右不等式保证了步长 不会取值太小。( )f xkk第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划(1)式等价于以下两个不等式()()()(2)()()() (3)kkkktkkkkkkktkkkf xpf xf xpf xpf xf xp 令 ，则由(2)、(3)有，( )()kkf x

3、p ()(0)()(4)()(0)()(5)ktkkkktkkkf xpf xp 12( )(0)()( )(0)()ktkktklf xplf xp在 平面上，点 应在下述两条直线之间：( , ) ()kk ，第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划 也就是说，夹在这两条直线之间的曲线 所对应的 均满足(1)式。( ) 称满足（称满足（1 1）式的）式的 为为可接受步长可接受步长；由所有可接受步长构成的区间称为由所有可接受步长构成的区间称为可接受区间可接受区间。remark: 这个条件是必要的这个条件是必要的1(0, )2第四章第四章 非线性规划非线性规划orxjtu第

4、二章 线性规划事实上，若 是满足条件 ( ) (0)0,(0)0的二次函数，则 的全局极小点为 ( ) (0)(0) 而相应的全局极小值为 1()(0)(0)2 由式（4）可得 ()(0)(0) 由这两个表达式，并注意到 ，则有 (0)012第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划goldsteingoldstein不精确不精确lsls的计算步骤：的计算步骤：第四章第四章 非线性规划非线性规划s1：给定初始搜索区间 及 ， max0,11(0, ),( ,1),122计算 (0)(),(0)()kktkf xf xd 令 ，取 ， 00max0,ab00(,)a b0j

5、s2：计算 ，若 ，则转s3； ( )()kkf xd ( )(0)(0) 否则， ，转s411,jjjaabs4： ，转s2.11,12jjabjjs3：若 ，则 ，输出 ，停止；( )(0)(0) kkmax1,4; 1,2.jbsjjs若转否则，转否则， ；11,jjjabborxjtu第二章 线性规划第四章第四章 非线性规划非线性规划无约束最优化问题无约束最优化问题min ( ) nf xxr（） 典型算法：典型算法：解析法：解析法： 可微，算法迭代过程中要用到 等信息直接法：直接法： 无需可导，算法迭代过程中仅用到函数值 ( )f x ( )f x2( ),( )f xf xorxj

6、tu第二章 线性规划第四章第四章 非线性规划非线性规划无约束优化问题的最优性条件：无约束优化问题的最优性条件： 由上节介绍下降方向时的定理易知th(极值的必要条件极值的必要条件)：设 在点 处可微， 1:nfrrnxr若 为问题（）的局部最优解，则必有 x()0f x使 成立的点 称为函数 的驻点、稳定点，或平稳点 ( )0f xx ( )f xremark: 平稳点可以是极小点，也可以是极大点；甚至也可能既不是极小点，也不是极大点， orxjtu第二章 线性规划第四章第四章 非线性规划非线性规划th(极值的充分条件极值的充分条件)：设 （即函数具有连续的二2( )f xc阶偏导数）， 为它的

7、一个稳定点，则 为 的一个严 x ( )f xx格局部最优解的充分条件是 的hesse阵 正定。 ( )f x2()f xproof: 因为 为 的稳定点，故有 .x ( )f x()0f x 将 在 处进行taylor展开，有 ( )f xx22221( )()()()()()()()21 ()()()()()2tttf xf xxxf xxxf xxxo xxf xxxf xxxo xx由 的正定性得： 2()f x21()()()0, 2txxf xxxxx 而 为 的高阶无穷小量。 2()o xxxx必然存在 ，使得 , . 0( )()f xf xxxorxjtu第二章 线性规划第四

8、章第四章 非线性规划非线性规划example： 1( )2ttf xx axb xc稳定点 ： x0axb若 为正定阵，则其驻点 必为（全局）最优解。 axth(凸函数的极值条件凸函数的极值条件)：设 ， ， 是 上的 1:nfrrnxrfnr可微凸函数，若有 ，则 为问题（）的全局最优 ()0f xx解。 proof:因 为 上的可微凸函数，故由前述凸函数的等价刻 fnr画定理知： () ()( )(),tnf xxxf xf xxr 由于 ，则有()0f x()( ), nf xf xxr 对于无约束凸规划问题，其目标函数的驻点即为其全局最优解。orxjtu第二章 线性规划第四章第四章 非

9、线性规划非线性规划最速下降法最速下降法 基本思想基本思想：若 连续可微，且当前迭代点不是 的平稳点，则由前述关于下降方向的存在性与性质可知，此时 的负梯度方向为使其下降最快的方向，选取它作为搜索方向 ，则有 ( )f x( )f x( )f xkp最速下降法的迭代步骤：最速下降法的迭代步骤： s1：选取初始点 ，给定精度参数 ，令 . 0 x0: 0k s2：计算 ，若 ，停止，输出 ，否则转s3.()kf x()kf xkxs3：取 . ()kkpf x s4：采用某种ls技术确定步长 ，令 ，k1,:1kkkkxxpkk转s2. remark:在s4中选择不同的ls策略，就可以导出不同形式

10、的最速下降算法。定步长，变步长；不精确ls，精确ls. 0: argmin()kkkf xporxjtu第二章 线性规划第四章第四章 非线性规划非线性规划最速下降法的全局收敛性定理：最速下降法的全局收敛性定理：th.设 一阶连续可微， 是由采用精确ls的最速下降法产( )f xkx生的迭代序列，则 的每一个聚点都是 的平稳点。 kx( )f xth.设 是二阶连续可微函数且 ，对任给初始点 ( )f x2( )f xm0 x，采用精确ls的最速下降法或有限步终止，或 lim()0kkf x或 . lim()kkf x example:2212( )f xxx010000001*(2,2) ,

11、()(4,4)() argmin()0.5(2,2)0.5 (4,4)(0,0)ttttxf xxf xf xf xxx 事实上，对任意的初始点，利用精确ls的最速下降法均有 ,1(0,0)x orxjtu第二章 线性规划第四章第四章 非线性规划非线性规划2212( )25f xxx采用精确ls的最速下降法需要10次迭代才能找到最优解 (0,0)twhy？对于采取精确ls的最速下降法，有110()() () () ()(). ()0kktkkkkktkkktkktkf xppf xf xf xf xf xpp 最速下降法中相邻两次迭代的搜索方向是相互正交的。orxjtu第二章 线性规划第四章第

12、四章 非线性规划非线性规划在二维空间，该二元函数的等值线为椭圆，则有下图：考虑目标函数 为二次函数的情形， ( )f x因此，几何上，最速下降法产生的迭代序列 向极小点 kx*x的移动路径呈“锯齿状”。 在迭代开始的几步，移动步长较大， 下降的幅度亦比较大； ( )f x随着迭代的进行，当 越来越接近 时，移动步长越变越小， kx*x的下降速度越来越缓慢。 ( )f xorxjtu第二章 线性规划第四章第四章 非线性规划非线性规划解释解释：“最速下降”是基于 梯度描述的，其变化的局部特征， ( )f x这仅能保证在当前迭代点的某个邻域内来说可使 下降最快， ( )f x并不能保证从问题的整体求

13、解，算法的整体迭代过程来说亦最快。 总之，总之， l最速下降法全局收敛，对最速下降法全局收敛，对ls要求不高要求不高l最速下降法简单易行，计算量（每步）与存贮量需求小最速下降法简单易行，计算量（每步）与存贮量需求小l在问题求解的开始阶段，采用最速下降法是比较适宜的在问题求解的开始阶段，采用最速下降法是比较适宜的 与其他算法结合与其他算法结合l收敛速度太慢收敛速度太慢线性收敛速度线性收敛速度orxjtu第二章 线性规划共轭方向法共轭方向法特点：特点： 把它用在n维二次函数的极小化问题上时，最多经过n次迭代即可找到其最优解有限步终止性。 共轭方向法的讨论与二次函数是分不开的 应用原理应用原理 ：对

14、于连续可微的一般函数，它在其极小点附近的性态近 似于二次函数从而可用于无约束优化问题。第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划def（共轭方向）（共轭方向）设a为n阶实对称矩阵，对于非零向量 ，若 ,np qr（1） 0tp aq 则称 和 是相互a共轭的。pq对于非零向量组 ，若 ,0,1,1inpr in0,tijpap ,0,1,1 , ,i jnij则称 是a共轭方向组 011,npppl或称它们为一组a共轭方向。 若在（1）中取 ，则 ，即 和 正交。nai0tp q pq（a-）共轭是线性代数中正交向量概念的推广！）共轭是线性代数中正交向量概念的推广！第四章第

15、四章 非线性规划非线性规划orxjtu第二章 线性规划example: 2112a，则向量既满足 ,又满足 2111,1012111,101而且 111,120 , 1, 12011 故它们既是a共轭的，又是正交的。同样的方法可以检验，向量 和向量 是a共轭1,0t1, 2t的，但不是正交的。第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划共轭方向的性质：共轭方向的性质：th:设a是n阶实对称正定矩阵， 为非零向,0,1,1inpr in量。若 是一组a共轭方向，则它们一定是线性无 011,npppl关的。 proof:设存在一组实数， ，使得 .011,n 110njjjp依次

16、用 ，左乘上式得 ,0,1,1tipa in110,0,1,1ntjjjjpapjnl（） 因已知 是一组a共轭方向，故有011,npppl0,0,1,1, tijpapi jnijl而a的正定性与0,0,1,1tiipapinl第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划将上述两组关系式带入()，则知必有0,0,1,1iin这意味着 是线性无关的。011,nppplln维空间中a共轭的向量的个数最多为n l在n维空间中，若有 彼此a共轭,则 011,npppl便构成了n维空间的一个基。 011,npppl反之？反之？ th：任给n维空间中的一组线性无关向量 ，可通 12,m

17、g gg过它们的线性组合构造出一组m个向量 ,它们彼12,mp pp此之间是a-共轭的。 第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划11pgproof：不妨取 （给出共轭化过程），（当然取 1,1,2,ipg im均可。故自由度很大。） 为产生与 共轭的方向 ，取1p2p221pgp即 与 是a-共轭的。 1212221211111ttttp agp agpgpggp app ap1p（因而可取 中任一个异于 的方向，放在 的位置 12,mg gg1g2g上，故 的选择也有很大的自由性） 2p由 与 a共轭，有1p2p1212110tttp app agp ap得 1211

18、ttp agp ap 设已求出 ，它们彼此是a-共轭的，其中 12,kp pp每一个向量都是 的线性组合。 12,mg gg第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划为得出一个向量 ，它与 均为a-共轭，记 1kp12,kp pp111kkkrrrpgp为使 与 a-共轭，即有1kp12,kp pp10 , 1,2,tikp apik由此可求出应有 1 , 1,2,tikitiip agikp ap 即 1111tkikikktiiip agpgpp ap(*)与 a-共轭。12,kp pp因 为标量，而每一个 均为 1ttikiip agp ap12,kp pp12,mg

19、 gg的线性组合，所以 也是 的线性组合。 1kp12,mg gg在(*)中取 ，便得到了m个彼此a-共轭的向量 1,2,1km12, .mp pp第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划th：0向量与任何向量均a-共轭，除0向量外， 向量a-共轭的概念与向量的长度是无关的。 极小化严格凸二次函数的共轭方向算法极小化严格凸二次函数的共轭方向算法 1min2ttfxx axb xcnxr(qp)考虑如下迭代格式1,1,2,kkkkxxpkl(1)第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划这里 为实对称正定阵， ， n nar是关于a-共轭的一组共轭方向。

20、01,nbrpp若采用精确ls法确定步长 ，则有下列结论。kth：（最佳步长的计算公式）：（最佳步长的计算公式） 设 是关于a的共轭方向， 则在迭代公式（1）中的最佳步长为： 01,kppp0,kkkkkkkkfxpfxpappapp 第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划k f xproof：因为 是的最小点，而 为严格凸函数 故知 是如下方程的根:k,0kkkfxpp,0kkka xpb p,0kkkaxbapp,kkkkkkkkkfxpaxb pappapp 第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划由于 关于a共轭，故有01,pp 10101

21、101110,kkkjjkjkkjjkjkkjkjjkfxpfxfxfxpfxpa xxpfxpappfxp从而得知：0,kkkkfxpapp 进而，我们还可以证明此时共轭方向法的有限步收敛性。第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划th：（有限步收敛性）：（有限步收敛性） 设 为任一组a-共轭方向，则对任意011,nppp的初始点 由(1)式按精确ls法产生的序列 0nxr kx最多经过n次迭代即可找到（qp）的全局最优解 proof：若存在某个 ，使得:01kkn0kfx则 必为（qp）的全局最有解。*kxx第四章第四章 非线性规划非线性规划orxjtu第二章 线性规

22、划设当 时，均有 ，下证1kn0kfx0nfx由其共轭性知 为n个线性无关的向量。011,nppp要证 ，只须证， 0nfx,0,0,1,1nifxpin因为100110000nnnjjjnnjjjjjjfxaxba xpbaxbapfxap第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划所以100000,0nniijijjiiiiiiiiiifxpfxpappfxpappfxpfxpappapp0,1,1in第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划fletcher-reeves共轭梯度法共轭梯度法 l对于a共轭的方向组 不仅不唯一，而且随意011,nppp

23、性大。 l用不同的方法可产生不同的共轭方向向量组，从而就有不同的共轭方向法。共轭梯度法共轭梯度法 以各迭代点处的负梯度向量为基础。任选初始点 ，若 ，则取 , 从 点沿 0nxr00fx00pfx 0 x方向 进行精确ls，求得 . 0p0令 ，若 ，则已获得（qp）的最优解 . 1000 xxp 10fx*1xx否则，第二个搜索方向取 ，这里 的选取 1100pf xp 0要使 与 关于a共轭，即 .由上式可推得p0p100tpap 01000ttpa f xpap第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划一般地，若已获得a的共轭方向 ，依次沿它们进行 01,kpppls

24、所得迭代点 . 11,kxx若 ，则 .10kfx*1kxx否则，定义 ,110kkkiiipfxt p 为使 与 是a-共轭，应选 . 1kp01,kppp0110kttt从而,11kkkkpfxp 而为使 与 为a-共轭，即要求 .1kpkp10tkkpap2112tkkkktkkkf xpa f xpapf x0,1,2kn第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划fletcher-reeves公式：公式：0011212,0,1,2kkkkkkkpf xpf xpknf xf x 的不同选取方法将导出不同形式的共轭梯度法 kvpolak-ribiere-polyak法法 112tkkkkkf xf xf xf x第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划vdixon法法 21kktkkfxfxpvcrowder-wolfe法法 111tkkkktkkkf xf xf xf xf xpexample: 用f-r共轭梯度法求解前例2212min25xx第四章第四章 非线性规划非线性规划orxjtu第二章 线性规划2212min25xx0001121020110011211*12,24,1001.91988, 0.003073.