运筹学-非线性规划-2-约束极值课件.ppt

1、7.约束极值问题的最优性条件约束极值问题的最优性条件ljxgmixhtsxfji,1,0)(,1,0)(.)(min ，其其中中可可行行域域0)(,0)(|xgxhxD .)(,)(,)()()(,)(,)()(2121TlTmxgxgxgxgxhxhxhxh ）：积积极极约约束束（起起作作用用约约束束处处的的积积极极约约束束。是是，则则称称不不等等式式约约束束，若若对对于于xxgxgDxjj0)(0)(1,0)(|)(ljxgjxIxj 处的积极约束指标集处的积极约束指标集处处的的积积极极约约束束指指标标集集。，求求点点令令设设例例xxxxgxxxgxxxgT 22,22,0)(,01)(,

2、02)(.13222122121.解解,022222)(21 xg,022221)(222 xg,022)(3 xg。2,1)(xI1x2xO0)(1 xg0)(2 xg0)(3 xgx。有有处处的的可可行行方方向向，则则为为性性质质：若若0)()(pxgxIjxpTj)(1xg)(2xg p0)(2 xg0)(1 xgx。处处的的可可行行方方向向必必是是则则有有若若，反反之之，对对于于方方向向xppxgxIjpTj,0)()(;0)(,0)(,)(tpxgxgxIjjj则则即即若若.0)()()()()()(,)(topxgttopxgtxgtpxgxIjTjTjjj则则若若有有因因为为对对

3、于于充充分分小小的的,0 t因因此此有有处处的的下下降降方方向向，为为，则则另另外外，若若xppxfT0)(.*)(,0*)(0*)(*xIjpxgpxfpxTjT 且且使使得得向向为为极极小小点点，则则不不存存在在方方定定理理：若若Kuhn-Tucker 条件（极值点的必要条件）条件（极值点的必要条件）.0*)(*)()1(xgixIi，即即只只有有一一个个积积极极约约束束若若.*为为一一个个局局部部极极小小点点设设 x.*)(*)(pxfxgi可可行行下下降降方方向向否否则则存存在在一一个个共共线线且且方方向向相相反反，与与则则 )*(xgi)*(xf p*x.0*)(0*)(,*)()2

4、(两个积极约束两个积极约束和和，即有，即有若若 xgxgjixIji;*)(*)(*)(一一个个可可行行下下降降方方向向而而有有体体的的高高与与棱棱夹夹锐锐角角，从从，四四面面它它们们为为棱棱有有一一个个四四面面体体共共面面，若若不不然然，以以、则则xfxgxgji 。一一个个可可行行下下降降方方向向的的夹夹角角内内，否否则则也也有有与与必必在在进进而而，*)(*)(*)(xgxgxfji 。使使得得所所以以，*)(*)(*)(0,0 xgxgxfjjiiji )*(xgi)*(xf p*x)*(xgj)*(xgi)*(xf *x)*(xgj)*(xf 使使得得存存在在实实数数线线性性无无关关

5、，则则设设一一般般地地，)*)(0*)(*)()3(|xIjxIjxgjj *)(*)(*)(xIjjjxgxf.)*)(*)(*)(张张成成的的凸凸锥锥内内在在即即xIjxgxfj )*(xf *x使使得得、约约束束，因因此此有有正正数数极极代代替替，而而且且二二者者都都是是积积和和可可用用两两个个不不等等式式约约束束由由于于等等式式约约束束 iijiiixhxhxh 0)(0)(0)()4(miiiiixIjjjxhxhxgxf1*)()(*)(*)(*)(*)(，则则令令 iii miiixIjjjxhxgxf1*)(*)(*)(*)(Kuhn Tucker(K T)条件条件:),2,1

6、(0),2,1(0*)(*)(*)(*)(11ljljxgxgxhxfjjjljjjmiii 满足满足、实数实数线性无关，则存在一组线性无关，则存在一组、可微，可微，在在、是局部极小点，是局部极小点，若若jijijixIjxgxhxxgxhxfx )*)(*)(*)(*)()()(*上述为上述为K T条件，满足该条件的可行点称为条件，满足该条件的可行点称为 K T点。点。若定义若定义 Lagrange 函数函数 ljjjmiiixgxhxfxL11)()()(),(条条件件为为乘乘子子，则则称称为为其其中中TKLagrangeji ,ljljxgnjxxLjjjj,2,1,0,2,1,0*)(

7、,2,1,0),*,(极值点的充分条件：极值点的充分条件：若若 x*为为 K T 点，且对符合以下条件的方向点，且对符合以下条件的方向 p )0,*)(0*)()0,*)(0*)()0)(0*)(jTjjTjiTixIjpxgxIjpxgxhpxh 为为等等式式约约束束是是严严格格局局部部极极小小点点。，则则有有*0),*,(2xpxLpxT 例例.用用 K T 条件解问题条件解问题0,02,01.)2()1(),(min212121222121 xxxxxxtsxxxxf解解.Lagrange 函数函数2312211122221)2()1()2()1(xxxxxxxxL K T 条件条件0,

8、0,0,0)2(0)2(20)1(2321231221131212111 xxxxxxLxxL0,02,01212121 xxxxxx可行性条件可行性条件，可解出，可解出，则，则若若00,0,0)2(32211 xx.0,1,0,23,2113221 xx.,02,2,12121不不可可行行但但这这导导致致 xxxx，可可解解出出则则若若0,1,0,0,0)3(32211 xxx.0,4,222矛矛盾盾与与 有有结结合合则则若若,01,02,0)1(21211 xxxx.,0,0)4(211不不可可行行若若 xx 点点，是是唯唯一一TKx 23,21*是是极极小小点点。正正定定，所所以以且且*

9、20022xLx 8.二次规划二次规划 njnkkjjknjjjxxqxq11121min)ii(,2,1,0)i(,2,1,.1njxmibxatsjinjjij njjjinjjijmiinjnkkjjknjjjxbxaxxqxqxL11111121),(Lagrange 函函数数.kjjkqq 其其中中)iii(,1,011njaxqqxLjmiiijnkkjkjj )iv(,1,0)(,1,0njnjxjjj K T 条件条件求二次规划的求二次规划的 K T 点等价于求线性等式及不等式组点等价于求线性等式及不等式组(i)、(ii)、(iii)、(iv)的一个可行点，并且满足互补条件的一

10、个可行点，并且满足互补条件(*)。设设 x 0 是一个满足条件是一个满足条件(i)、(ii)的基本可行解，则求的基本可行解，则求(i)-(iv)的可行点可转化为线性规划问题的可行点可转化为线性规划问题:njjz1minnjqzaxqjjjjmiiiijnkkjk,1,)(11 mibxainjjij,1,1 ,0,jiijjzx 。，其其中中jnkkjkjnkkjkjqxqqxq1010,1,1 上述线性规划有初始基本可行解：上述线性规划有初始基本可行解：nkkjkjjiijjjxqqzxx100,0,0,同同时时成成为为基基变变量量。和和不不能能让让线线性性规规划划时时述述在在用用单单纯纯形

11、形算算法法求求解解上上注注：为为了了满满足足互互补补条条件件jjx,)(初始基本可行解中的基变量包括初始基本可行解中的基变量包括 x 0 中的基变量和所有中的基变量和所有 z j。优优解解。，即即算算法法能能获获得得整整体体最最正正定定，则则行行且且收收敛敛性性：若若二二次次规规划划可可0min)(1 njjnnjkzq定定阵阵处处理理。增增大大主主对对角角元元后后化化为为正正定定成成立立，但但可可适适当当半半正正定定，上上述述结结论论不不一一若若nnjkq)(9.可行方向法可行方向法mixgtsxfi,1,0)(.)(min 在迭代点在迭代点 x k，选择一个可行下降方向，选择一个可行下降方

12、向 p k 为搜索方向，为搜索方向，则则 p k 应满足应满足)(,0)(0)(kkTkikTkxIipxgpxf p k 可以通过解下述线性规划获得：可以通过解下述线性规划获得：njpxIipxgpxftsjkTkiTk,2,1,11)(,)()(.min nppp1其其中中;)()(,0*线线性性无无关关）点点（若若已已是是处处不不存存在在可可行行下下降降方方向向则则性性质质：若若kkikkxIixgTKxx 。处处的的一一个个可可行行下下降降方方向向则则得得到到若若*,0*pxk 。点点，即即总总有有一一定定收收敛敛到到有有例例子子表表明明上上述述方方法法不不0*TK改进方法：在找可行下

13、降方向时考虑所有约束，即改进方法：在找可行下降方向时考虑所有约束，即njpmipxgxgpxftsjTkikiTk,2,1,11,2,1,)()()(.min 可可行行解解。是是上上述述线线性性规规划划的的一一个个Tp)0,0(,0 行行解解。也也是是上上述述线线性性规规划划的的可可Tp)0,0(,0 ;,0*点点是是则则性性质质：若若TKxk 处处的的可可行行下下降降方方向向。是是则则若若kxp*,0*是是可可行行方方向向。又又，时时，*,0*)(,0*)(0)()(ppxfpxgxgxIiTkTkikik 可证：改进方法具有全局收敛性。可证：改进方法具有全局收敛性。10.制约函数法制约函数

14、法将约束非线性规划问题转化为一系列无约束问题求解。将约束非线性规划问题转化为一系列无约束问题求解。（SUMT：Sequential Unconstrained Minimization Technique）（1）外点法）外点法ljxgmixhtsxfji,1,0)(,1,0)(.)(min 记可行域为记可行域为 D成成为为极极小小点点。数数值值很很大大，因因而而不不可可能能时时，对对应应的的目目标标函函的的目目标标函函数数值值为为时时，对对应应束束问问题题，使使得得出出发发点点：构构造造一一个个无无约约DxxfDx ;)(构造罚函数构造罚函数 DxcDxxp,0)(其中其中 c 是充分大的正数

15、。是充分大的正数。考虑无约束问题考虑无约束问题)()()(minxpxfxF F(x)称为增广目标函数，它的极小点也是原问题的极称为增广目标函数，它的极小点也是原问题的极小点，但小点，但 F(x)不能保持原目标函数不能保持原目标函数 f(x)可能具有的良可能具有的良好性态（如连续、光滑），因为好性态（如连续、光滑），因为 F(x)在可行域在可行域 D 的边的边界上发生跳跃。界上发生跳跃。另构造罚函数另构造罚函数2)(112)(,0min)()(ljjmiicxgcxhcxp增广目标函数增广目标函数)()()(minxpxfxFcc c 称为罚因子。称为罚因子。连连续续（可可导导）。（可可导导）

16、，则则连连续续和和性性质质：如如果果)(),1()(),1()(xpljxgmixhcji 的的最最优优解解。也也是是则则，的的最最优优解解，且且是是性性质质：设设)(min)(*)(*)(min)(*xfcxDcxxFcxDxc 。题题然然后后解解一一系系列列无无约约束束问问），（趋趋于于列列递递增增的的数数求求解解困困难难，因因此此常常取取一一会会造造成成无无约约束束问问题题实实际际计计算算中中，过过大大的的足足够够大大时时才才成成立立，但但在在仅仅在在一一般般说说来来，)(min)(min)(*xcFcxFccDcxkkc 01.)(2)(min.212221 xxtsxx例例 1)1(

17、)(2)(1)(2)(1,0min)(2)()(.2122122212122212122212)(xxxxcxxxxxxxxcxxxFc解解 1)1(2212)(212112111xxxxcxxxxxxFc 1)1(2414)(212122122xxxxcxxxxxxFc，因因此此称称为为外外点点法法。的的外外部部趋趋向向从从可可行行域域连连续续，则则和和、设设*)(*),1()(),1()()(xDcxljxgmixhxfkji 无无解解；时时，0)()(11121 xxFxxFxxcc得得由由时时，,0)()(11121 xxFxxFxxcc 0)1(240)1(22212211xxcxx

18、xcxccxccx32,32221 31,3221 xxc时时，.31,32*x（2）内点法）内点法D DintDDintD 可可行行域域0)(|xgjxDj使使得得至至少少有有一一个个边边界界0)(|jxgxDintj ，内内部部内点法的迭代点列在可行域的内部移动，并对接近可内点法的迭代点列在可行域的内部移动，并对接近可行域边界的点施加越来越大的惩罚，对可行域边界上行域边界的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比在边界上筑一道墙阻的点施加无限大的惩罚，这好比在边界上筑一道墙阻止迭代点穿越边界。止迭代点穿越边界。内点法要求可行域的内点集合非空，并且要求初始点内点法要求

19、可行域的内点集合非空，并且要求初始点必须是内点，因此内点法只能处理不等式约束。必须是内点，因此内点法只能处理不等式约束。mixgtsxfi,1,0)(.)(min miicmiicxgcxBxgcxB11)(ln)()(1)(或或设设)()()(minxBxfxFcc 考考虑虑无无约约束束问问题题可可行行域域的的内内部部。的的极极小小点点将将落落在在原原问问题题因因此此无无限限增增大大，界界时时，从从可可行行域域的的内内部部趋趋向向边边当当)()(xFxBxcc。题题然然后后解解一一系系列列无无约约束束问问减减趋趋于于零零的的罚罚参参数数单单调调递递的的影影响响，为为此此设设置置一一列列须须尽

20、尽可可能能减减弱弱因因此此必必的的目目标标是是另另一一方方面面，由由于于原原问问题题)()()(min,)(,)(minxBxfxFcxBxfkkcckc 。收收敛敛于于产产生生的的点点列列则则内内点点法法连连续续、收收敛敛性性：若若*)(*,),1()()(xcxmixgxfki 0)()(21.32min.222121 xxtsxx例例 222121)()(21ln32)(.xxcxxxFc 解解，由由0)()(2142)(222111 xxcxxxFc得得，0)()(2123)(222122 xxcxxxFc11113311112221 ccxccx，113,111021 xxc时时，.113,111*x