非线性规划理论与算法 ●非线性规划及其最优性条件 对偶理论 外点罚函数法 内点罚函数法
1 非线性规划理论与算法 • 非线性规划及其最优性条件 • 对偶理论 • 外点罚函数法 • 内点罚函数法
非线性规划 设x=(x1…,xn)∈R",∫(x),c;(x):R"H>R,i=1,2,…,P+q,如下约束问 题称为非线性规划( Nonlinear programming,NP): mn f(r) st.c1(x)s0,i=1,…,p minf(x) p=q=0即无约束规划 y∈ S (x)=0,i=P+1,…,p 约束集或可行域:S={xeR"(x)s01=1,-,()=0.j=p+1“p+q x是整体(全局极小点兮Vx∈S,∫(x)≥∫(x) x是严格整体(全局极小点冷x∈S\{x},∫(x)>f(x*) x*是局部极小点台eSn{x∈F"|x-x+-<,/()2(x) x“是严格局部极小点Wx∈n{x∈Rx-x+e,(x)>/x) 非线性规划向量化表示 令g(x)=(c(x),…,Cn(x) min f(r) st.g(x)≤0 h(x)=(cn+(x),c,+(x)) h(x)=0
3 设 T n x = (x1 ,..., xn ) R ， ( ), ( ) : n i f x c x R R , i p q = + 1,2, , ，如下约束问 题称为非线性规划(Nonlinear Programming, NP)： min ( ) . . ( ) 0, 1,..., ( ) 0, 1,..., i i f x s t c x i p c x i p p q = = = + + ( ) 0, 1,..., , ( ) 0, 1,..., n 约束集或可行域: S x R c x i p c x j p p q = = = = + + i i 非线性规划 x*是整体(全局)极小点 x S f x f x , ( ) ( *) x*是严格整体(全局)极小点 x S x f x f x \ { }, ( ) ( *) x*是局部极小点 * , ( ) ( *) n − x S x R x x f x f x x*是严格局部极小点 * , ( ) ( *) n − x S x R x x f x f x min ( ) x S f x 1 1 ( ) ( ( ),..., ( )) , ( ) ( ( ),..., ( )) T p T 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 = 非线性规划向量化表示 p=q=0即无约束规划
非线性规划的几个概念 min f(r) 定义1.设∫:R"HR,∈R",d∈R",d≠0,若存在δ>0,使 St.g(x)≤0 f(x+td <f(x, tE(0, 8) h(x)=0 则称向量d是函数八x)在点x处的下降方向。 dVf(x)<0 定义2.设ScR,x∈S,d∈R",d≠0,若存在t>0,使x+l∈S,则 称向量d是函数八(x)在点处关于S的可行方向。 线性化可行方向: g(x)=0 dVg(x)≥0;dVh2(x)=0 可行方向锥 g2(x)=0
4 非线性规划的几个概念 定义 1. 设 : , , , 0 n n n f R R x R d R d ，若存在 0，使 f x td f x t ( ) ( ), (0, ) + 则称向量 d 是函数 f(x)在点 x 处的下降方向。 定义 2. 设 , , , 0 n n S R x S d R d ，若存在t 0，使 x td S + ，则 称向量 d 是函数 f(x)在点x处关于 S 的可行方向。 线性化可行方向: ( ) 0 T d f x ( ) ; ( ) 0 0 T T i i d g x d h x = min ( ) . . 0 ( ) 0 f x s t g(x) h x = g1 (x) = 0 g2 (x) = 0 0 x 1 x 1 d 1 d 2 d 2 d 1 2 3 3 d 可行方向锥
mIn St.g(x)≤0 定义3:积极约束: h(x)=0 设点x∈Q,对于不等式约束g(x)≤0,如果g,(x)=0, 则称g(x)≤0是点x处的积极约束。 或起作用约束(紧约束\积极约束\有效约束) 记I(x)={l!g(x)=0,1≤i≤l},称(x)为点x处的积极约束指标集。 例:设g1(x)=√2x2-x2≤0,81(x)=x2+x2-1≤0,g1(x)=-x1≤0 令x=( √√2 ),则I(x)={1,2} 81(x)=0/g(x)2=0 g3(x)=0
5 定义3: 积极约束: , ( ) 0 ( ) 0, ( ) 0 i i i x Q g x g x g x x = 设点 对于不等式约束 ，如果 则称 是点 处的积极约束。 或起作用约束（紧约束\积极约束\有效约束）。 ( ) { | ( ) 0,1 }, ( ) i 记I x i g x i l I x x = = 称 为点 处的积极约束指标集。 2 2 2 1 1 2 2 1 2 3 1 ( ) 2 0, ( ) 1 0, ( ) 0 2 2 ( , ) ( ) 2 2 T g x x x g x x x g x x x I x = − = + − = − = = 例：设 . 令 ，则 {1,2}. 1 x 2 x O g2 (x) = 0 g1 (x) = 0 g3 (x) = 0 x min ( ) . . 0 ( ) 0 f x s t g(x) h x =