K-T条件与罚函数法

1、非线性规划及其应用非线性规划及其应用Kuhn-Tucker理论、 罚函数法Kuhn-Tucker理论理论Kuhn-Tucker条件（或称Karush-Kuhn-Tucker条件）是将等式约束的Lagrange乘子法推广到不等式约束，不必加入剩余变量。Kuhn-Tucker条件是确定约束极值点的必要条件，对于凸规划来说同时也是充分条件。二、二、不等式约束问题的不等式约束问题的Kuhn-Tucker条件：条件： NLP问题问题 min f(x) s.t. hi(x)=0 i=1,2,.,m gj(x)0 j=1,2, ,p 设设 x*S=x|gj(x) 0 j=1,2, ,p 令令 J=j| gj

2、(x*) =0 j=1,2, ,p 称称J为为 x*点处的起作用集（紧约束集）。点处的起作用集（紧约束集）。 如果如果x*是是最优值最优值,对每一个约束函数来说，只有当它是起作用对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：约束时，才产生影响，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1为起作用约束二、二、不等式约束问题的不等式约束问题的Kuhn-TuckerKuhn-Tucker条件条件： 定理（最优性必要条件）：定理（最优性必要条件）： （K-TK-T条件）条件） 问题问题(fg), (fg), 设设S=S=x x|g|gj j(x)0,(x)0,

3、X X* *S,S,J J为为X X* *点处的起作用集，点处的起作用集，设设f f(x)(x), ,h hi i(x),(x),g gj j(x)(x),j,jJ J在在X X* *点可微点可微, ,g gj j(x)(x), h, hi i(x)(x)在在X X* *点连点连续。续。 向量组向量组 h hi i(X(X* *) ) , , g gj j( (X X* *)线性无关。线性无关。 如果如果X X* *是极小点且满足正则条件是极小点且满足正则条件, ,则必存在则必存在* *=(=(1 1,2 2,.,.,m m) )T, ,* *=(=(1 1,2 2,.,.P) )T,使得以下

4、各式成立：使得以下各式成立：Jj库恩-塔克条件应用举例若给定优化问题的数学模型为 22122minf xxx. .st 211210gxxx 223100gxxgxx *01,2,.,00jjj Jiijjdf xdgxindxdxgxjJjJK-T条件库恩-塔克条件的几何意义：在约束极小点处，函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。下面以二维问题为例，说明K-T条件的几何意义二、约束极值点的二阶充分条件二、约束极值点的二阶充分条件 前面我们讨论了两类最优化问题：约束极值问题及非线性规化问题，并且给出了求解两类问题的拉格朗日方法和库恩塔克条件。 不过，从求解的过程看，无

5、论是前面梯度向量的角度，还是后面等式约束问题的拉格朗日方法、非线性规划的库恩塔克条件，我们都只是分析了在最优解处应满分析了在最优解处应满足的性质，而并没有保证满足此性质的点一定是最优解足的性质，而并没有保证满足此性质的点一定是最优解，比如最大值问题和最小值问题的一阶条件是相同的，或者说由拉格朗日方法推导出的一阶条件和库恩塔克条件只是解的必要条件。为此，我们需要找到新的条件，以保证为此，我们需要找到新的条件，以保证由一阶必要条件所求得的解就是此最优规划问题的最优解，由一阶必要条件所求得的解就是此最优规划问题的最优解，这就是二阶条件的讨论这就是二阶条件的讨论。 对于凸规划来说，Kuhn-Tucke

6、r点事其全局极小点，但是对目标函数、约束函数的要求比较严格，实际情况难以满足，这可以用二阶充分条件来进行检验Kuhn-Tucker点是否是局部极小点。 对于前述NLP问题，如果目标函数、约束函数均二阶连续可微，可行点X*是严格局部极小点的二阶充分条件为： （1）存在(*,*),使(X*,*,*)是一个Kuhn-Tucker点，既满足Kuhn-Tucker条件。对于满足条件 的非0向量Y所形成的子空间M上,有 YTHL (X*,*,*)Y0 (d)即L(X,)的黑塞矩阵 在子空间M上正定,式中A(X*)为X*出起作用的不等式约束的下标集，J+,J0分别是A(X*)的满足条件j*0,j*=0的子集

7、。)(Xg-)(Xh-)f(X=*)*,(X*, H*j2p1j*i2m1i*i*2Lj罚函数法罚函数法约束最优化问题约束最优化问题 基本思想基本思想 无约束最优化问题无约束最优化问题 利用问题的目标函数和约束函数构造新的目标函数利用问题的目标函数和约束函数构造新的目标函数 罚函数罚函数（penalty function） P(X,R)=f(X)+Q(R,h(X),g(X) 式中式中Q是惩罚项，是惩罚参数是惩罚项，是惩罚参数R和约束的函数和约束的函数。一般形式一般形式Sequential unconstrained minimization technique序列无约束最小化技术混合罚函数法外

8、点罚函数法内点罚函数法罚函数法内点罚函数法mixgtsxfi, 2 , 10)(. .)(min是连续函数。其中), 2 , 1)(),(mixgxfi基本思想: 迭代总是从内点出发,并保持在可行域内部进行搜索. niExmixgxS, 2 , 1, 0)(|int|( )0,1,2,niSx g xim xE罚(障碍)函数)()(),(xrBxfrxG。趋向可行域边界时，当点是连续函数；它满足两个条件：定义在可行域内部，是很小的正数，其中)()2()() 1 ()(xBxxBxBr两种最重要的形式:miimiixgxBxgxB11)(ln)()(1)(对数障碍函数障碍因子倒数障碍函数min.

9、 .10 xs tx1( ),1( , )1B xxrG x rxx 取则 内 罚 函 数 为210(1)( )10( )1*.Grxxxx rrrx rx 令得到当时，有两种障碍函数的比较min. .10 xs tx ( )ln1 ,( , )ln1B xxG x rxrx 取则内罚函数为101( )10( )1*.Grxxxx rrrx rx 令得到当时，有两种障碍函数的比较例:考虑约束优化问题1. .2minxtsx) 1ln(2),(xrxrxG该问题的对数障碍函数为( , ):121(0)11(, )ln2(0)22rrG x rxrrG x rrrrr 的最小点为mixgtsxfi

10、, 2 , 10)(. .)(minSxtsxrBxfrxGint. .)()(),(minSxtsxBrxfrxGkkint. .)()(),(min 的障碍因子数列。为严格单调减且趋于其中0kr步骤:。置缩小系数，初始参数，允许误差给定初始点1),1, 0(,0int. 11)0(krSx。设其极小点为题为初始点，求解下列问以)()1(int. .)()(min. 2kkkxSxtsxBrxfx。，返回，置令；否则，则停止计算，得到点若21:)(. 31)()(kkrrxxBrkkkkk例:用内点法求解下列问题00. .min122121xxxtsxx212121122112121212(

11、 , )lnln210,10311118,1184280*(0,0)kkkkkkkkTkG x rxxrxxrxx rrrGGxxxxxxxrxrxrrx 解：定义障碍函数令当时，1213111 8,11 8428kkrxrxr 12( )( )110.51.2520.50.3090.5953 0.250.1830.28340.10.0850.1075 0.000100kkkrx rx rx4x3x2x1求初始内点的迭代步骤。置如取任取0:),1(0,. 100)0(krrExn.1, 0)(|,1, 0)(|. 2)()(mixgiTmixgiSkikkik令。，停止计算；否则，转若4. 3

12、kSkikkTiikSiikTixgxRrxgrxgrxPkk0)(|)0()(1)(),(. 4记构造函数。，转得的极小点域内，求障碍函数为初始点，在以6. .),(min:),(. 5)1()(kkkkkkxRxtsrxPrxPRx。转，置如取令21:,1010. 611kkrrrrkkkk内点罚函数法优点内点罚函数法缺点 迭代总在可行域内进行，每一个中间结果都是可行解，可以作为近似解。 选取初始可行点较困难，且只适用于含不等式约束的非性性规划问题。 外点罚函数法ljxhmixgtsxfAji, 2 , 10)(, 2 , 10)(. .)(min)(), 2 , 1(0)(), 2 ,

13、1(0)(|), 2 , 1)(), 2 , 1)(),(ljxhmixgxSEljxhmixgxfjinji上连续。在其中引入罚项00)(00)(00)(00)()(),()()()(11yyyyyyyyyyxhxgxpljjmii当当当当是连续函数，且满足其中。均为给定常数，通常取其中的典型取法：和函数21, 1)()()(, 0max)(xhxhxgxgjjiiljxhmixgtsxfji, 2 , 10)(, 2 , 10)(. .)(min)()(),(minxpxfxFmiljjixhxgxfxF11)()()(),(min是很大的正数。其中01)(. .) 1()(min2222

14、1xxgtsxxxf1) 1() 1(1) 1() 1(, 0max) 1(),(222222122221222221xxxxxxxxxxxF解：定义罚函数12120011()11FFxxxxx 令得1) 1(2212) 1(222222211xxxxxxFxxF外点法迭代步骤:。，置，允许误差系数，放大，初始罚因子给定初始点101) 1(0. 111)0(kcx。设其极小点为问题为初始点，求解无约束以)()1()()(min. 2kkkxxpxfx。，返回，置令；否则，则停止计算，得到点若21:)(. 31)()(kkcxxpkkkkk混合法混合法 混合法是将内点法和外点法的惩罚项形式结合在