《最优化方法》课程教学资源（题解）第六次 单纯形替换法

单纯形替换法 1.单纯形替换法: Spendley、Hext和 hImsworth 于1962年提出; Ne|der和Mead1965年改进 2.问题: min f(x) x∈RM f(x是R"上连续函数 即f(x)∈CR

单纯形替换法 1.单纯形替换法: Spendley、Hext 和Himsworth 于1962年提出; Nelder 和Mead 1965年改进 2. 问 题: min f ( x ) n xR f ( x )是R n 上连续函数 f ( x ) C( R ) n 即 

3.算法思想 (1)集合迭代的思想 S0→>S1→>…→>Sk→Sk+1→ 这里S1(i=1,2,…)为单纯形 (2)下降迭代的思想 使S,中顶点的目标函数值降

(1) 集合迭代的思想。 这 里 S (i , , )为单纯形 S S S S i k k    1 2 0 1 1 = → → → → + → 3.算法思想 (2) 下降迭代的思想。 使Si 中顶点的目标函数值下降

4.单纯形概念 1)例: R:线段 R2:三角形 R3:四面体

4. 单纯形概念 例：R 2 : 三角形 (1) R 3 : 四面体 R 1 : 线段 0 V 1 V 0 V 0 V 1 V 1 V 2 V 2 V 3 V

(2)单纯形的定义 设V°,V,…,V"∈R",如果V-V°(j=1,2,…,n)线性无关, 则°,V,…,V的凸组合称为由,V,,"构成的 单纯形,记为S=[v0,,…,V"],即 {x1∑aV,其中∑a1=1,a1>0} 称V°,V,…,V"为该单纯形的顶点

V , V , , V R , n n   设 0 1 ( 1,2, , ) , 如果 V j −V 0 j =  n 线性无关 单纯形 记 为 即 则 的凸组合称为由 构成的 , [ , , , ] , , , , , , , 0 1 0 1 0 1 n n n S V V V V V V V V V    = [ , , , ] 0 1 n S = V V  V 称V 0 , V 1 ,  , V n为该单纯形的顶点。 （2）单纯形的定义 { | , 1 , 0} 0 0 =   =  = = j n j j n j j x  j V 其中  

5如何构造单纯形? 对于给定的点x和正数δ,有两种方式构造单绝形: (1)=x V=yo+se =+8e V2-"=8e1+e2) Vn=vn-+se V"-V=8(e1+e2 则S=°,V1,…,"]成一个单纯形

对于给定的点x 0和正数，有两种方式构造单纯形 ： V V e V V ( e e e ) V V e V V ( e e ) V V e V V e V x n n n n n    = +  − =  + + = +  − =  + = +  − =  = − 1 2 1 0 1 2 2 0 2 2 1 1 1 0 1 1 0 0 0 (1) 5.如何构造单纯形? 则 S = [V 0 , V 1 ,  , V n ]构成一个单纯形

例设=(1,0,)y,6=1 2 则v=V"+6;=(,1)+1(1,.0)y÷=(3,0,1y, 2 2 31 22 313 V3=V2+6e3=(,,1)+(0,0,1)=( 22 2 222 则S=[°,V,V,构成一个单纯形

例 设 （ 。 2 1 1,0,1) , 0 =  = T V 则 ,0,1) , 2 3 (1,0,0) ( 2 1 (1,0,1) 1 1 0 T T T V =V +  e = + = ,1) , 2 1 , 2 3 (0,1,0) ( 2 1 ,0,1) 2 3 ( 2 2 1 T T T V =V +  e = + = V V e T T ) T 。 2 3 , 2 1 , 2 3 (0,0,1) ( 2 1 ,1) 2 1 , 2 3 ( 3 3 2 = +  = + = 则 S = [V 0 , V 1 , V 2 , V 3 ]构成一个单纯形

6.单纯形替换法的几何解释 给定单纯形S=Ⅳ,V1,…,V" 设∫(W)=max{f(W),f(V),…,∫(V")}, ∫(Ⅳ)=min{∫(),f(W),…,f(")}

6.单纯形替换法的几何解释 * x 0 V 2 V 1 V V r V e V 给定单纯形S = [V 0 , V 1 ,  ,V n ]。 ( ) max{ ( ), ( ), , ( )}, h 0 1 n 设 f V = f V f V  f V f (V l ) = min{ f (V 0 ), f (V 1 ),  , f (V n )}

令V=∑V ni≠h 反射步:V′=V+a(-Vb) ′:反射点,a:反射系数,一般取a=1。 如果∫(W)<∫(V): 延伸步:则令Ⅳ=+B(V-卩), Ie:延伸点,阝:延伸系数,一般取尸=2 若∫()<∫(),则用v代替V,构成新的单纯形 否则用V代替,构成新的单纯形

延伸步：( ) ( ): r l 如果 f V  f V V e :延伸点，β :延伸系数，一般取 β = 2。 则令V e =V +  (V r −V ) ， : ( ) r h 反射步 V =V +  V −V V r :反射点， :反射系数，一般取 = 1。 令  。  = i h i V n V 1 若 ( ) ( ),则 用 代 替 ,构成新的单纯形, e l e h f V  f V V V 否则用V r 代替V h ,构成新的单纯形

收缩步(情形一) Vi≠h有∫(V)≤f()≤f(b) 则令=+y(V-T) c:收缩点,y收缩系数,一般取y 2 若∫()<∫(),则用v代替V,构成新的单纯形

0 V 2 V 1 V V r V c V 收缩点， ：收缩系数，一般取 。 则 令 ， 有 2 1 : ( ) ( ) ( ) ( ) = = + −        c c r i r h V V V V V i h f V f V f V 收缩步（情形一）: 若 f (V c )  f (V h ),则 用V c 代 替V h ,构成新的单纯形

收缩步(情形二 若∫(V)>∫(W"),则令V=+y(Vh-) c:收缩点,y收缩系数,一般取y 2 若∫()<∫(),则用V代替,构成新的单纯形

0 V 2 V 1 V V r V c V 收缩步（情形二）: 收缩点， ：收缩系数，一般取 。 若 ， 则 令 ， 2 1 : ( ) ( ) ( ) =  = + −    c r h c h V f V f V V V V V 若 f (V c )  f (V h ),则 用V c 代 替V h ,构成新的单纯形