Lagrange函数 L(x,a)Jf(x)+∑ac(x)(an≥0i=1,2,…,p) L(x,un,v)=∫(x)+ug(x)+vh(x)(u≥0 Lagrange乘子:或v 互补松弛条件:cx)≤0,a1*20,a1n*c:(x)=0,=1,2,…,P 0rg(x*)≤0,ur*20,u*g(x)=0 VL(,,v)=0 Karush- Kuhn-Tucker条件—KKT条件 l20,ug(x)=0 约束规格——约束限制(规范)条件 h(x)=0 1)有效约束的梯度向量Vc(xi∈4(x*)线性无关; 2)所有约束都是线性函数; 3) 16
16 Lagrange函数 ( *) , * , * ( *) , , , , 0 0 0 1 2 i i i i c x c x i p = = ( , , ) 0 0, ( ) 0 ( ) 0 x T L x u v u u g x h x = = = Karush-Kuhn-Tucker条件——KKT条件 1 ( , )= ( ) ( ) ( 0, 1,2, , ) ( , , ) ( ) ( ) ( ) ( 0) p q i i i i T T L x f x c x i p L x u v f x u g x v h x u + = + = = + + Lagrange乘子： i 或u v ， 互补松弛条件： ( *) 0, * 0, * ( *) 0 = T or g x u u g x 约束规格——约束限制(规范)条件 1) 有效约束的梯度向量 ( *)( ( *)) i c x i A x 线性无关; 2) 所有约束都是线性函数； 3) ……
约束规划最优性充分条件 定理:(约束问题解的鞍点充分条件)对一般约束规划问题 mn s.g(x)≤0的L(x,a,B)=f(x)+a'g(x)+fTh(x),(a≥0) h(x)=0 若对x∈R",存在a0、B∈R使得 L(x,a,B)SL(x,a,B)sL(x,a,B,ⅵx∈S,a∈R,B∈R 则x∈R"是问题的整体最优解。 鞍点条件 证明:∵L(x,a,B)SL(x,,B),Va∈R,B∈R (a-a)8(x)+(-6)H(x)≥0,Va∈R,B∈R 由a≥0,的的任意性知:g(x)≤0,(x)=0且ag(x)=0或ag(x)=0 进一步由不等式的后两部分知:f(x)≤∫(x) 同时aB是max{L(x,a,B),x∈S}的最优解! 17
17 定理：(约束问题解的鞍点充分条件)对一般约束规划问题 min ( ) . . 0 ( ) 0 f x s t g(x) h x = 的 ( , , ) ( ) ( ) ( ), ( 0) T T L x f x g x h x = + + 若对 n x R ，存在 0、 q R 使得 ( , , ) ( , , ) ( , , ), , , p q L x L x L x x S R R + 则 n x R 是问题的整体最优解。 约束规划最优性充分条件 鞍点条件 , , max ( , , ), L x x S 同时 是 的最优解！ ( , , ) ( , , ), , p q 证明： L x L x R R + ( ) ( ) ( ) ( ) 0, , T T p q − + − g x h x R R + 由 0, 的任意性知: g x h x ( ) 0, ( ) 0 = 且 i i ( ) 0 ( ) 0 T g x g x = = 或 进一步由不等式的后两部分知: f x f x ( ) ( )
凸规划最优性充要条件 定理:对一般可微规划问题(f(x),c(x)都凸函数 min f(x) st.c(x)≤0,i=1,…,P Ax= b 设x*是问题的解,若x*处的有效约束的梯度向量线性无关,或所有约束函数 是线性函数则x*是问题的解的充要条件是 存在向量a*=(aa2…a)和/*使得 Vf(x*+2a "c(x)+A'B*=0 Vf(x)+vg(x)a*+AB*=0 c、(x*)≤0a1*≥0,a1*c(x+)=0i=1…,p(g(x*)≤0.*≥0,a*g(x*)=0 Ax*=b,β*∈R Ax*=b,B*∈R Karush- Kuhn-Tucker条件—KKT条件
18 定理：对一般可微规划问题( ( ), ( ) i f x c x 都凸函数) min ( ) . . ( ) 0, 1,..., i f x s t c x i p Ax b = = 设 x* 是问题的解，若 x* 处 的有效约束的梯度向量线性无关，或所有约束函数 是线性函数;则 x* 是问题的解的充要条件是 存在向量 ( ) * * * 1 2 * , , , = T p 和 * 使得 凸规划最优性充要条件 1 ( *) * ( *) * 0 ( *) 0, * 0, * ( *) 0, 1, , * , * = + + = = = = p T i i i i i i i q f x c x A c x c x i p Ax b R ( *) ( *) * * 0 ( *) 0, * 0, * ( *) 0 * , * + + = = = T q f x g x A g x g x Ax b R Karush-Kuhn-Tucker条件——KKT条件
其他最优性条件 定理( Fritz John条件) 设x∈Q,f(x)和g(x)(i∈I(x*)在点x处可微, g;(x)(igI(x)在点x*处连续。若x*是约束极值 问题①的局部极小点,则梳一组不全为零 的非负实数,使得 Vf(x)+∑Vg(x*)=0 i∈I(x*)
19 的非负实数 ，使得 问题（）的局部极小点，则存在一组不全为零 在 点 处连续。若 是约束极值 设 ， 和 在 点 处可微， i i i g x i I x x x x Q f x g x i I x x 1 ( )( ( *)) * * * ( ) ( )( ( *)) * ( *) ( *) 0 ( * ) 0 + = iI x f x i gi x 定理 (Fritz John条件): 其他最优性条件
fritz John条件与KKT条件的区别 fritz john条件可能出现w0=0的情形。这 时 fritz john条件中实际上不包含目标函数的 任何数据,只是把起作用约束的梯度组合成零 向量。这样的条件,对于问题的解的描述,没 有多大价值。我们感兴趣的是M0≠0的情形,所 以为了保证w≠0,还需要对约束施加某种限 制。这种限制条件通常称为约束规格。在上 个定理中,如果增加紧约束的梯度线性无关的 约束规格,则给出问题的KKT条件
20 Fritz John 条件与KKT条件的区别: Fritz John 条件可能出现w0=0的情形。这 时Fritz John 条件中实际上不包含目标函数的 任何数据，只是把起作用约束的梯度组合成零 向量。这样的条件，对于问题的解的描述，没 有多大价值。我们感兴趣的是w0≠0的情形，所 以为了保证 w0≠0 ，还需要对约束施加某种限 制。这种限制条件通常称为约束规格。在上一 个定理中，如果增加紧约束的梯度线性无关的 约束规格，则给出问题的KKT条件