文档介绍：§ § 约束最优化方法约束最优化方法 Linear Programming 运筹学课件 1 、约束问题的最优性条件令, ,},..., 2,1{},..., 2,1{qJpI??则对任意 Xx?* ,有 IixgJjxh i j????,0)(,,0)( * * 称使0)( *?xg i 的约束 0)( *?xg i 为点*x 的一个积极约束。点*x 的所有积极约束的下标集记为},0)(|{)( **IixgixI i????????????qjxh pixgts xf j i,,1,0)( ,,1,0)(.. )( min ??qjRRh piRRg RRf Rxxx nj ni n nTn,..., 1,: ,..., 1,: : ),,( 1????????( MP) 其中????????????????qjxh pixgRxX j in,..., 1,0)( ,..., 1,0)( 例 ( ) 比如????????????????02)( 01)(.. )2(),( min 21 2 211 22 2121xxxg xxxgts xxxxf 显然Tx)0,0( *?是该问题的一个可行点。所以?)( *xI 下标集}2{ 定理 设RRf n?: 和)(,: *xIiRRg ni??在点*x 处可微, )(\, *xIIig i?在点*x 处连续, JjRRh nj?,:?在点*x 处连续可微,并且各 JjxhxIixg j i????),( ),( ),( *** 线性无关。若*x 是(MP) 的局部最优解,则存在两组实数)(, **xIi i??和Jj j?, *?,使得?????????????????)(,0 0)()()( * * ** )( *** *xIi xhxgxf i Jj jj xIi ii???( ) ( )称为(MP) 的 Kuhn - Tucker 条件,简称为 K-T 条件。凡是满足 K-T 条件( )的可行点 x 叫做(MP) 的K-T点。注:很多约束最优化方法就是寻找(MP) 的K-T 点。问题() 问题若进一步要求每个 Iixg i?),( 在点*x 处都可微,则(MP) 的 K-T 条件可写为更简便的形式???????????????????????},,1{,0 },,1{,0)( 0)()()( * ** *****pIi pIixg xhxgxf i ii Jj jj Ii ii??????( ) 其中},,,1{,0)( **pIixg ii?????称为互补松紧条件。注:对Jj j?, *?没限制。)(\ *xIIi?引进(MP) 的 Lagrange 函数??????? qj jj pi iixhxgxfxL 1 1)()()(),,(????其中, Tq Tp),,(,),,( 1 1??????????叫做 Lagrange 乘子。则(MP) 的K-T 条件( )可写?????????????},,1{,0 },,1{,0)( 0),,( * ** ***pIi pIixg xL i ii x??????( ) 定理 对于(MP) 问题,若 JjhIigf ji??,,,, 在点*x 处连续可微,可行点*x 满足(MP) 的K-T 条件,且)(,, *xIigf i?是凸函数, Jjh j?, 是线性函数,则*x 是(MP) 的整体最优解。() 例用 K-T 用K-T 条件解下列问题????????????????????????????01)( 0)( 0)( 02)(.. )2()1(),( min 211 23 12 211 22 2121xxxh xxg xxg xxxgts xxxxf ( ) 解:问题( )的 Lagrange 函数为)1()( )()2()2()1(),,( 2123 12211 22 21???????????????xxx xxxxxxL??????所以?????????? 2111)1(2xx L?????????? 3122)2(2xx L Lagrange 因此,问题( )的 K-T 条件是?????????????????????????????0,, 0)( 0)( 0)2( 0 )2(2 0 )1(2321 23 12 211 312 211????????????x x xx x x 作为 K-T 点还应满足可行性条件??????????????0,0 01 02 21 21 21xx xx