第章 约束最优化方法
第 六 章 约束最优化方法
第六章约束最优化方法 问题 mIn feh)s.t.g(x)≤0 分量形式略 h(x)=0 约束集S={xg(x)≤0,h(x)=0 61Kuhn- Tucker条件 等式约束性问题的最优性条件: 考虑 (fh) min f(x) t.h(x)=0 回顾高等数学中所学的条件极值: 问题求(xy极值 即 min f(x, y) 在p(x,y)=0的条件下。 St.φ(x,y)=0 引入 Lagrange乘子: Lagrange函数L(xy:)=f(xy)+(x,y
第六章 约束最优化方法 问题 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) 即
第六章61 Kuhn-Tucker条件 等式约束性问题的最优性条件:(续) 若(xxy-)是条件极值,则存在x,使 f(xy)+中x(xx)=0 ∫xy)+中x)=0 Φ(xxy)=0 推广到多元情况,可得到对于(h)的情况: min f(x) 分量形式: s.b(④)=0j=1,2,…, 若x是ih)的0pt.,则存在o∈R使 了(x")+∑oVh,(x")=O 矩阵形式: VfO)+ Oh(
第六章 6.1 Kuhn-Tucker 条件 一、等式约束性问题的最优性条件： (续) 若(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使 矩阵形式： 分量形式： = + = l j f x j hj x 1 * * * ( ) ( ) 0 0 ( ) ( ) * * * = + x h x f x
第六章61Kuhn- Tucker条件 等式约束性问题的最优性条件:(续) 几何意义是明显的:考虑一个约束的情况: Vf(x* h(x) 这里 opt.Vfx*与 又) Vh为共线,而又非opt 又 h(xx Vf又)与Vh(又)不共线 Vh(又) 最优性条件即: Vf(x*)=∑UVh(x
一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况： 最优性条件即： 第六章 6.1 Kuhn-Tucker 条件 -▽f(ㄡ ) ㄡ ▽h(ㄡ ) h(x) -▽f(x*) ▽h(x*) 这里 x* ---l.opt. ▽f(x*)与 ▽h(x*) 共线，而ㄡ非l.opt. ▽f(ㄡ )与▽h(ㄡ )不共线。 = = − h j f x j hj x 1 * ( *) ( *)
第六章61 Kuhn-Tucker条件 、不等式约束问题的Khun- Tucker条件: 考虑问题 min f(c) t 8A(x)≤0 ,2 9·.· 设xx∈S={gAx)≤0i=1,2,…,m} F={g(x3)=0÷=1,2,…,m 称/为x点处的起作用集(紧约束集)。 如果x*是.opt.,对每一个约束函数来说,只有当它是起作用约 束时,才产生影响,如: g2(x)=0 g1(x米)=0,8为起作用约束 gIr
第六章 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)=0 x* g1 (x)=0 g1 (x*)=0, g1为起作用约束
第六章61Kuhn- Tucker条件 二、不等式约束问题的Khun- Tucker条件:(续) 特别有如下特征:如图 Y又) glx g(又) 在 f(x)+Vg(x=2)=0u-0 要使函数值下降,必须使g(x值变大, 在叉点使f(x)下降的方向(-V又)方向)指向约束集合内 部,因此又不是Lopt
第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的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*)
第六章61Kuhn- Tucker条件 二、不等式约束问题的Khun- Tucker条件:(续) 定理(最优性必要条件):(KT条件) 问题(g),设S=!x)≤0x*∈S为x点处的起作用集,设, gx),∈Ix点可微,g{),1*点连续。 向量组{Vgx,∈线性无关。 如果xx-0pt那么,彐u≥0,i∈使 vf(x)+∑uVg1(x)=0 如果在x,g(x)可微,∨i。那么 Vf(x)+∑uVg,(x)=0 LL:≥0 m(互补松弛条件) 满足K-T条件的点x“称K一T点
第六章 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*i≥0, i ∈I使 满足 条件的点 称 点。 互补松弛条件 如果在 可微， 。那么， K T x K T u g x i m u i m f x u g x x g x i f x u g x i i i m i i i i i I i i − − = = = + = + = = * * 1 * ( ) 0 1,2, , ( ) 0 1,2, , ( ) ( ) 0 , ( ) ( ) ( ) 0
第六章61 Kuhn-Tucker条件 不等式约束问题的Khun- Tucker条件:(续) f(x12x2)=(x1-3)2+(x2-2) g1( x十 5≤0 例 +2 4≤0 83( 1>2 O ≤O g21(x* (3,2) glx")
第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件：（续） = − = − = + − = + − = − + − ( , ) 0 ( , ) 0 ( , ) 2 4 0 . . ( , ) 5 0 min ( , ) ( 3) ( 2) 4 1 2 2 3 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 2 2 1 2 1 g x x x g x x x g x x x x st g x x x x f x x x x 例 1 2 3 4 1 2 g1=0 g2=0 g4=0 x1 g3=0 x2 x* ▽g2 (x*) ▽g1 (x*) -▽f(x*) (3,2)T
第六章61 Kuhn-Tucker条件 、不等式约束问题的Khun- Tucker条件:(续) 在x”点 81( 0交 点(2,1) 起作用集I={1,2} )=0 Vg1(x*)=(2x1,2x2)=(4,2) Vf(x")=(2(x1-3),2(x2-2)) 计算可得 3使 Vf(x)+Vg1(x)+3Vg2(x”)=0 用KT条件求解 2(x1-3) Vf( Vg() Vg2(2) O Vg3(x) O V84
第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件：（续） 用K-T条件求解： ( ) ( ) ( ) 0 ( ) (2( 3),2( 2)) ( 2, 2) ( ) (1,2) ( ) (2 ,2 ) (4,2) 2 1 {1,2} ( , ) 0 ( , ) 0 3 2 2 3 1 * 1 3 * 2 3 2 * 1 1 * 2 * 1 * 2 1 1 2 2 1 2 1 1 2 * + + = = = = − − = − − = = = = = = f x g x g x u u f x x x g x g x x x I g x x g x x x T T T T T T 计算可得 使 交点（ ，） 起作用集 在 点 − = − = = = − − = 1 0 , 0 1 ( ) 2 1 , (2) 2 2 , ( ) 2( 2) 2( 3) ( ) 3 4 2 2 1 1 2 1 g x g g x x g x x x f x
第六章61Kuhn- Tucker条件 、不等式约束问题的Khun- Tucker条件:(续) VoX)+> (x)=O ,≥O,i=1 (x)=O 2(x1-3)+12x1+ 0 2(x2-2)+112x2+2l2 0 (2) (x1+x2-5)=0 (3) (x1+2x2-4)=0 (4) l2x1=0 5 6个方程6个未知量
第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件：（续） → = = + = ( ) 0 0, 1,2, , ( ) ( ) 0 u g x u i m f x u g x i i i m i i i = = + − = + − = − + + − = − + + − = 6个方程6个未知量 0 (6) 0 (5) ( 2 4) 0 (4) ( 5) 0 (3) , , , 0 2( 2) 2 2 0 (2) 2( 3) 2 0 (1) 4 2 3 1 2 1 2 2 2 2 1 1 1 2 3 4 2 1 2 2 4 1 1 1 2 3 u x u x u x x u x x u u u u x u x u u x u x u u