第7章 最优化方法 §1 引言 §2 一维搜索 §3 非线性最小二乘法 §4 最速下降法 §5 共轭斜量法 §6 变尺度方法

Presentation on theme: "第7章 最优化方法 §1 引言 §2 一维搜索 §3 非线性最小二乘法 §4 最速下降法 §5 共轭斜量法 §6 变尺度方法"— Presentation transcript:

1 第7章 最优化方法 §1 引言 §2 一维搜索 §3 非线性最小二乘法 §4 最速下降法 §5 共轭斜量法 §6 变尺度方法
第7章 最优化方法 §1 引言 §2 一维搜索 §3 非线性最小二乘法 §4 最速下降法 §5 共轭斜量法 §6 变尺度方法 §7 单纯形方法

2 §1 引言 1.1一元函数的极值 1.定义 设函数f(x)在点x0的某个邻域内有定义,在该邻域内,若满足f(x)＞f(x0)(x≠x0),则称f(x)在点x0达到极小值, x0为f(x)的极小点;若满足f(x)＜f(x0)(x≠x0),则称f(x)在点x0达到极大值,x0为f(x)的极大点。

3 如图7.1,f(x)在点x1达到极大值,在点x2达到极小值,x1、x2分别为f(x)的极大点和极小点。极大值和极小值统称为极值。
图 7.1

4 2. 极值的必要条件 设函数f(x)在点x0可微,且在x0达到极值,则   f′(x0)=0  如图7.1,曲线f(x)在A点、B点的切线都平行于x轴,也即f′(x1)=0,f′(x2)=0。这里的x0称为函数f(x)的驻点。驻点不一定是极值点,例f(x)=x3,有f′(0)=0,但x=0不是f(x)=x3的极值点。

5 3.极值的充分条件 第一种充分条件设函数f(x)在点x0的某个邻域内具有导数且f′(x0)=0, (1)若当x＜x0时,f′(x)＞0,当x＞x0时,f′(x)＜0,则函数f(x)在点x0处达到极大值; (2)若当x＜x0时,f′(x)＜0,当x＞x0时,f′(x)＞0,则函数f(x)在点x0处达到极小值; (3)当x取x0的左、右边附近的值时,f′(x)恒为正(或恒为负) ,则函数f(x)在点x0处无极值。

6 第二种充分条件设函数f(x)在点x0处具有二阶导数且f′（x0)=0,f″(x0)≠0,则
(1)当f″(x0)＜0时,函数f(x)在点x0处达到极大值; (2)当f″(x0)＞0时,函数f(x)在点x0处达到极小值。

7 1.2 二元函数的极值 多元函数的极值不能完全从一元函数的情形反映出来,但能从二元函数中得到较好的反映。为此,我们给出二元函数的极值。读者可推广到一般的多元函数上去。 1.定义 设二元函数z=f(x,y)在点p0(x0,y0)的某个邻域内有定义,在该邻域内若满足f(x,y)＞f(x0,y0) (p(x,y)≠p0(x0,y0)),则称函数f(x,y)在点p0达到极小值,p0为f(x,y)的极小点;若满足f(x,y)＜f(x0,y0)

8 (p(x,y)≠p0(x0,y0)),则称函数f(x,y)在点p0达到极大值,p0为f(x,y)的极大点。如图7
(p(x,y)≠p0(x0,y0)),则称函数f(x,y)在点p0达到极大值,p0为f(x,y)的极大点。如图7.2,f(x,y)在p1(x1,y1)达到极大值,在p2(x2,y2)点达到极小值,p1、p2分别为f(x,y)的极大点和极小点。

9 图 7.2

10 设二元函数f(x,y)在p0(x0,y0)点的一阶偏导数存在,且在该点达到极值,则有
2. 极值的必要条件 设二元函数f(x,y)在p0(x0,y0)点的一阶偏导数存在,且在该点达到极值,则有 f′x(x0,y0)=0 f′y(x0,y0)=0 满足(7―1) 式的点p0(x0,y0)称为函数f(x,y)的驻点。 为了求函数的极值点,应该先求函数的驻点,但驻点不一定是极值点。例如,z=xy的驻点为p(0,0),但它不是极值点。 (7―1)

11 设函数f(x,y)在点p0(x0,y0)的某个邻域内有连续的直到二阶偏导数,且
3. 极值的充分条件 设函数f(x,y)在点p0(x0,y0)的某个邻域内有连续的直到二阶偏导数,且 f′x(x0,y0)=0 f′y(x0,y0)=0 (7―2)

12 则函数f(x,y)在点p0(x0,y0)达到极值。若f″xx(x0,y0)＞0,那么f(x,y)在点p0达到极小值,若f″xx(x,y)＜0,则函数f(x,y)在点p0达到极大值。

13 1.3目标函数的最速上升方向和最速下降方向 以二元函数为例,讨论f(x)的最速上升方向和最速下降方向。 设f(x)为定义在二维空间R2上的函数

14 将f(x)在x(0)点附近展成泰勒级数,取到二次项为

15 这里   Δx1=x1-x(0)1 Δx2=x2-x(0)2 若用向量和矩阵记号,上式可以简写为 (7―3)

16 其中

17 g0为目标函数f(x)在点x(0)处的斜量(或称为梯度) ,常记为
 g0=f(x(0))(或gradf(x(0))) A为对称矩阵。 我们知道,过点x(0)引向量p0,f(x)沿这个方向的变化 率就是f(x)在该点沿此方向的方向导数,其值为

18 见图7.3。 因为 所以,h为单位向量。若用θ表示gT0和h正向之间的夹角,则 gT0h=‖g0‖‖h‖cosθ =‖g0‖cosθ 可知,当θ=0时, gT0h=‖g0‖为最大值,h的方向与g0一致;当θ=π时, gT0h=-‖g0‖为最小值,h的方向与g0相反。

19 图 7.3

20 1.4 求目标函数极值的迭代法 数值解法中最为常见的是迭代法。它的基本思想为:首先给出目标函数f(x)极小点的初始点x(0),然后按一定的规则构造一系列点列x(k)(k=0,1,2,…),希望点列｛x(k)｝的极限x就是f(x)的一个极小点。下面讨论点列｛x(k)｝的产生。 设｛x(k)｝为已知,要求x(k+1)。因为 x(k+1)与x(k)之差是一个从x(k)出发指向x(k+1)的向量,而向量总是由方向和长度所确定,即总可以写成

21 x(k+1)-x(k)=λkpk (7―4a) 或 x(k+1)=x(k)+λkpk (7―4b) 选取pk与λk的方法有多种多样,但选择的原则应该满足我们的需要。第一,点列｛x(k)｝的每一项x(k)所对应的函数值f(x(k))必须逐次减小,即 f(x(0))≥f(x(1))≥…≥f(x(k))≥…

22 综合前面的讨论,最优化算法中的迭代法大致可分成下列步骤进行:
(1)选择初始点x(0); (2)按某种规则产生方向pk,使得目标函数f(x)从x(k)出发,沿pk方向按下降算法找到 x(k+1)(x(k+1)=x(k)+λkpk); (3)确定λ=λk,使得f(x(k)+λkpk)＜f(x(k)),也即沿射线x(k)+λpk求   g(λ)=f(x(k)+λpk) (7―5)  的极小值,也称为一维搜索

23 (4) 检验x(k+1)是否满足所给精度的最优解(例,
f(x(k+1))-f(x(k)) ＜ε,ε为预给的精度) ,若已达到,则迭代过程终止,   x≈x(k+1) f(x)≈f(x(k+1))   否则再进行下一步迭代。

24 §2 一维搜索 上面已经提到,在无约束极值的算法中,为了求点列｛x(k)｝,只要沿逐次确定的一系列射线x(k)+λpk求极小点。当方向pk确定以后,x(k)为已知,则f(x(k)+λpk)为以λ为单个自变量的函数,即 g(λ)=f(x(k)+λpk)

25 这样,求f(x(k)+λpk)的极小值实际上就是求一元函数g(λ)的极小值。为了方便,我们仍然讨论一元函数f(x)的极小值问题,并假设f(x)在局部范围内的极小值存在且唯一。
由一元函数极值存在的必要条件,我们需要求   f′(x)=0  的解,也就是求解该方程。

26 2.1 牛顿法 第二章第四节中介绍,求解非线性方程 φ(x)=0 的牛顿迭代公式为 为求解方程f′(x)=0,则迭代公式应改为
(7―6) 是求一维无约束极值的牛顿迭代公式。

27 2.2 二分法 设函数f(x)在某区间上连续可导,若x为f(x)的极小点,则f′(x)=0,且当x＜x时,f′(x)＜0,即函数单调减小;而当x＞x时,f′(x)＞0,即函数单调增加。如果能找到一个区间［a,b］,且有f′(a)＜0,f′(b)＞0,则在a,b之间必有f(x)的极小点x。下面介绍二分法。

28 区间［a,b］为已知的二分法的计算步骤如下:
②(a+b)/2x。 ③若f′(x)=0,则停止计算,x=x。 ④若f′(x)＞0,则xb,转向⑤;否则xa,转向⑤。 ⑤若b-a＜ε,则x=x,结束;否则转向②。 其计算框图如图7.5。

29 图 7.4

30 图 7.5

31 2.3 黄金分割法(0.618法) 牛顿法和二分法都要计算函数的导数。这往往会给计算带来麻烦。黄金分割法就克服了这种计算中的不足,仅用函数值本身的方法解决。此方法曾作为优选法用于生产和科学实验,收到了良好的效果。

32 由于不须求导数,函数在尖点上达到极值也可以,见图7
由于不须求导数,函数在尖点上达到极值也可以,见图7.6。设x(x)的极小点,则在极小点x的左边f(x)单调减小,也即若x1＜x2≤x,则f(x1)＞f(x2);在极小点x的右边f(x)单调增加,也即若x≤x1＜x2,则f(x1)＜f(x2)。为了求出函数f(x)的极小点x,就要在［a,b］内选取一些点的函数值进行比较。当然,总想寻找最少点的函数值进行比较,尽快地接近x。

33 图 7.6 图 7.7

34 如图7.7,在［a,b］内取两个对称的点x1和x′1,若
  f(x1)＜f(x′1)则极小点在［a,x′1］内,否则在 ［x1,b］内,记新的极小点存在的区间为［a1,b1］,如图7.8,这样原极小点存在的区间被缩短了一次;在区间［ a1,b1 ］内再取得两个对称点x2和x′2,如图7.9,通过比较f(x2)和f(x′2)的值,又可确定极小点存在的新区间［a2,b2］;如上不断缩短区间,最终总可求出满足精度要求的近似极小点。

35 图 7.8

36 图 7.9 图 7.10

37 我们的问题是如何选取xi和x′i(i=1,2,…) ,使每次区间的长度按一定比例缩短。
现令区间［a,b］的长度为1,设区间［a,x′1］的长度为α,如图7.10,要使每次区间长度均按一定比例缩短,则应有 (7―7) 解得 (7―8)

38 由上述讨论,黄金分割法用k个试点可以把原来的 区间［a,b］连续缩短k-1次,而每次的缩短率为 α(α=0.618),最后区间长度就缩短为
取正值 一般取  α= (7―9) 由上述讨论,黄金分割法用k个试点可以把原来的 区间［a,b］连续缩短k-1次,而每次的缩短率为 α(α=0.618),最后区间长度就缩短为 (7―10)

39 ① 在［a,b］内取两个试点a1和b1,如图7.11所示。
若预先给定精度ε,则可取满足不等式   αn-1＜ε (7―11)   的最小n作为所需要试点的个数。 具体计算步骤为: 在n确定以后,可分下列五步进行。 ① 在［a,b］内取两个试点a1和b1,如图7.11所示。 图 7.11

40 2）计算函数值(a1)和f(b1),并令 ③ 比较f1和f2,若 则令

41 否则令 ④上述计算重复次数为从n-1开始,以-1为步长,直到1为止(也可从1开始,以1为步长,直到n-1为止) ⑤ 最后比较f1和f2,如果   f1＜f2

42 则a1为极小点,f1为极小值;否则b1为极小点,f2为极小值。其计算框图见图7.12。
应用黄金分割法时也可不必预先确定n,而在计算过程中逐次判断是否有   αk＜ε (7―12)   若成立,k+1即是所需试点的个数,从而比较函数值的大小,输出结果。也可由   ｜f2-f1｜≤ε｜f1｜ (7―13) 及   ｜b1-a1｜≤ε｜a1｜ (7―14)

43 图 7.12

44 图 7.13

45 例1 用黄金分割法求函数 f(x)=x2-x+2   在区间［0,1］内的极小点和相应的极小值(取ε=0.1)。 解 利用黄金分割法,这里不预先确定试点个数n,而在计算过程中逐次判断是否有 ｜(b1-a1)/a1｜≤ε   若a1=0,则用   ｜(b1-a1)/b1｜≤ε

46 表 7―1

47 由表中可见,满 足精度要求的极小点为  x≈0.494   极小值为   f(x)≈1.750  实际上,函数f(x)在区间［0,1］上的极小点为x=0.5,而极小值为f(x)=1.75。

48 设目标函数f(x)在x1,x2,x3(x1＜x2＜x3)三点的函数值分别为f1,f2和f3,作二次插值公式。令二次插值多项式为
2.4 二次插值法 设目标函数f(x)在x1,x2,x3(x1＜x2＜x3)三点的函数值分别为f1,f2和f3,作二次插值公式。令二次插值多项式为 P(x)=a0+a1x+a2x (7―15) 它应满足 P(x1)=a0+a1x1+a2x21=f1 P(x2)=a0+a1x2+a2x22=f2 P(x3)=a0+a1x3+a2x23=f3 (7―16)

49 (7―17)式就是计算近似极小点的公式。只要求出a1和a2, 这个极小点就确定了。具体做法如下:
对多项式(7―15) 求导数并令其等于零,则 P′(x)=a1+2a2x=0   解得 (7―17) (7―17)式就是计算近似极小点的公式。只要求出a1和a2, 这个极小点就确定了。具体做法如下: 在方程组(7―16)中消去a0,得到含a1,a2的方程组

50 (7―18) 解这个方程组得

51 将a1、a2代入(7―17)式得 (7―19) 若取x1,x2,x3为等距基点,即   x3-x2=x2-x1=Δx 则(7―19)式可简化为

52 ①令   c1=(f3-f1)/(x3-x1) c2=((f2-f1)/(x2-x1)-c1)/(x2-x3)   ② x=0.5×(x1+x3-c1/c2) 其计算框图比较复杂,读者可参阅南京大学计算数学专业著《最优化方法》。

53 §3 非线性最小二乘法 在实际问题中,我们经常碰到一种特殊类型的最优化问题,即目标函数为平方和形式 例如,求解非线性方程组
§3 非线性最小二乘法 在实际问题中,我们经常碰到一种特殊类型的最优化问题,即目标函数为平方和形式 例如,求解非线性方程组   fi(x)=0, i=1,2,…,n (7―21) (7―20)

54 可化为求平方和函数 的极小点。 这类函数的极小问题,也可以用前面介绍的方法求解。但由于该目标函数的特殊形式,我们试图通过某些方法进行改造简化,从而寻找求解该目标函数极小值的较简便方法。

55 令 则目标函数还可写为 F(x)=fT(x)f(x) (7―22) 假设fi(x)具有一阶连续偏导数

56 根据极值理论,F(x)存在极小值的必要条件为
亦即

57 于是,可得到 (7―23)

58 令 则(7―23)式可化为下列方程组 (7―24)

59 即  ATf= (7―25)  常称A为雅可比矩阵, 而(7―25)式为非线性最小二乘法的法方程。这样求F(x)的最小二乘解只要在n维空间Rn中找点x,使其满足(7―25)。 设 给定初始点

60 则将函数fi(x)在x0点附近展成泰勒级数到线性项为
i=1,2,…,m, (7―26)

61 由于 因此

62 (7―27) 这里 于是

63 这样,非线性最小二乘法的法方程为 AT0(f(x0)+A0Δx0)= (7―28) 即   AT0A0Δx0=-AT0f(x0) 若矩阵A0的列向量为线性无关,则AT0A0为对称正定矩阵,故可逆,于是求得   Δx0=-(AT0A0)-1AT0f(x0) (7―29) 故近似极小点   x1=x0+Δx (7―30)

64 重复上述计算过程,直到对于预先给定的精度ε,使得
  ｜Δxk｜＜ε  为止。或者   ｜gradF(xk+1)｜＜ε′(ε′为预给的精度) 从而得到极小点   xk+1 =xk+Δxk  和极小值F(xk+1)。

65 图 7.14

66 图 7.15

67 §4 最速下降法 我们已经知道,求多元函数的极小值可化为逐次从某点xk(k=0,1,2,…)出发,沿寻查方向pk(k=0,1,2,…)求最优步长因子tk(k=0,1,2,…),以 xk+1=xk+tkpk k=0,1,2,…

68 逼近函数的极小点x。这里寻查方向pk的选择是个关键。由极值理论,多元函数F(x)(x∈Rn)在xk点的最速下降方向为该点的负梯度方向,即
(7―33)

69 也就是,在xk点使函数F(xk)下降得最快的方向为该点的负梯度方向。
最速下降法是取负梯度方向作为寻查方向,故也称梯度法或斜量法。 对于目标函数F(x),在点xk处取寻查方向 pk=-gk=-gradF(xk)

70 这里-gk与等高面在xk点的切面垂直,见图7
这里-gk与等高面在xk点的切面垂直,见图7.16。沿pk方向求最优步长因子tk,使得F(xk+tkpk)为极小值。重复上述过程,直到满足预给精度为止。 最速下降法的计算步骤为: ① 给定初始出发点x0和精度ε,x=x0。 ② 计算 p=-gradF(x)   ③若   ｜p｜＜ε

71 则转⑤;否则进行下一步。 ④用一维寻查方法求t使得F(x+tp)为极小值,令  x+tp x   并转②。 ⑤输出极小点x和极小值F(x)。 其计算框图见图7.17。

72 图 7.16

73 图 7.17

74 检验最优化方法的一个简单易行的原则是看它应用于二次函数的情形如何。因为对于一般的非线性函数来说,其在极小点附近的性态接近于二次函数的性态。
下面求二次函数的最优步长因子。 设二次函数 (7―34) 其中A为n阶对称正定矩阵,b为常向量,c为常量,此 时,最优步长因子 (7―35)

75 这是因为 于是 因此 也即

76 例2 用最速下降法求二次函数 的极小点和极小值。取初始点 ,精度ε=0.1。 解 F(x)的矩阵向量表示形式为

77

78 于是

79 从而有 由于 故满足精度的极小点为 极小值为

80 实际上,F(x)的准确极小点可由 g(x)=0   求得 其极小值为

81 §5 共轭斜量法 共轭斜量法是对最速下降法的一种改进。现就n元二次函数讨论共轭斜量法。 定义设A是n阶对称正定矩阵,若n维向量p,g满足关系
§5 共轭斜量法 共轭斜量法是对最速下降法的一种改进。现就n元二次函数讨论共轭斜量法。 定义设A是n阶对称正定矩阵,若n维向量p,g满足关系   pTAg= (7―36)

82 则称向量p与g为A共轭或A直交向量。 定理对于n元二次函数(7―34),若所取的寻查方向 p0,p1,…,pn-1为A共轭, 则n步即可求得极小点xn,即有 gn=gradF(xn)=0 由上述定理知,对于二元二次函数,只要找到两个A共轭方向作为寻查方向,最多两步就可求得极小点,如图7.18所示。

83 图

84 对于n元二次函数(7―34),设x0为任取的初始点,而即将寻查的A共轭方向为
 p0,p1,…,pk,pk+1,…   且依次沿这些方向求得的各次近似极小点分别为 x1,x2,…,xk+1,xk+2,… 因为 gk=g(xk)=Axk+b xk+1=xk+tkpk

85 于是   g k+1=Ax k+1+b =A(xk+tkpk)+b =Axk+b+tkApk =gk+tkApk 即   gk+1-gk=tkApk (7―37) 由于

86 pTiApk=0, i≠k (7―38)  也就是 pTi(gk+1-gk)= (7―39) 其次建立共轭斜量法。 从给定的初始点x0出发,取   p0=-g0  沿此方向用一维寻查方法求出最优步长因子t0,从而求得 x1=x0+t0p0 计算 g1=g1(x1)

87 因为   f(t)=F(xk+tpk)  则  f′(tk)=gradF(xk+tkpk)Tpk=0  亦即  gTk+1pk= (7―40) 于是   gT1p0=0

88 由此知,g1与g0也直交,因此g0,g1构成了一个直交系。在这个直交系所张成的二维空间里寻找p1,使p1与p0为A共轭。
作线性组合   p1=-g1+α0g (7―41) 由(7―39)式,要p1与p0为A直交,应有 pT1(g1-g0)=0 (-g1+α0g0)T(g1-g0)=0 于是有 gT1g1+α0gT0g0=0

89 即 (7―42) 假定g0≠0(否则x0即为所求的极小点),则 (7―43)

90 再沿p1方向求近似极小点x2 x2=x1+t1p1 g2=g(x2) 因为p0,p1为A共轭,据(7―39)有 即 可得到 由(7―40)式得

91 作线性组合 p2=-g2+α1g1+α0g0 (7―44) 要p2与p0,p1均为A共轭,用(7―39)式应有
(-g2+α1g1+α0g0)T(g1-g0)=0 (-g2+α1g1+α0g0)T(g2-g1)=0 仿前假定g1≠0,解(7―46)式得 (7―45) (7―47)

92 由(7―44)和(7―47)式可得 p2=-g2-β1g1-β0β1g0 =-g2+β1(-g1-β0g0) 因此
  p2=-g2+β1p (7―49) 再沿p2方向求极小点x3,…,一般有递推公式 (7―50)

93 从理论上讲,共轭斜量法对于n元二次函数在n步以内可达到极小点。但在实际计算时,由于舍入误差的影响,一般要超过n次才能达到满足精度的结果。
共轭斜量法的计算步骤为: ①给定初始点x0和精度ε。 ②0 xi。 ③0 i。 ④计算F(xi),gi。 ⑤若｜gi｜＜ε,则输出结果并结束;否则继续下一步。 ⑥若i＜n,则进行下一步;否则令

94 并转③。 ⑦当i=0时,则 -gi pi   否则   gi+βi-1pi-1 pi 其中

95 ⑧用一维寻查方法求ti,使F(xi+tipi)为极小值,令
并转向④。 必须说明,若目标函数F(x)为二次函数,则最优步长因子 共轭斜量法的计算框图见图7.19。

96 图 7.19

97 §6 变尺度方法 共轭斜量法是最速下降法的一种改进,而变尺度方法又是共轭斜量法的改进。现就二次目标函数对寻查方向进行分析,从而阐述变尺度方法的基本思想。 对于二次目标函数(7―34)式,其在x点的梯度为 g(x)=Ax+b (7―51)   若x为F(x)的极小点,则有 g(x)=Ax+b= (7―52)

98 图 7.20

99 如果目标函数F(x)是非二次函数,则用泰勒公式在xk点展开到二次项
(7―55) 其中 称为赫申(Hessian)矩阵,其对称正定。我们可逐次取  pk=-A-1 kgk (7―56)

100 作为寻查方向,求一般函数F(x)的极小点。这就是变尺度方法的基本思想。这里当A-1k为单位矩阵时,即为最速下降法。
特别说明,若目标函数F(x)的二阶偏导数不易求得,直接采用(7―56)式作为寻查方向比较困难,可设法用其它矩阵H来逐步逼近赫申矩阵A的逆矩阵A-1。这样既避免了计算二阶偏导数,又不要计算逆矩阵。

101 例4 用变尺度方法求 的极小点和极小值。 解 这是二次函数,根据前面的讨论,任取初始点x0,取-A-1g(x)作为寻查方向,一步即可求出极小点

102 而

103 则 于是

104 §7 单纯形方法 7.1 单纯形方法的基本思想 前面介绍的最小二乘法、最速下降法、共轭斜量法及变尺度方法都必须计算目标函数的导数,而单纯形方法只需通过计算目标函数的值来逐步求极小点。我们先就对二元函数f(x,y)来谈谈单纯形方法的基本思想。

105 对于二元函数f(x,y),取不在同一条直线上的三点(见图7
对于二元函数f(x,y),取不在同一条直线上的三点(见图7.21),算出相应的函数值,并将函数值最大的点、次大的点、最小的点分别记为pH、pG、pL。这三点就构成初始单纯形｛pH、pG、pL｝。因为我们是求函数的极小点,所以函数值越大的点也就越“坏”。下面分三步确定寻查方向。 1.反射   过pH点并穿过连线pGpL的中点pC的方向上选一点pR,使得 pHpR=2pHpC (7―57) 称点pR为pH关于pC点的反射点,算出函数f(x,y)在点pC、pR的值fC、fR。

106 图 7.21

107 表明pR并不比pH好,也即前进得太远了,需要压缩, 可在pH与pR之间另取一新点pS。 3.扩张 若 fR＜Fh (7―59)
2. 压缩   若 (7―58) 表明pR并不比pH好,也即前进得太远了,需要压缩, 可在pH与pR之间另取一新点pS。 3.扩张   若 fR＜Fh (7―59)

108 则表明情况有改善,沿pHpC方向还可以试探走得更远一些,也即可以扩张。在pHpR的延长线上取一点pE,如果在pE点的函数值fE满足
  fE≤fR (7―60)   就取pE作为新点pS,否则取pR作为pS。 不管是压缩还是扩张,都得到一个新点pS,若   fS＜fG (7―61)   则把原来的点pH换成改进的新点pS。这样得到一个新的单纯形｛pS,pG,pL｝,重复上述步骤,直至获得满足精度的极小点为止。

109 若式(7―61)不成立,即   fS≥fG (7―62)   则表明将pH换成pS时情况没有多少改善。此时可把原先的单纯形｛pH,pG,pL｝向pL点收缩,可取连线pHpL和pGpL的中点p1、p2与pL重新构成新的单纯形｛p1,p2,pL｝(见图7.22),然后按照前述方法重新开始寻查。

110 图

111 一般地,对于n元函数f(x),在n维空间里取n+1个不同在n-1维超平面上的点x0,x1,…,xn构成初始单纯形,比较各点的函数值,最坏点被改进的新点代替,构成新的单纯形,逐步逼近极小点。

112 构造单纯形的方法较多,这里我们仅介绍一种最基本的方法。
7.2 初始单纯形的构造 构造单纯形的方法较多,这里我们仅介绍一种最基本的方法。   令 (7―63) 其中ei为单位坐标向量,即 行

113 h为初始步长。这样,除x0点外,其它n个点x1,x2,…,xn均是从x0出发沿着各坐标方向前进了一步h。
例如,在二维空间中取初始点 取步长h=1,于是

114 7.3 单纯形方法的计算步骤及框图 单纯形方法的计算步骤为: ①计算函数值   i=0,1,2,…,n  比较函数值的大小,决定最坏点xH,最好点xL,次坏点xG。

115 ②算出除xH以外的n个点的中心点 求出反射点xR及其函数值yR ③若 yR≥yH  则进行压缩,并令   xS=(1-λ)xH+λxR,0＜λ＜1 其中λ称为压缩因子。

116 进行扩张,令   (1-μ)xH+μxR xE   其中μ＞1,这里μ为扩张因子。实践经验一般取1.2＜μ＜2。这里扩张条件   yR＜yH  也可换成  yR＜yL 或  (1-μ)yH+μyR＜yL

117 或 若 则令 否则 ⑤若 则

118 从而新的xH与其它的n个点一起构成新的单纯形,重新确定xH,xG和xL,并重复前述步骤;否则进行下一步。
然后转向①。 上述过程一直继续到满足 为止(ε为预先给定的精度)。