运筹学非线性规划4new.ppt

《运筹学非线性规划4new.ppt》由会员分享，可在线阅读，更多相关《运筹学非线性规划4new.ppt（33页珍藏版）》请在第壹文秘上搜索。

1、非线性规划2(),f xC即要求二次前提：连续可微.*1*();().kkkf xxxTaylorf xxxxx将目标函数在其极小点的近似点进行 二阶展开用展开的二次函数去逼近 将此二次函数的极小点作为的一个新的近似点，如此迭代，思想：.为提高最速下降法与共轭方向法的收目的：敛速度.二次收敛二阶方法 Newton法非线性规划推导过程：2*2(),()()()()()1()()()2kkkTkkkTkkf xCxxTaylorf xqxf xf xxxxxf xxx 设为的一个近似点，由展开：2()()()()0,kkkkqxf xf xxx 令2()()().kkkf xxxf x 2()()

2、kkf xqx若正定,解得的极小点121()()kkkkxxf xf xkkxpNewton迭代公式非线性规划kp因矩阵求逆的计算工作量太大，代替直接计算：2()()()kkTkf xpf xLDL pf x 线性方程组(),.kTLyf xDzyL pz)H(TNewton法的收敛性*2*2()()()0,()()()()0,:1,f xxf xf xf xf xHesseG xf xLipschitzi ji jn设二阶连续可微，是的局部极小点，正定，的阵满足条件，即存在，使得对所有的，有,()(),ni ji jGxGyxyx yR,*0()()(,)Newton.i jkxGxG xi

3、 jkxxx其中为的元素，则当初始点时，对于一切，迭代公式有定义，迭代点列收敛于，并且具有二阶收分靠近敛速度充非线性规划收敛优点：速度高.仅 局 部 收 敛，缺 点：计 算 量 大Newton阻尼法121Newton,()()LS.kkkkkkkkkkxxpxf xf x在迭代公式中引进阻尼因子(步长)这里由策略确定非线性规划(Newton)TH 阻尼法的全局收敛性0200()0(),(),NewtonnTnkf xxRmm uu G x uxL xuRxx 设二阶连续可微，且对任意的，存在常数，使得成立，则从任意初始点 出发，阻尼法产生的迭代点列满足：1()kxf x）当为有限点列时，其最后

4、一个点为的唯一极小点；2()kxf x）当为无限点列时，它收敛于的唯一极小点.Newton法的其它变形：带保护措施的阻尼Newton法稳定Newton法 为克服Newton法计算量大的缺点，同时又能（基本）保持其快速收敛性非线性规划().1()()().2kkkTkTkn nkxf xf xpf xpf xp B pBR在每个迭代点 附近考虑的二次逼近 (1)这里为对称阵.拟Newton法：保持最速下降法，共轭梯度法结构简单，计算量小的优 点，克服其收敛速度慢的不足目的：避免Newton法及其变形需计算Hesse矩阵，计算工作量很大，但又保持其快速收敛性基本思想与导出：非线性规划1,(1)()

5、kkkkBpBf x 若是非奇异阵 则式右端函数的稳定点为：(2)(1),.kp由逼近关系有理由把做为线搜索方向LS1.kkkkxxp1kB如何确定？21121()()kkkkkBfxfxsy希 望为的 某 种 近 似，因 (3)111()()kkkkkkkkkksxxpyggfxfx 其中，(4)(5)我们要求：1kkkBsy (6)Newton拟方程（条件）非线性规划11,01,1;nxRBk给出选：11(),LS0;kkkkkkkkkf xpBgxxp 若停止.否则，计算，利用某种求，1:1,S2kBkk构 造，使 得(6)成 立.转；1kB如何具体构造？如何保证收敛性？一般拟Newto

6、n法的迭代步骤：S1S2S3问题：非线性规划1()()TTkkkkkkkkTTkkkkkBFGS BroydenFletcherGoldfarbShannoy yB sB sBBy ss B s公式：1()(1).TTTTkkkkkkkkkkkkkTTTkkkkkkDFP DavidonFletcherPowellB s yy s Bs B sy yBBs ys ys y公式：1()().()TkkkkkkkkTkkkkyB syB sBByB ss对称秩1修正公式：典型的拟Newton法非线性规划拟Newton法的性质在适当的条件下，这一类方法中的相应算法可保证：kB的对称、正定性，一致正定

7、性对于二次函数的共轭性与二次终止性对于凸函数的全局收敛性1minkkBB相对于线性变换的不变性，最小变化性质 局部超线性收敛性拟Newton法的改进与变形稀疏拟Newton法无记忆拟Newton法有限内存拟Newton法非线性规划直接方法：不需要函数任何导数的方法函数值比较和一维搜索技术典型的直接方法坐标轮换法（交替方向法）、Rosenbrack方法单纯行法、共轭方向法、差分拟Newton法、现代优化技术Exp：极小化函数(,)m ax,.fx yxy(,)(1)(1,1)iiix y()(0,0).f x而显然，只有唯一的极小点11(,)(1,1)xy10,2e搜 索任 何均 可2(2)(2

8、)11(,)(1,1)xy22e搜 索22(,)(1,1)xy非线性规划1,0,:1.nxRk给定()()()()(1)()()()min(),:1,S3.iiiikkkikiRiiikkkkf xef xexxeiiin 求，使得若则转(1)(0)1(0)(1)(0)1;1S3,()min(),.kkkkkkkkkkRikxxf xpf xpxxp若，则，并转；求使n 利用每 次交替方向搜基本索后找到的新点估计出一个方向，进行一模式思想：搜索步.Hooke-Jeeves方法的迭代步骤：模式搜索(Pattern Search)方法S1S2S3S4(1)1111,;,:1,S2.nkkkkkkx

9、xpxxpkk若则停.否则转非线性规划性质TH*()()min()1,2,()()kiRf xxxxf xf xeinf xxxf x设连续，上述算法产生的点列 收敛于，则 必满足，对一切均成立，若在 处可微，则 为的稳定点.Nevertheless一般情况下，上述算法并不能保证收敛仅可能局部收敛，许多直接法均存在此问题非线性规划约束最优化方法约束最优化问题的最优性条件仅有等式约束的非线性规划问题：min().()0,1,2,(1)jf xsth xjq微积分中求条件极值的Lagrange乘子法1*12*1(,)()()(1),(,)()()0.qjjjqqxjjjL xf xh xxL xf

10、 xh x 在问题的(局部)最优解 处，应有存在使得含义？如何推广到不等式约束问题？一般的(MP)?非线性规划*12(,)Txx x设为(2)局部最优解，*()()0 xf xc x 因 仅仅是在约束曲线上的极小点.min().nx Rf x一般来说，它并不是的解考虑仅有一个等式约束，两个变量的简单问题1212min()(,).()(,)0 (2)f xf x xstc xc x x2)()0c x 问题(的可行域是由所确定的一条曲线，*()()f xxf x所以,在 处的梯度未必是零向量.非线性规划(4)()0(1)kkc xkk当 较大 如时，它与曲线由交点，但当 变小 如时，它将离开约束

11、曲线.*.x解点 恰好是它即将离开约束曲线而尚未离开时显，的交点然*()2()0 xf xc x在处，等高线与约束曲线相切.()f xk考虑目标函数的等高线*That i,.sxt它们在 处有公共的切线*,In o(ther words)()c xf x它们在该点处的法线方向和共线.非线性规划*()()0()()c xxc xf xc x 假定约束函数在 处的梯度向量非零:，则必存在常数，使得 (3)c*(,)()()0 xL x uf xc x*()0 xc x解 除满足上述方程组外，自然还应满足约束条件 (4)Note：*(3)(4)(2)x和为问题的局部解应满足的必要条件.不难推广到一般

12、的多个等式约束情形.非线性规划仅有不等式约束的非线性规划1212*12min()(,).()(,)0(,).f xf x xstc xc x xxxx (5)设为该问题的局部解 有两种情况：*Case1:()0c x*Case2:()0c x*12*12Case1:(,)0(,)0 xc x xxc x x对于在可行域的边界上，若去掉约束，则 可能不再是解，因而约束条件是有效的.非线性规划For Case 1:*1212 min()(,).()(,)0 (6).xf xf x xstc xc x x显然也是等式约束问题的解*()().f xc x因此，与共线*Nevertheless,(6)(

13、5)x 不仅是的解，而且是的解.*().xc x在 处指向可行域的外部*()().f xc x与是反向的*12*12Case2:(,)0(,)0 xc x xc x xx对于在可行域的内部，约束条件实际上不起作用.因为即使不考虑约束，仍然是解.非线性规划*()0,()()0 ()0c xfxc xc x若 假 定则 存 在0，使，0For Case 2:*()()0()0 xxf xf xc x在可行域的内部，是的无约束极小点，故 ，*()()0()0f xc xc x，=0Lagrange (,)()()L xf xc x若引进函数非线性规划则可综合上述两种情况下的两组条件，得到不等式约束问

14、题(5)的一阶必要条件：*(,)()()0 xL xf xc x 不难推广到一般（多个）不等式约束问题 综合上述等式约束问题，不等式约束问题时的结论，则可给出一般非线性规划问题的一阶必要条件.*()0c x，0*()0c x，非线性规划约束非线性规划问题的一阶必要条件min().()01,(MP)()01,ijf xs tgxiphxjq考虑如下的一般约束非线性规划问题 *(MP)()0,ixxig给定的某个可行点，若则第个不等式约束是一个，或称积极约束起作用约束、有其为效约束；Def.*().()0ig xI xx不起作用约束、非有效否则，即，则称该约束是；用表示在 处约束所有积极约束的指标

15、集即*()0,1,1,.()ig xixiIIpJqI，相应地，记 这里非线性规划11*1*:(),(),:,(),(,(),),(),nniinjijijfRRgRRiI xxg iII xxhRRjJg xiI xh xxxiI xjJjJ设和，在 处可微，在点 处连续，在 连续可微 并且各，若 是(MP)的局部最优解，则存在两线性实无关组数和，使 Kuhn-Tucher(K-T)条件约束规范条件Th.(约束问题的一阶必要条件)*()*()()()0 0,().iijjj Ji I xjf xg xh xiI x非线性规划*()K-TiiIg xx推论：若在上述定理中进一步要求对所有的，均

16、在 处可微，则条件可改写为：互补松弛条件Example1：求下述非线性规划问题的K-T点：21222112212min().()()()()f xxxs tgxxxgxxx +90 +10 *11*()()()0 ()0 1,0 1,pqiijjijiiif xg xh xipipg x非线性规划解：该规划问题的K-T条件为：111222210 (1)211xxx212120 ()(2)xx+91220 (3)xx+1120,0 (4)2212()()xx+90 (5)12xx+10 (6)作为K-T点，除满足上述条件外，还应是可行点：为从(1)-(6)中解出K-T点，分三种情况：非线性规划1Case1:K-)T(0gx 点不在，12()0()0Case2:K-Tgxgx，点在不在120,1,(4).则由(2)、(1)得，这与矛盾 21111 0,(1)(1)0,120 xx则由(3)得，代入得，106 ,30 x 再由(4),(5)解得=.非线性规划12()0()Ca0 se3:-K Tgxgx与的交点，因交点是点有两个：117 117(,),22Tx 10,(4).代入(1)，得这