最优性条件(非线性规划)kuhn-tucker条.ppt

非线性规划非线性规划最优性条件最优性条件（（Kuhn-Tucker 条件）条件）数学规划数学规划约束集或可行域约束集或可行域MP的可行解或可行点的可行解或可行点向量化表示向量化表示当当p=0,q=0时，称为时，称为无约束非线性规无约束非线性规划划或者或者无约束最优化问题无约束最优化问题否则，称为否则，称为约束非线性规划约束非线性规划或者或者约束约束最优化问题最优化问题非线性规划方法概述非线性规划方法概述 问题问题 min f(x) s.t. g(x) ≤0 h(x)=0 约束集约束集 S={x|g(x) ≤0 , h(x)=0} 一、等式约束问题的最优性条件：一、等式约束问题的最优性条件： 考虑考虑 min f(x) s.t. h(x)=0 回顾高等数学中所学的条件极值：回顾高等数学中所学的条件极值： 问题问题 求求z=f(x,y)极值极值 min f(x,y) 在在ф(x,y)=0的的条件下。

条件下 S.t. ф(x,y)=0 引入引入Lagrange乘子：乘子：λ Lagrange函数函数 L(x,y;λ)= f(x,y)+ λ ф(x,y)(fgh)(fh)即一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件： (续续)若若(x*,y*)是条件极值，则存在是条件极值，则存在λ* ，，使使 fx(x*,y*)+ λ* фx (x*,y*) =0 fy(x*,y*)+ λ* фy(x*,y*) =0 Ф (x*,y*)=0 推广到多元情况，可得到对于推广到多元情况，可得到对于(fh)的情况：的情况： min f(x) s.t. hj(x)=0 j=1,2, …,l 若若x*是是(fh)的的l.opt. ,则存在则存在υ*∈∈ Rl使使 矩阵形式：矩阵形式：分量形式：一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件： (续续) 几何意义是明显的：考虑一个约束的情况：几何意义是明显的：考虑一个约束的情况： 最优性条件即：最优性条件即：-▽f(ㄡ )ㄡ ▽h(ㄡ )h(x)-▽f(x*)▽h(x*)这里 x* ---l.opt. ▽f(x*)与▽h(x*) 共线，而ㄡ非l.opt.▽f(ㄡ )与▽h(ㄡ )不共线。

二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件：考虑问题考虑问题 min f(x) s.t. gi(x) ≤0 i=1,2, …,m 设设 x*∈∈S={x|gi(x) ≤0 i=1,2, …,m} 令令 I={i| gi(x*) =0 i=1,2, …,m} 称称I为为 x*点处的起作用集（紧约束集）点处的起作用集（紧约束集） 如果如果x*是是l.opt. ,对每一个约束函数来说，只有当它是起作用约对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：束时，才产生影响，如：(fg)g2(x)=0x*g1(x)=0g1(x*)=0, g1为起作用约束二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续） 特别特别 有如下特征：如图有如下特征：如图 在在x* ：： ▽▽f(x*)+u* ▽▽g(x*)=0 u*>0 要使函数值下降，必须使要使函数值下降，必须使g(x)值变大，则值变大，则 在在ㄡㄡ 点使点使f(x)下降的方向（下降的方向（- ▽▽f(ㄡㄡ ) 方向）指向约束集合内方向）指向约束集合内部，因此部，因此ㄡㄡ不是不是l.opt. l.opt. 。

▽g(ㄡ )-▽f(ㄡ )X*-▽f(x*)▽g(x*)二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续） 定理（最优性必要条件）：定理（最优性必要条件）： （（K-T条件）条件） 问题问题(fg), 设设S={x|gi(x) ≤0},x*∈∈S,I为为x*点处的起作用集，点处的起作用集，设设f, gi(x) ,i ∈∈I在在x*点可微，点可微， gi(x) ,i I在在x*点点连续 向量组向量组{▽▽gi(x*), i ∈∈I}线性无关线性无关 如果如果x*----l.opt. 那么，那么， u*i≥0, i ∈∈I使使二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续）123412g1=0g2=0g4=0x1g3=0x2x*▽g2(x*)▽g1(x*)-▽f(x*)(2,2)T二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件： （续）（续）用用K-T条件求解：条件求解：二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件： （续）（续）二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续）可能的可能的K-T点出现在下列情况：点出现在下列情况： ①①两约束曲线的交点：两约束曲线的交点：g1与与g2,g1与与g3,g1与与g4,g2与与g3,g2与与g4,g3与与g4。

②②目标函数与一条曲线相交的情况：目标函数与一条曲线相交的情况： g1，，g2, g3, g4 对每一个情况求得满足对每一个情况求得满足(1)~(6)的点的点(x1,x2)T及乘子及乘子u1,u2,u3,u4,验证当满足可得，且验证当满足可得，且ui≥ 0时，即为一个时，即为一个K-T点下面举几个情况：下面举几个情况： ● g1与与g2交点：交点：x=(2,1)T∈∈S ,I={1,2} 则则u3=u4=0 解解二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续）●●二、不等式约束问题的二、不等式约束问题的Kuhn-Tucker条件：条件： （续）（续）●三、一般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件三、一般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件 (续续)。