《非线性规划理论与算法》课程教学资源（PPT课件讲稿）

非线性规划理论与算法 ●非线性规划及其最优性条件 对偶理论 外点罚函数法 内点罚函数法

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+-/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 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       =

min f(r) 定理1: St.g(x)≤0 给定点x∈Q,记点x的积极约束指标集为I(x)。给定向量d, 如果对任意的∈I(x)有vg(x)d0。则对任意的i∈I(x),有 8, (x)=g, (x)+tvg (x)d+o( td) =tvg(x)d+o( 5<o x∈Q,即d为可行方向。 定义4可行下降方向 设点x∈旦给定向量d,如果d既是点x处的可行方向, 又是该点的下降方向,则称d为点x处的可行下降方向

6 令 x'= x + t d ,t  0。则对任意的i  I(x),有 ( ') ( ) ( ) (|| || ) 2 g x g x t g x d o td T i = i +  i + ( ) (|| || ) 2 t g x d o td T =  i +  0  x'Q,即d为可行方向。 又是该点的下降方向，则称 为点 处的可行下降方向。 设点 ，给定向量 ，如果 既是点 处的可行方向， d x x Q d d x 证明: 定理1: 定义4: 可行下降方向 如果对任意的 有 则 是 点 的可行方向。 给定点 记 点 的积极约束指标集为 。给定向量 ， i I x g x d d x x Q x I x d T i ( ) ( ) 0, , ( )     min ( ) . . 0 f x s t g(x)    

定理2: min f(r) 给定点xeQ,记点x的积极约束指标集为(x)。给定(s.g(x)≤0 向量d,如果d满足 g(x)d<0i∈I(x) vf(x)d<0 则向量d是点x处的可行下降方向。 证略 ③极值点的必要条件: 定理3:设x*∈Q,I(x)是其积极约束指标集。 f(x)和g;(x)(i∈I(x)在点x*处可微, g;(x)(igⅣ(x)在点x处连续。 如果x*是约束极值问题1)的局部极小点,则在 点x处没有可行下降方向

7 则向量 是 点 处的可行下降方向。 向 量 ，如果 满 足 给定点 记 点 的积极约束指标集为 。给定 d x f x d g x d i I x d d x Q x I x T T i          ( ) 0 ( ) 0 ( ) , ( ) 设 x*Q，I(x*)是其积极约束指标集。 定理2: 定理3: 证略 ③极值点的必要条件: f (x)和gi (x)(i  I(x*))在点x*处可微， gi (x)(i  I(x*))在点x*处连续。 点 处没有可行下降方向。 如 果 是约束极值问题 的局部极小点，则在 * * (1) x x min ( ) . . 0 f x s t g(x)    

定义5.设ScR",称S为凸集当且仅当Vx1,x2ES及∈0,1都有 x1+(1-1)x2∈S 定义6.设x,x,…,x,∈R",称x是x,x,…x的一个凸组合当且仅当存在 ∑1=1,20使x=∑1x。 定义7.设S∈R",称∫是S上的凸函数当且仅当对x,x2∈S及 ∈|0,都有 ∫(x1+(1-1)x2)≤f(x1)+(1-A)f(x2) 严格凸组合严格凸 线性组合 定理若八以)是S上的凸函数,则ce∈R,水平集X=(sS∫(xsc是凸集 若八∞)是凸函数,S是凸集,min∫(x)为凸规划。凸规划的局部解是整体解! xES S={xe1:(x)s0;=1…,c(x)=00=p+,…+q 般要求c1(x)当=1,2…p时为凸函数,当p+1,+时为线性函数。 8

8 定义 5. 设 n S R  ，称 S 为凸集当且仅当 1 2   x x S , 及  [0,1]都有 1 2   x x S + −  (1 ) 定义 6. 设 1 2 , , , n p x x x R  ，称 x是 1 2 , , , p x x x 的一个凸组合当且仅当存在 1 1, 0 l i i i   =  =  使 1 l i i i x x  = =  。 定义 7. 设 n S R  ，称 f 是 S 上的凸函数当且仅当对 1 2   x x S , 及   [0,1]都有 1 2 1 2 f x x f x f x ( (1 ) ) ( ) (1 ) ( )     + −  + − 严格凸组合 严格凸 线性组合 定理 若 f(x)是 S 上的凸函数，则 c R，水平集 X x S f x c =    ( ) 是凸集. min ( ) x S f x  若f(x)是凸函数，S是凸集， 为凸规划。  ( ) 0, 1,..., , ( ) 0, 1,...,  n S x R c x i p c x j p p q =   = = = + + i i 一般要求 ( ) i c x 当i=1,2,…,p时为凸函数，当i=p+1,…,p+q时为线性函数。 凸规划的局部解是整体解！

82∫(x)a2f(x) 2f(x) C, o df(x) a-f(r)af( 82∫(x) axax. a ax. a Vf(x)= ax2 vf(r) df(x) a-f(r)af(x a-f(r) axax 定理(凸函数的一阶充要条件)若fx)在S上可微,则f(x)是凸函 数当且仅当 ∫(x)≥∫(x)+Vf(x)(x-x),Vx∈S 定理(凸函数的二阶充要条件)设∫:S→R二阶连续可导,则 I)厂是S上的凸函数的充要条件是∫的Hese矩阵vf(x)在S上是半正定的。 2)当vf(x在S上是正定矩阵时,∫是S上的严格凸函数。(注:逆命题不成立)9

9 2 2 2 2 1 1 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 ( ) ( ) ( ) .... ( ) ( ) ( ) ... ( ) ( ) ( ) ( ) n n n n n f x f x f x x x x x x f x f x f x x x x x x f x f x f x f x x x x x x                      =           1 2 ( ) ( ) ( ) ( ) n f x x f x f x x f x x               =               定理(凸函数的一阶充要条件) 若 f(x)在 S 上可微，则 f(x)是凸函 数当且仅当 ( ) ( ) ( ) ( ) T f x f x f x x x  +  − ，  x S 定理(凸函数的二阶充要条件) 设 f : S  R 二阶连续可导，则 1)f 是 S 上的凸函数的充要条件是 f 的 Hesse 矩阵 ( ) 2  f x 在 S 上是半正定的。 2)当 ( ) 2  f x 在 S 上是正定矩阵时，f 是 S 上的严格凸函数。(注:逆命题不成立)

最优性条件 无约束规划minf(x) x∈R 定理:可微函数解的必要条件:x*是局部解则:V(x)=0.x是驻点(稳定点) 可微凸函数解的充要条件:x是整体极小解当且仅当Vf(x)=0 y=f(r) qp(t)=∫(x*+tdO 10

10 定理：可微函数解的必要条件：x*是局部解,则：  = f x( *) 0. 最优性条件 min ( ) n x R f x  无约束规划 x*是驻点(稳定点) 可微凸函数解的充要条件：x*是整体极小解当且仅当  = f x( *) 0. ( ) ( * ) t f x td = +