约束规划最优性条件的几何表述 min f(r) c(x)=0 St.c1(x)=0,讠=1, vf(x) 梯度共线 f(x)=4 Vf(x)=aVc(x) 11
11 约束规划最优性条件的几何表述 min ( ) . . ( ) 0, 1,..., i f x s t c x i q = = 梯度共线 = f x c x ( *) ( *)
约束规划最优性条件的几何表述 Vf(x”) min f(r) sc()=0,i=1,,qa(xy0 c2(x)=0 D f(x)=f(x V(x)=avc(x)+avc2(x)共面<→梯度被线性标示 12
12 共面→梯度被线性标示 约束规划最优性条件的几何表述 1 1 2 2 = + f x c x c x ( *) ( *) ( *) min ( ) . . ( ) 0, 1,..., i f x s t c x i q = =
约束规划最优性条件的几何表述 min f(x) St.c;(x)≤0,i=1,,p x)=4 c(x)=0 Vc(x") x vf(r) 结论:在解处仅等式(紧)约束有效!Vf(x*)+aVc(x*)=0.,a≥013
13 min ( ) . . ( ) 0, 1,..., i f x s t c x i p = 结论：在解处仅等式(紧)约束有效！ 约束规划最优性条件的几何表述 + = f x c x ( *) ( *) 0, 0 S
f(x)=4 c(x)0 vc( S Vx梯度的负线性表示! vf(x*)+aVc1(x)+a2Vc2(x*)=0,1≥0,a2≥0 定义7有效约束(紧约束、积极约束)— active constraint 对约束cx)≤0,在x*处有(x)=0,则称在x处c(x)是紧约束。 处有效约束指标集A(x+)=(1c(x*)=0} 14
14 对约束 定义7. 有效约束(紧约束、积极约束)——active constraint c x i ( ) 0, 在x*处有 c x i ( *) 0, = 则称在x*处ci (x)是紧约束。 x*处有效约束指标集 A x i c x ( *) ( *) 0 = = i 梯度的负线性表示! 1 1 2 2 1 2 + + = f x c x c x ( *) ( *) ( *) 0, 0, 0 S
约束规划最优性必要条件 定理:(约束问题解的必要条件对一般可微规划问题 nn f(r) St.c1(x)≤0,i=1,…,pP c;(x)=0,=P+1,…,P+q 设x*是问题的局部解,若x*处的有效约束的梯度向量vc(xi∈A(x+) 线性无关,或者所有约束函数是线性函数,则存在p+g维向量 xi)使得yf(x+)+∑a1c(x+)=0 Karush-Kuhn-Tucker 条件—KKT条件(x*)≤0,.1*20.1*c(x*)=0,i=1,2,…,P c(x*)=0i=P+12…P+q 互补 令g(x)=()x)y,M)=(1(x-m,(xy向量化表示松弛 条件 min f(r) Vf(x)+vg(x)u*+Vh(x)v* st.g(x)≤0 g(x2)≤0.n*20.m*g(x+)=0 h(x)=0 h(x*)=0,v∈R 15
15 定理：(约束问题解的必要条件)对一般可微规划问题 min ( ) . . ( ) 0, 1,..., ( ) 0, 1,..., i i f x s t c x i p c x i p p q = = = + + 设 x* 是问题的局部解，若 x* 处的有效约束的梯度向量 ( *)( ( *)) i c x i A x 线性无关，或者所有约束函数是线性函数，则存在 p+q 维向量 ( ) * * * 1 2 * , , , = + T p q 使得 1 1 ( ) ( ( ),..., ( )) , ( ) ( ( ),..., ( )) T T p p p p g x c x c x h x c x c x 令 = = + + min ( ) . . 0 ( ) 0 f x s t g(x) h x = 向量化表示 约束规划最优性必要条件 1 ( *) * ( *) 0 ( *) 0, * 0, * ( *) 0, 1,2, , ( *) 0, 1,2, , p q i i i i i i i i f x c x c x c x i p c x i p p q + = + = = = = = + + ( *) ( *) * ( *) * 0 ( *) 0, * 0, * ( *) 0 ( *) 0, + + = = = T q f x g x u h x v g x u u g x h x v R Karush-Kuhn-Tucker 条件——KKT条件 互补 松弛 条件