1、第 六 章约束最优化方法第六章 约束最优化方法问题 min f(x)s.t. g(x) 0 分量形式略h(x)=0约束集 S=x|g(x) 0 , h(x)=0 6.1 Kuhn-Tucker 条件一、等式约束性问题的最优性条件：考虑 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)即第六章 6.1 Kuhn-Tucker 条件一、等式约束性问题的最优性条
2、件： (续 )若 (x*,y*)是条件极值，则存在 * ， 使fx(x*,y*)+ * x (x*,y*) =0fy(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使矩阵形式：分量形式：一、等式约束性问题的最优性条件： (续 )几何意义是明显的：考虑一个约束的情况：最优性条件即：第六章 6.1 Kuhn-Tucker 条件- f( ) h( )h(x)- f(x*) h(x*)这里 x* -l.opt. f(x*)与
3、h(x*) 共线，而 非 l.opt. f( )与 h( )不 共线。第六章 6.1 Kuhn-Tucker 条件二、不等式约束问题的 Khun-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为起作用约束第六章 6.1 Kuhn-Tucker 条件二、
4、不等式约束问题的 Khun-Tucker条件： （续）特别 有如下特征：如图在 x* ： f(x*)+u* g(x*)=0 u*0要使函数值下降，必须使 g(x)值变大，则在 点使 f(x)下降的方向（ - f( ) 方向）指向约束集合内部，因此 不是 l.opt. 。 g( )- f( ) X*- f(x*) g(x*)第六章 6.1 Kuhn-Tucker 条件二、不等式约束问题的 Khun-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*i0, i I使第六章 6.1 Kuhn-Tucker 条件二、不等式约束问题的 Khun-Tucker条件： （续）1 2 3 412g1=0 g2=0g4=0x1g3=0x2x* g2(x*) g1(x*)- f(x*)(3,2)T第六章 6.1 Kuhn-Tucker 条件二、不等式约束问题的 Khun-Tucker条件： （续）用 K-T条件求解：第六章 6.1 Kuhn-Tucker 条件二、不等式约束问题的 Khun-Tucker条件： （续）
