《最优化方法》课程教学资源（PPT课件）第七章 约束最优化方法（刘二永）

第七章 约束最优化方法

第七章 约束最优化方法

§7.2罚函数法

§ 7.2 罚函数法

基本思想 设法将约束问题求解转化为无约束问题求解 具体说根据约束的特点,构造某种惩罚函数, 然后把它加到目标函数中去,将约束问题的 求解化为一系列无约束问题的求解 惩罚策略企图违反约束的迭代点给予很大的 目标函数值迫使一系列无约束问题的极小点或 者无限地靠近可行域,或者一直保持在可行域 内移动,直到收敛到极小点

基本思想 设法将约束问题求解转化为无约束问题求解． 具体说：根据约束的特点，构造某种惩罚函数， 然后把它加到目标函数中去，将约束问题的 求解化为一系列无约束问题的求解． 惩罚策略：企图违反约束的迭代点给予很大的 目标函数值．迫使一系列无约束问题的极小点或 者无限地靠近可行域，或者一直保持在可行域 内移动，直到收敛到极小点．

外罚函数法 引例:求解等式约束问题: mIn f(x1,x)=x2+ s t +x,-2=0 解:图解法求出最优解x=(1y 构造 F(x,x2)= xi+x x1+x2=2 x+x2≠2 但是F(x1x2)性态极坏无法用有效的无约束 优化算法求解

外罚函数法 引例：求解等式约束问题: ( ) 2 2 2 1 2 1 min f x , x = x + x . 2 0 st x1 + x2 − = 解: 图解法求出最优解 (1,1) . * T x = 构造： ( )    +  +  + + = = 2 2 , 1 2 1 2 2 2 2 1 1 2 x x x x x x F x x 但是 ( ) 1 2 F x , x 性态极坏，无法用有效的无约束 优化算法求解．

设想构造:P(xA)=x2+x2+0(x+x2-2)2 其中σ是很大的正数 求解此无约束问题得:o)=xo) 20 20+1 当o→+时有 ,y)→;xy=

设想构造： ( ) ( ) 2 1 2 2 2 2 ; 2 1 P x  = x + x + x + x − 其中  是很大的正数． 求解此无约束问题得： ( ) ( ) 2 1 2 1 2 + = =     x x 当  → + 时，有： ( ) ( ) ( ) ( ) ( ) T T T x , x x , x 1,1 * 2 * 1 2 → 1 =  

等式约束问题 minf(x)x∈R() st x)=0i∈E 构 P(x, o)=f(x)+oP(x 其中σ>0为参数,称为罚因子 分析:P(x)=∑c:(x)B≥1 当x不是可行解时s1(x)≠0,P(x)>0,越大, 惩罚越重因此当。充分大时,P(x)应充分小 即P(x,a)的极小点应充分逼近可行域进而 逼近(1)的最优解

等式约束问题 min ( ) (1) n f x xR st. ci (x) = 0 iE = 1,2, l 构造： P(x ) f (x) P(x) ~ , = + 其中   0 为参数，称为罚因子． 分析： ( ) ( ) 1 ~ 1 =   =   l i i P x c x 当 x 不是可行解时， ( ) ( ) 0, ~ ci x  0,P x   越大， 惩罚越重．因此当  充分大时， P(x) ~ 应充分小． 即 P(x, ) 的极小点应充分逼近可行域，进而 逼近(1)的最优解．

不等式约束问题 mn f(x)x∈Rn(2) st (x)≥0i∈={1,2,…m} 构造:P(x,o)=f(x)+aP(x) 分析P(x)=∑mm(c(x)2a≥l 当x不是可行解时g(x)0,o越大, 惩罚越重因此当o充分大时P(x)应充分小 即P(x,a)的极小点应充分逼近可行域进而 逼近(2)的最优解

不等式约束问题 min ( ) (2) n f x xR st. ci (x) 0 iI = 1,2, m 构造： P(x ) f (x) P(x) ~ , = + 分析： ( ) min (0, ( )) 1 ~ 1 =   =   m i i P x c x 当 x 不是可行解时， ( ) ( ) 0, ~ ci x  0,P x   越大， 惩罚越重．因此当  充分大时， P(x) ~ 应充分小． 即 P(x, ) 的极小点应充分逼近可行域，进而 逼近(2)的最优解．

般约束问题 minf(x)x∈R(3) st x)=0i∈E c;(x)≥0i∈I={+1, 构造:P(x,o)=f(x)+o(x)(4)其中 P(x)=∑c(x)2+mim(0,c/(x)a≥1,B≥1 j=l+1 注:-般取a=B=2

一般约束问题 min ( ) (3) n f x xR st. ci (x) = 0 iE = 1,2, l ci (x) 0 iI = l +1,  ,m 构造： ( ) ( ) ( ) (4) ~ P x, = f x +P x ( ) ( ) min (0, ( )) 1, 1 ~ 1 1 = +    = = +     m j l j l i i P x c x c x 其中： 注：一般取  =  = 2

例1:用外罚函数法求解 min f(x)=x2+x2 st +1≤0 #4: P(,c)=x2+x2+omin(, -x-1)] 即(xa)-+ x1+1≤0 2+x2+a(x1+1)2x1+1>0 因此:aP「2x1 12x+2(x1+1) aP Ox

例1：用外罚函数法求解： ( ) . 1 0 min 1 2 2 2 1 +  = + st x f x x x 解： ( )  ( ) 2 1 2 2 2 P x, = x1 + x + min 0,−x −1 即： ( )  ( )   + + + +  + +  = 1 1 0 1 0 , 1 2 1 2 2 2 1 1 2 2 2 1 x x x x x x x P x   因此：  ( )   + +  −  − =   2 2 1 1 2 1 1 1 1 1 1 1 x x x x x x P  2 2 2x x P =  

OPOP 0 Or ax 得:x1(o)= x(G)=0 o+1 最优值P(x,a)= o+1 +1 当σ→+∞时 x1()→>-1,x2(o)->0 x(a)→>x,P(x,o)→f(x)=1

令： 0 1 2 =   =   x P x P 得： ( ) ( ) 0 1 1 2 = + = −    x  x 最优值： ( ) 1 1 1 1 , 2 2 +  =      +  +      + = −       P x  当  → + 时： x1 ( )→−1, x2 ( )→0 ( ) , ( , ) ( ) 1 * * x  → x P x  → f x =