约束规划最优性充分条件 定理：（约束问题解的鞍点充分条件）对一般约束规划问题 min f(x) s.t.gy≤0的L(x,a,B)=f(x)+ag(x)+Brh(x), (a≥0) h(x)=0 若对x∈R",存在a≥0、B∈R使得 L(c,a,B)≤L(c,a,B)≤L(x,a,B),x∈S,a∈Rf,B∈R9 则x∈R"是问题的整体最优解。 鞍点条件 证明：：L(x,a,B)≤L(c,a,B),Va∈Rf,B∈R9 ∴.(a-a)'g()+(B-B)rh()≥0，a∈R,B∈R9 由廿a≥0，P的任意性知：g()≤0，h()=0且a'g()=0或a8:()=0 进一步由不等式的后两部分知：f()≤f(x) 同时a,B是max{L(x,a,P),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) S.t.c,(x)≤0，i=1,,p Ax=b 设x*是问题的解，若x*处的有效约束的梯度向量线性无关，或所有约束函数 是线性函数；则x*是问题的解的充要条件是 存在向量a*=(a,,…,a)'和B*使得 f(x*)+2a,vc,(x*)+AB*=0 Vf(x*)+vg(x*)a*+AB*=0 c,(*)≤0，a*≥0，，*c,(x*)=0,i=1,…,p→g(x*)≤0，a*≥0，*Tg(x*)=0 Ax*=b,B*∈R9 A*=b,B*∈R9 Karush-Kuhn-Tucker条件一KKT条件 18
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*∈2，f(x)和g(x)(i∈(x*)在点x*处可微， gi(x)(i生I(x*)在点x*处连续。若x*是约束极值 问题①的局部极小点，侧在一组不全为零 的非负实数2，使得 2Vf(x*)+∑2，Vg,(x*)=0 i∈I(x*) 19
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条件可能出现w=O的情形。这 时Fritz John条件中实际上不包含目标函数的 任何数据，只是把起作用约束的梯度组合成零 向量。这样的条件，对于问题的解的描述，没 有多大价值。我们感兴趣的是w≠0的情形，所 以为了保证w+0，还需要对约束施加某种限 制。这种限制条件通常称为约束规格。在上一 个定理中，如果增加紧约束的梯度线性无关的 约束规格，则给出问题的KKT条件。 20
20 Fritz John 条件与KKT条件的区别: Fritz John 条件可能出现w0=0的情形。这 时Fritz John 条件中实际上不包含目标函数的 任何数据，只是把起作用约束的梯度组合成零 向量。这样的条件，对于问题的解的描述，没 有多大价值。我们感兴趣的是w0≠0的情形，所 以为了保证 w0≠0 ，还需要对约束施加某种限 制。这种限制条件通常称为约束规格。在上一 个定理中，如果增加紧约束的梯度线性无关的 约束规格，则给出问题的KKT条件
最优性条件总结 1) 所有规划解的最优性必要条件=KKT条件+约束规格 2) 凸规划解的最优性充分条件=KKT条件 最优性必要条件证明：需要用到凸集分离定理、择一性定理 (Farkas引理 凸规划最优性充分条件证明较简单，但对非凸规划结果没有实 际指导意义，蕴含着对偶原理一Langrange对偶 21
21 1) 所有规划解的最优性必要条件=KKT条件+约束规格 2) 凸规划解的最优性充分条件=KKT条件 最优性条件总结 最优性必要条件证明：需要用到凸集分离定理、择一性定理 (Farkas引理 凸规划最优性充分条件证明较简单，但对非凸规划结果没有实 际指导意义，蕴含着对偶原理——Langrange对偶