K-T条件与罚函数法解析

非线性规划及其应用——Kuhn-Tucker理论、罚函数法Kuhn-Tucker理论Kuhn-Tucker条件（或称Karush-Kuhn-Tucker条件）是将等式约束的Lagrange乘子法推广到不等式约束，不必加入剩余变量。Kuhn-Tucker条件是确定约束极值点的必要条件，对于凸规划来说同时也是充分条件。二、不等式约束问题的Kuhn-Tucker条件：NLP问题minf(x)s.t.hi(x)=0i=1,2,.....,mgj(x)≤0j=1,2,…,p设x*∈S={x|gj(x)≤0j=1,2,…,p}令J={j|gj(x*)=0j=1,2,…,p}称J为x*点处的起作用集（紧约束集）。如果x*是最优值,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：(fg)g2(x)=0x*g1(x)=0g1(x*)=0,g1为起作用约束二、不等式约束问题的Kuhn-Tucker条件：定理（最优性必要条件）：（K-T条件）问题(fg),设S={x|gj(x)≤0},X*∈S,J为X*点处的起作用集，设f(x),hi(x),gj(x),j∈J在X*点可微,gj(x),hi(x)在X*点连续。向量组{▽hi(X*)},{▽gj(X*)}线性无关。如果X*是极小点且满足正则条件,则必存在λ*=(λ1,λ2,...,λm)T,γ*=(γ1,γ2,...γP)T,使得以下各式成立：Jj库恩-塔克条件应用举例若给定优化问题的数学模型为22122minfxxx..st211210gxxx223100gxxgxx***01,2,...,00jjjJiijjdfxdgxindxdxgxjJjJK-T条件库恩-塔克条件的几何意义：在约束极小点处，函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。下面以二维问题为例，说明K-T条件的几何意义二、约束极值点的二阶充分条件前面我们讨论了两类最优化问题：约束极值问题及非线性规化问题，并且给出了求解两类问题的拉格朗日方法和库恩－塔克条件。不过，从求解的过程看，无论是前面梯度向量的角度，还是后面等式约束问题的拉格朗日方法、非线性规划的库恩－塔克条件，我们都只是分析了在最优解处应满足的性质，而并没有保证满足此性质的点一定是最优解，比如最大值问题和最小值问题的一阶条件是相同的，或者说由拉格朗日方法推导出的一阶条件和库恩－塔克条件只是解的必要条件。为此，我们需要找到新的条件，以保证由一阶必要条件所求得的解就是此最优规划问题的最优解，这就是二阶条件的讨论。对于凸规划来说，Kuhn-Tucker点事其全局极小点，但是对目标函数、约束函数的要求比较严格，实际情况难以满足，这可以用二阶充分条件来进行检验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的子集。)(Xg-)(Xh-)f(X=γ*)λ*,(X*,H*j2p1j**i2m1i*i*2Lj罚函数法约束最优化问题基本思想无约束最优化问题利用问题的目标函数和约束函数构造新的目标函数——罚函数（penaltyfunction）P(X,R)=f(X)+Q(R,h(X),g(X))式中Q是惩罚项，是惩罚参数R和约束的函数。一般形式Sequentialunconstrainedminimizationtechnique序列无约束最小化技术混合罚函数法外点罚函数法内点罚函数法罚函数法内点罚函数法mixgtsxfi,,2,10)(..)(min是连续函数。其中),,2,1)((),(mixgxfi基本思想:迭代总是从内点出发,并保持在可行域内部进行搜索.niExmixgxS,,,2,1,0)(|int|()0,1,2,,,niSxgximxE罚(障碍)函数)()(),(xrBxfrxG。趋向可行域边界时，当点是连续函数；它满足两个条件：定义在可行域内部，是很小的正数，其中)()2()()1()(xBxxBxBr两种最重要的形式:miimiixgxBxgxB11)(ln)()(1)(对数障碍函数障碍因子倒数障碍函数min..10xstx1(),1(,)1BxxrGxrxx取则内罚函数为210(1)()10()1*.Grxxxxrrrxrx令得到当时，有两种障碍函数的比较min..10xstx()ln1,(,)ln1BxxGxrxrx取则内罚函数为101()10()1*.Grxxxxrrrxrx令得到当时，有两种障碍函数的比较例:考虑约束优化问题1..2minxtsx)1ln(2),(xrxrxG该问题的对数障碍函数为(,):121(0)11(,)ln2(0)22rrGxrxrrGxrrrrr的最小点为mixgtsxfi,,2,10)(..)(minSxtsxrBxfrxGint..)()(),(minSxtsxBrxfrxGkkint..)()(),(min的障碍因子数列。为严格单调减且趋于其中0kr步骤:。置缩小系数，初始参数，允许误差给定初始点1),1,0(,0int.11)0(krSx。设其极小点为题为初始点，求解下列问以)()1(int..)()(min.2kkkxSxtsxBrxfx。，返回，置令；否则，，则停止计算，得到点若21:)(.31)()(kkrrxxBrkkkkk例:用内点法求解下列问题00..min122121xxxtsxx212121122112121212(,)lnln210,10311118,1184280*(0,0)kkkkkkkkTkGxrxxrxxrxxrrrGGxxxxxxxrxrxrrx解：定义障碍函数令当时，12131118,118428kkrxrxr12()()110.51.2520.50.3090.59530.250.1830.28340.10.0850.10750.000100kkkrxrxrx4x3x2x1求初始内点的迭代步骤。置如取任取0:),1(0,.100)0(krrExn.1,0)(|,1,0)(|.2)()(mixgiTmixgiSkikkik令。，停止计算；否则，转若4.3kSkikkTiikSiikTixgxRrxgrxgrxPkk0)(|~)0()(1)(),(~.4记构造函数。，转得的极小点域内，求障碍函数为初始点，在以6~..),(~min:),(~~.5)1()(kkkkkkxRxtsrxPrxPRx。转，置如取令21:,1010.611kkrrrrkkkk内点罚函数法优点内点罚函数法缺点迭代总在可行域内进行，每一个中间结果都是可行解，可以作为近似解。选取初始可行点较困难，且只适用于含不等式约束的非性性规划问题。外点罚函数法ljxhmixgtsxfAji,,2,10)(,,2,10)(..)(min)()},,2,1(0)(),,,2,1(0)(|{),,2,1)((),,,2,1)((),(ljxhmixgxSEljxhmixgxfjinji上连续。在其中引入罚项00)(00)(00)(00)()(),()()()(11yyyyyyyyyyxhxgxpljjmii当当当当是连续函数，且满足其中。均为给定常数，通常取其中的典型取法：和函数21,1)()()(,0max)(xhxhxgxgjjiiljxhmixgtsxfji,,2,10)(,,2,10)(..)(min)()(),(minxpxfxFmiljjixhxgxfxF11)()()(),(min是很大的正数。其中01)(..)1()(min22221xxgtsxxxf1)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混合法混合法是将内点法和外点法的惩罚项形式结合在一起，用于解决同时包含等式约束和不等式约束的NLP问题。其中不等式约束的惩罚项采用内点法的形式，而等式约束的惩罚项采用外点法的形式。其罚函数为：混合法的求解与内点法类似，初始点应在可行域内，在迭代过程中惩罚因子逐渐减小，当Rk0时，罚函数在可行域内的极值点纪委f(X)的约束极值点。m1ii0.5kp1jjkkm1ii0.5kp1jjkk22(X)hR(X)g1R-f(X)=)RP(X,(X)hR(X)glnR-f(X)=)RP(X,或