非线性规划及其应用,——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(x*) =0 j=1,2, …,p}称J为 x*点处的起作用集（紧约束集）如果x*是最优值,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：,g2(x)=0,二、不等式约束问题的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的子集罚函数法,约束最优化问题,基本思想,无约束最优化问题,利用问题的目标函数和约束函数构造新的目标函数——罚函数（penalty function）,,,P(X,R)=f(X)+Q(R,h(X),g(X))式中Q是惩罚项，是惩罚参数R和约束的函数一般形式,Sequential unconstrained minimization technique 序列无约束最小化技术,内点罚函数法,基本思想: 迭代总是从内点出发,并保持在可行域 内部进行搜索.,罚(障碍)函数,两种最重要的形式:,对数障碍函数,障碍因子,倒数障碍函数,两种障碍函数的比较,两种障碍函数的比较,例:考虑约束优化问题,该问题的对数障碍函数为,,步骤:,例:用内点法求解下列问题,,,,,,,,x4,x3,x2,x1,,,,,求初始内点的迭代步骤,内点罚函数法优点,内点罚函数法缺点,迭代总在可行域内进行，每一个中间结果都是 可行解，可以作为近似解。
选取初始可行点较困难，且只适用于含不等式 约束的非性性规划问题外点罚函数法,引入罚项,,外点法迭代步骤:,混合法,混合法是将内点法和外点法的惩罚项形式结合在一起，用于解决同时包含等式约束和不等式约束的NLP问题其中不等式约束的惩罚项采用内点法的形式，而等式约束的惩罚项采用外点法的形式其罚函数为：混合法的求解与内点法类似，初始点应在可行域内，在迭代过程中惩罚因子逐渐减小，当Rk 0时，罚函数在可行域内的极值点纪委f(X)的约束极值点谢谢！不足之处，请批评指正。