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,使得以下各式成立：库恩-塔克条件应用举例假设给定优化问题的数学模型为K-T条件库恩-塔克条件的几何意义：在约束极小点处，函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。下面以二维问题为例，说明K-T条件的几何意义二、约束极值点的二阶充分条件前面我们讨论了两类最优化问题：约束极值问题及非线性规化问题，并且给出了求解两类问题的拉格朗日方法和库恩－塔克条件。不过，从求解的过程看，无论是前面梯度向量的角度，还是后面等式约束问题的拉格朗日方法、非线性规划的库恩－塔克条件，我们都只是分析了在最优解处应满足的性质，而并没有保证满足此性质的点一定是最优解，比方最大值问题和最小值问题的一阶条件是相同的，或者说由拉格朗日方法推导出的一阶条件和库恩－塔克条件只是解的必要条件。为此，我们需要找到新的条件，以保证由一阶必要条件所求得的解就是此最优规划问题的最优解，这就是二阶条件的讨论。

对于凸规划来说，Kuhn-Tucker点事其全局极小点，但是对目标函数、约束函数的要求比较严格，实际情况难以满足，这可以用二阶充分条件来进行检验Kuhn-Tucker点是否是局部极小点。对于前述NLP问题，如果目标函数、约束函数均二阶连续可微，可行点X*是严格局部极小点的二阶充分条件为：〔1〕存在(λ*,γ*),使(X*,λ*,γ*)是一个Kuhn-Tucker点，既满足Kuhn-Tucker条件。对于满足条件

的非0向量Y所形成的子空间M上,有YTHL(X*,λ*,γ*)Y>0(d)即L(X,λ,γ)的黑塞矩阵

在子空间M上正定,式中A(X*)为X*出起作用的不等式约束的下标集，J+,J0分别是A(X*)的满足条件γj*>0,γj*=0的子集。罚函数法约束最优化问题

根本思想无约束最优化问题

利用问题的目标函数和约束函数构造新的目标函数——罚函数〔penaltyfunction〕

P(X,R)=f(X)+Q(R,h(X),g(X))

式中Q是惩罚项，是惩罚参数R和约束的函数。一般形式Sequentialunconstrainedminimizationtechnique序列无约束最小化技术内点罚函数法根本思想:迭代总是从内点出发,并保持在可行域内部进行搜索.罚(障碍)函数两种最重要的形式:对数障碍函数障碍因子倒数障碍函数两种障碍函数的比较两种障碍函数的比较例:考虑约束优化问题该问题的对数障碍函数为步骤:例:用内点法求解以下问题x4x3x2x1求初始内点的迭代步骤内点罚函数法优点内点罚函数法缺点

迭代总在可行域内进行，每一个中间结果都是可行解，可以作为近似解。

选取初始可行点较困难，且只适用于含不等式约束的非性性规划问题。外点罚函数法引入罚项外点法迭代步骤:混合法

混合法是将内点法和外点法的惩罚项形式结合在一起，用于解决同时包含等式约束和不等式约束的NLP问题。其中不等式约束的惩罚项采用内点法的形