运筹学ppt课件非线性规划课件

1、xjtu非线性规划(wolf)the 法的收敛性( )(2)wolfe(2)k-tkf xamx 设连续可微，问题的约束系数阵 的任意 列均线性无关，且其任何基本可行解非退化，则简约梯度法所产生点列的任一聚点均是的点。014(2,1,3,1)( ,) ,ttbxxx x从出发，初始时取运用简约梯度法求解下列极小化问题：例：22121231241234min( )()4(). . 21 - 0 , 0f xxxstxxxxxxx x x x xjtu非线性规划求解线性约束优化问题的其他方法：序列lp方法zoutendijk可行方向法投影梯度法有效集方法及其改进xjtu非线性规划非线性约束问题的广

2、义简约梯度法：min( ). . ( )0, 1,if xstc xim (1),kx设已有可行点在该点处由各个约束函数的梯度向量1()(),()kkkkn mmaa xc xcx , , bmn mbnnxxxxxx设存在 的一个划分：1()()(),1,bmtkkkiixibbc xc xc ximxx且假定，线性无关.xjtu非线性规划1()(),()bbkkkkm mbbxxmac xc xcx 非奇异(), , kkkn mmbnnknaaaxa各约束函数关于的偏导数向量由隐函数定理 kbnxxx在 的一个邻域内可由方程组 c(,)=0bnbnxxxx惟一的确定 为的函数：（ ）问题

3、(1)等价于下列无约束局部优化问题： min(,)(,)n mnbnnnnxf xxfxxf x （）（）xjtu非线性规划knnf xx假设用最速下降法求解此问题，先计算（）在处的梯度(,)(,)()ntbnbnbnxnnnbf xxf xxxg xf xxxx （）(,)0,tbbnnxc xxx由约束方程组知满足：(,)(,)0tttbnbnbnbnc xxc xxxxxxkba由非奇异，隐函数存在定理及上述两个等式1(,)(,)()kkkkkkkbnbnnnbnbf xxf xxg xaaxx()kkpg x 从而得搜索方向: .kpls沿进行以确定步长xjtu非线性规划约束的，于然而

4、由非线性性()( (),)(1)kkkkkkknnnpf xtpfxtpxtp当沿对进行一维极小时，难以保证问题的约束始终满足！( )(,)0( )kkbnf xc xxtp代替ls,对在满足方程组 的曲线上作曲线搜索.0()kkkbntxxtpx因 ()的解析表达式一般未知，且对每个试探步长，通过求解随而变化，因此定，( ),确xjtu非线性规划newton若用法，则有(0)kbbxx(1)( )( )( )1(,)(,)jkkbbnjjjkkbbbnxxc xxc xxtppt(1)( )1( )(,)jjkjkkbbbbnxxac xxtpnewton伪法具体迭代过程，算法？xjtu非线

5、性规划罚函数类方法通过构造惩罚函数，将带约束的非线性规划问题 转化为无约束优化问题思想：的求解。每当某个点不可行时，就要对其处以惩罚，且惩罚值将随着该点不可行性的提高而增大，但当某点变为可行时，惩罚项的则不做任构造原理：何惩罚。sumt因需通过调整罚参数，求解一系列无约束优化问题才能保证得到序列无约束极小化方法原(mp)的解，故又称不同的构造罚函数的思路，就可导出不同的 具remark:体罚函数算法xjtu非线性规划等式约束问题的平方罚函数21min ( )s.t.( )0, 1,( ,)( )( ) , 0 ( ,)jqjjkkkfxhxjqp xfxhxp xxx 罚 因 子不等式约束问题

6、的内点罚函数（障碍罚函数）000m in()s.t.()0, 1,()0, 1,inifxgxipxrgxipx xjtu非线性规划()分 倒 数罚函数11( ,)( )( )piip xf xg x1( ,)( )ln( )piip xf xg x对数罚函数000 x缺点：要求非空，且初始点迭代只能在可行域内部、病态问题xjtu非线性规划一般(mp)的混合罚函数min( ). .( )0, 1, ( )0, 1,ijf xstg xiph xjq (mp)( )jh x等式约束的违反程度可由来度量max0,( )ig x不等式约束的违反程度可由来度量依照惩罚项的构造原理可取下列函数为惩罚项：

7、11( )( )max0,( ) , (1)qpjijip xh xg x11这里，为选定的常数，( )p x 通常取 = =2，连续可微xjtu非线性规划，可定义(mp)的因此罚函数为(,)()(), (2 )pxfxpx0这里为一参数，常称其为罚因子。()xmp当 为的可行解时：( )0, 1, max0,( )0( )0, 1, ( )0iijjg xipg xh xjqh x( )0 ( ,)( )p xp xf x，( )0(1)p xx，若，则由式中各项的非负性知： 此时，对应的 必须满足(mp)的约束条件，即其为反之可行点。xjtu非线性规划()xmp当 不是的可行解时：则至少有

8、一个约束不成立。:1iip ，则若某个不等式约束不存在成立，使得( )0max0,( )( )0 max0,( )0 ( )0iiiig xg xg xg xp x:1jjq，则存若某个等式在约束不成立，使得( )0 ( )0 ( )0jjh xh xp x( )0( ,)( )xp xp xf x当 不可行时，必有从而( )()( ).p xxmpp x且由的定义知， 离的可行域越远，的值越大( )xp x而当 接近可行时，的值会变小.xjtu非线性规划，可望通过求解下列无约综上述束优化问题min( ,) (3)nx rp x ().mp来找到的最优解,( )( ),xmpxin fact若

9、对某一充分大的 ，问题(3)的最优解属于的可行域，则对(mp)的任一可行点有( ( )( ( ),)min( ,)( ,)( )nx rf xp xp xp xf x( )(mp)x这意味着为的最优解！因在实际中确定合适大小的 比较困难，k选取一个单调增的罚函数参数序列，(3)().mp通过求解一系列形如的无约束优化问题来寻找的解sumtxjtu非线性规划罚函数法的迭代步骤：01:,0,0: 1.sxck1任选初始点初始罚因子及精度参数0，令-12:(2)( ,).kkksxp xx以为初始点，求由所定义的罚函数的 无约束极小点，记其解为13:(),(), :1, 2.kkkkksp xxmp

10、ckks若则取为原约束问题的近似 最优解，停止；否则，令转xjtu非线性规划( )p x由惩罚项的特点：kk 当的时候，随着的不断增大，( ).kp x对每个不可行点的惩罚也不断增大并趋于无穷(3)()kkkxx在对应于的无约束极小化问题的最优解处，( ()kkp x的值应不断减小，().kxmp从而保证 逐步趋于可行并最终达到的最优解( )( , )p xp x由，的定义，与有极小下点的含义述定理：xjtu非线性规划11k+1( ,)(2)0,( ,)( ,)kkkkkp xp xp xxx设是由式定义的罚函数，且如果和分别在 和处达到无约束全局 极小，则有th1111(,)(,)()()(

11、)()kkkkkkkkp xp xp xp xf xf x1 2min ( ) ,.nx rp x进而，若则上述罚函数算法必有限终止()th 罚函数法的全局收敛性 1()(1)(2)( ,)kkkkkkkmpkkp xxx设存在全局最优解，为一满足且的正数序列，并假定对每个 ，由定义的函数的整体无约束极小点存在，则由罚函数算法所产生序列的任一聚点必为(mp)的全局最优解.xjtu非线性规划:.proofkxx不妨设().xmp由假定，设 为的一个全局最优解()0 xp x则由 的可行性知：(,)kkp xth从而由前一中所述的单调增性知()()()(,)kkkf xf xp xp x (,)k

12、kp xp这表明为一单调增且上有界序列，故必有极限，设为()(,)() (4)kkkf xp xf x因()().kkf xf xf故由单调增的性质知亦必收敛到某一极限于是lim()lim( (,)()kkkkkkkp xp xf xpfxjtu非线性规划k因，由上式知必有lim()0kkp x( )( )0.kxxp xp x从而由与的连续性知，有().xmp即， 为的可行解()( )(4)xf xf x由 的最优性知，以及( )lim()()kkf xf xf x()( )f xf x所以，()xxmp这一点与 的可行性表明 必为的一个全局最优解. xjtu非线性规划乘子(罚函数)法克服罚

13、函数法需罚因子趋于无穷大才可使得罚函数极小与求解(mp)等价，以及由此带来的病态性质，减目的：少计算量.给某个罚函数中增加乘子项 乘子罚函数法在通常的lagrange函数中增加惩罚项 增广lagrang想：思e函数法对一般的(mp)，其增广lagrange函数为：21121( , , ,)( )( )( )21 max(0,( )2qqjjjjjpiiiip xf xh xh xg x xjtu非线性规划相应的乘子修正公式为：1max(0,(),1, (5)kkkiiigxip1(),1, (6)kkkjjjhxjq11111:,0,0,0,: 1.sxk 选取初始点令乘子罚函数法的迭代步骤：

14、112:min( ,), .,.nkkkkx rkksxp xxx以为初始点，求解无约束问题得若 c()停止112213:4104 2.kkkksxxss若 c()c() ，则转；否则，令，转1114:(5)(6),:1,2.kkkkskks由计算，令，转xjtu非线性规划11( )(max0,( ),max0,( ),( ),( )remark:pqc xg xgxh xh x)h (t乘子法的收敛性 (mp).,(mp).kkkxxx 若的可行域非空，则对任何 0，上述乘子法必有限终止.对0，算法所产生点列的任何聚点都是可行点如果有界，则 必为的最优解xjtu非线性规划(sqp)序列二次规划方法克服上述方法收敛速度目的：慢的不足.newton.拟法在约束问题思：中的推广想约束线性化，目标函数“二次”化1min ()(,)2. . ()()0, 1, ()()0, j1,kttkkkkktiikktjjf xpp w xpstg xg xpiph xh xpq11(,)mp)lagrange ( , , )( )( )( )(,)hessen.kkkqpjjiijikkkw xl xf xh xg xxx 这里，为(的函数在处关于 的阵xjtu非线性规划111:,: 1.n nsxbrk选取初始点正定阵