胡毓達(dá)

教授，上海交通大學(xué)數(shù)學(xué)系，上海 200240

優(yōu)選法的對(duì)稱試驗(yàn)最優(yōu)性

胡毓達(dá)

教授，上海交通大學(xué)數(shù)學(xué)系，上海 200240

優(yōu)選法；斐波那契數(shù)列；黃金分割數(shù)

在實(shí)際應(yīng)用中，通過(guò)試驗(yàn)的辦法盡快求得只有一個(gè)最優(yōu)方案問(wèn)題的近似最優(yōu)方案的方法，統(tǒng)稱為優(yōu)選法。利用斐波那契數(shù)列和黃金分割數(shù)來(lái)構(gòu)建的近似黃金分割法類，是優(yōu)選法中最重要和常用的一類方法。本文給出了近似黃金分割法類的第一個(gè)試驗(yàn)點(diǎn)與相應(yīng)試驗(yàn)方法具有最大對(duì)稱試驗(yàn)最優(yōu)性次數(shù)之間的關(guān)系，據(jù)此可以判定任一近似黃金分割法的最大對(duì)稱試驗(yàn)最優(yōu)性次數(shù)。

20世紀(jì)60—70年代，中國(guó)數(shù)學(xué)家華羅庚提倡在全國(guó)推廣被稱為“優(yōu)選法”的應(yīng)用，在工礦企業(yè)取得了普遍成效。于是，在這類“盡可能少做試驗(yàn)、盡快地找到生產(chǎn)最優(yōu)方案的方法”[1]中，使用最多的“0.618法”在民眾中曾廣為傳播。鑒于“0.618法”的最優(yōu)性常常會(huì)與理論上的“黃金分割法”的最優(yōu)性相混淆，特別是在不少著作中甚至就將“0.618法”等同于“黃金分割法”。為此，本文將對(duì)優(yōu)選法中最典型的“n次斐波那契法”“黃金分割法”和“0.618法”等黃金分割法類，在搜索最優(yōu)方案時(shí)的最優(yōu)性問(wèn)題作出統(tǒng)一綜述和澄清。

1 單峰問(wèn)題與對(duì)稱試驗(yàn)方法

在現(xiàn)實(shí)世界中，許多事物都會(huì)具有某種意義下的最優(yōu)性問(wèn)題。例如，一些化工產(chǎn)品有原材料的最優(yōu)配比問(wèn)題，機(jī)床上的刀具加工零部件有最優(yōu)切削角問(wèn)題，加工某些食品時(shí)則有最優(yōu)溫度問(wèn)題，等等。這些要尋求最優(yōu)配比、最優(yōu)切削角和最優(yōu)溫度的問(wèn)題的共同點(diǎn)，都是要在它們的所有可能方案中，求得其最優(yōu)方案的問(wèn)題。在數(shù)學(xué)上，則都?xì)w結(jié)為在區(qū)間[0，1]上，尋求只有一個(gè)峰(最大)值函數(shù)φ(x)，使其函數(shù)值達(dá)到最優(yōu)(大)的最優(yōu)(大)點(diǎn)的問(wèn)題(求最小值可轉(zhuǎn)化為求其負(fù)數(shù)的最大值）。一般地，設(shè)φ(x)是區(qū)間[a,b](a＜b)上的單值(只有一個(gè)值的)函數(shù)，如存在一點(diǎn)x*∈(a,b)，使得φ(x)在[a,x*]上嚴(yán)格遞增，同時(shí)在[x*,b]上嚴(yán)格遞減，則稱φ(x)是[a,b]上的單峰函數(shù)，[a,b]是φ(x)的單峰區(qū)間。在單峰區(qū)間[a,b]上，求使單峰函數(shù)φ(x)取得最優(yōu)(大)值的最優(yōu)(大)點(diǎn)x*的問(wèn)題，稱為單峰問(wèn)題。

由于在實(shí)際應(yīng)用中出現(xiàn)的單峰問(wèn)題，一般都無(wú)法寫出其單峰函數(shù)的解析表達(dá)式。因此，對(duì)于這類問(wèn)題的實(shí)用求解方法是：通過(guò)直接試驗(yàn)取得試驗(yàn)點(diǎn)處的函數(shù)值，然后經(jīng)試驗(yàn)函數(shù)值的比較，淘汰掉最優(yōu)點(diǎn)不在其中的“廢區(qū)間”，逐次縮小單峰區(qū)間來(lái)求得其近似最優(yōu)點(diǎn)。此類方法統(tǒng)稱為淘汰廢區(qū)間方法。

設(shè)x*是[0, 1]中單峰函數(shù)φ(x)的最優(yōu)點(diǎn)。為更快地求得x*的近似點(diǎn)，通常采用如下在單峰區(qū)間[0, 1]中逐步進(jìn)行“對(duì)稱試驗(yàn)”的淘汰廢區(qū)間方法。具體做法是：第1步，在第1級(jí)單峰區(qū)間[0, 1]中，取第1個(gè)(次)試驗(yàn)點(diǎn)x1(＞0.5)和與它對(duì)稱的第2個(gè)試驗(yàn)點(diǎn)x2=1－x1(＜0.5)，然后比較φ(x1)和φ(x2)的值。這時(shí)有以下3種可能：①若φ(x1)＞φ(x2)，必有x*∈[x2,1]和x*∈/ [0,x2]，故可淘汰掉廢區(qū)間[0,x2]，留下縮小了的第2級(jí)單峰區(qū)間[t1,t2]=[x2, 1]和留下第2次試驗(yàn)點(diǎn)=x1(圖1(a))；②若φ(x1)＜φ(x2)，必有x*∈[0,x1]，同理淘汰掉廢區(qū)間[x1, 1]，留下第2級(jí)單峰區(qū)間[t1,t2]= [0,x1]和第2次試驗(yàn)點(diǎn)=x2(圖1(b))；③若φ(x1)=φ(x2)，因有x*∈[x1,x2]，則可隨意淘汰掉[0,x2]或者[x1, 1]，留下第2級(jí)單峰區(qū)間[t1,t2]=[x2, 1]或[0,x1]和第2次試驗(yàn)點(diǎn)=x1或x2(圖1(c))。如此，不論發(fā)生哪一種情況，都可以將第1級(jí)單峰區(qū)間[0, 1]縮小成第2級(jí)單峰區(qū)間[t1,t2]。這時(shí)，完成了第1步對(duì)稱試驗(yàn)。第2步，在第2級(jí)單峰區(qū)間[t1,t2]中，再選取第2次試驗(yàn)點(diǎn)的對(duì)稱試驗(yàn)點(diǎn)x3，經(jīng)同樣的函數(shù)值比較之后，又可淘汰掉廢區(qū)間，得到又縮小了的第3級(jí)單峰區(qū)間[t2,t3]和留下第3次試驗(yàn)點(diǎn)(圖2)，等等。按照以上做法，在單峰區(qū)間[0, 1]上連續(xù)取n(≥2)個(gè)試驗(yàn)點(diǎn)和做n-1步對(duì)稱試驗(yàn)的方法，稱為[0, 1]上的n次對(duì)稱試驗(yàn)方法，簡(jiǎn)記“x1法”。

圖1 淘汰廢區(qū)間方法

圖2 n次對(duì)稱試驗(yàn)方法

上述采取對(duì)稱試驗(yàn)方法來(lái)縮小單峰區(qū)間，以逐步尋求問(wèn)題的近似最優(yōu)點(diǎn)，其原因是由于事先人們并不知道所考慮問(wèn)題中單峰函數(shù)的性態(tài)。事實(shí)上，不論所考慮單峰函數(shù)的性態(tài)如何，只要用對(duì)稱試驗(yàn)方法，不管淘汰掉哪一個(gè)廢區(qū)間，所留下單峰區(qū)間的長(zhǎng)度都是相等的。如若采用兩個(gè)試驗(yàn)點(diǎn)在單峰區(qū)間中是不對(duì)稱的試驗(yàn)方法，經(jīng)函數(shù)值比較之后，可能會(huì)留下較長(zhǎng)的單峰區(qū)間(圖3)。因此，使用對(duì)稱試驗(yàn)方法總要比用不對(duì)稱的試驗(yàn)方法好。

圖3 不對(duì)稱試驗(yàn)方法

2 斐波那契數(shù)列和黃金分割數(shù)

本節(jié)介紹優(yōu)選法中兩個(gè)重要概念：斐波那契數(shù)列和黃金分割數(shù)。

1202年，意大利數(shù)學(xué)家列奧納多(Leonardo)在署名為斐波那契(Fibonacci L.)的一本《算盤冊(cè)(Liber Abaci)》的書中[2]，曾提出下面的兔子繁殖問(wèn)題：兔子出生后兩個(gè)月可生小兔，設(shè)1對(duì)兔子每月恰生一雄一雌兩只小兔，現(xiàn)若飼養(yǎng)了1對(duì)初生的小兔，問(wèn)一年后共有多少對(duì)兔子？

對(duì)于此問(wèn)題，我們可以按圖4(a)(黑色的為成熟兔子，白色的為未成熟兔子)推算如下：

第0個(gè)月后(第1個(gè)月中)，有1對(duì)未成熟小兔；

第1個(gè)月后，小兔成熟，仍只有1對(duì)兔子；

第2個(gè)月后，這對(duì)老兔子生了1對(duì)小兔，共有2對(duì)兔子；

第3個(gè)月后，老兔子又生了1對(duì)小兔，而上月出生的小兔成熟，這時(shí)共有3對(duì)兔子；

第4個(gè)月后，老兔子和第2個(gè)月后出生的兔子(已成熟)各生1對(duì)，連同它們本身計(jì)有4對(duì)，加上上月出生的小兔成熟，這時(shí)共有5對(duì)兔子；

圖4 斐波那契數(shù)列的實(shí)例

…………

按此推算，可得表1。由此可知，答案是：一年(第12個(gè)月)后共有兔子233對(duì)。

表1 兔子繁殖問(wèn)題

此外，如樹木分枝問(wèn)題的年份和分枝數(shù)(圖4(b))，以及蜜蜂家系問(wèn)題的傳代數(shù)和祖先數(shù)之間，等等，也都遵循上述規(guī)律。

將表1中的月份數(shù)記作n(=0, 1, 2,…)，相應(yīng)的兔子對(duì)數(shù)記作Fn，則有：{Fn}={1，1，2，3，5，8，13，21，34，55，89，144，233，377，…}。從兔子繁殖的規(guī)律，不難得知在數(shù)列{Fn}中，首兩項(xiàng)為F0=1和F1=1，3個(gè)相連項(xiàng)之間有如下遞推關(guān)系：

人們將具有上述性質(zhì)的數(shù)列{Fn}，稱為斐波那契數(shù)列，其中的Fn稱為斐波那契數(shù)[2]。

另外，設(shè)ω是正實(shí)數(shù)，若它具有關(guān)系：

則稱ω是[0, 1]中的黃金分割數(shù)，它在單位區(qū)間中的對(duì)應(yīng)點(diǎn)叫黃金分割點(diǎn)，它把單位長(zhǎng)度分割為兩部分叫黃金分割或黃金分割比。根據(jù)式(2)可知，黃金分割的幾何意義是：黃金分割點(diǎn)ω在單位區(qū)間[0, 1]中的位置，相當(dāng)于它在[0,1]中的對(duì)稱點(diǎn)1-ω在區(qū)間[0, ω]中的位置。

在現(xiàn)實(shí)世界中，黃金分割現(xiàn)象普遍存在。特別是在建筑藝術(shù)中，人們認(rèn)為使用黃金分割比的設(shè)計(jì)是最美的，因此在許多著名建筑中窗戶的寬與高之比常取黃金分割比(圖5(a))。又如，“標(biāo)準(zhǔn)”人體的肚臍高與身高之比，以及手肘到指尖與臂長(zhǎng)之比，也都是黃金分割數(shù)(圖5(b))，等等。

從(2)可知，黃金分割數(shù)ω滿足二次方程ω2+ω-1=0。求解此方程，得其正根即黃金分割數(shù)：

由(1)和(3)，可以證明斐波那契數(shù)和黃金分割數(shù)之間有如下關(guān)系[1,3]：

圖5 意大利建筑大師阿爾伯蒂(A lberti L. B., 1404－1472)用黃金分割比建造的代表作——魯奇蘭府邸(左圖)；人體中的黃金分割比(右圖)

3 斐波那契法和黃金分割法

現(xiàn)在，分別利用斐波那契數(shù)列和黃金分割數(shù)來(lái)構(gòu)造優(yōu)選法中尋求[0, 1]上單峰問(wèn)題近似最優(yōu)點(diǎn)的兩個(gè)典型方法。

先給出由斐波那契數(shù)列來(lái)構(gòu)造的方法。

n次斐波那契法設(shè)φ(x)是[0, 1]上的單峰函數(shù)。

(ii)逐步按對(duì)稱試驗(yàn)方法進(jìn)行。

(iii)直至給出第n次試驗(yàn)點(diǎn)后，取最后留下的點(diǎn)作為問(wèn)題的近似最優(yōu)點(diǎn)。

下面介紹利用黃金分割數(shù)來(lái)構(gòu)造求單峰問(wèn)題近似最優(yōu)點(diǎn)的方法。

黃金分割法設(shè)φ(x)是[0, 1] 上的單峰函數(shù)。

(i)在第1級(jí)單峰區(qū)間[0, 1]中，取第1個(gè)試驗(yàn)點(diǎn)為x1=ω和與它對(duì)稱的第2個(gè)試驗(yàn)點(diǎn)x2=1-ω。比較φ(x1)和φ(x2)的值之后淘汰掉廢區(qū)間，留下第2級(jí)單峰區(qū)間和留下第2次試驗(yàn)點(diǎn)=ω或1-ω。

(ii)逐步按對(duì)稱試驗(yàn)方法進(jìn)行。

(iii)直至最后得到足夠小的留下的單峰區(qū)間，取其中點(diǎn)(或其中任意一點(diǎn))，作為問(wèn)題的近似最優(yōu)點(diǎn)。

這種利用黃金分割數(shù)ω來(lái)確定第1個(gè)試驗(yàn)點(diǎn)，連續(xù)做n次試驗(yàn)(n-1步對(duì)稱試驗(yàn))的方法，叫做n次黃金分割法，簡(jiǎn)記“ω法”。

黃金分割法的最優(yōu)性[5]：對(duì)于[0, 1]上的單峰問(wèn)題，記Δn[ω法]是“ω法”做n次試驗(yàn)后最后留下區(qū)間的長(zhǎng)度，則對(duì)于任意一個(gè)淘汰廢區(qū)間方法U≠“ω法”，總存在一個(gè)正整數(shù)N(≥2)，當(dāng)n≥N后必有Δn[ω法]＜Δn[U]，其中Δn[U]是U做n次試驗(yàn)后最后留下區(qū)間的長(zhǎng)度。

黃金分割法的這一性質(zhì)說(shuō)明，對(duì)于[0, 1]上任意一個(gè)單峰問(wèn)題，用[0, 1]上的其他任何一個(gè)淘汰廢區(qū)間方法來(lái)尋求它的最優(yōu)點(diǎn)時(shí)，總存在一個(gè)試驗(yàn)次數(shù)，在這個(gè)次數(shù)之后，黃金分割法最后留下的n次區(qū)間精度與該淘汰廢區(qū)間方法的n次區(qū)間精度相比是“最小的”。通常人們把黃金分割法的這一性質(zhì)叫做黃金分割法具有無(wú)窮遠(yuǎn)處最優(yōu)性。由黃金分割法的第1個(gè)試驗(yàn)點(diǎn)ω和尋優(yōu)步驟，利用(2)可以推得Δn[ω法]=ωn-1。另外，從黃金分割法的試驗(yàn)步驟還可得知，使用它來(lái)尋求單峰問(wèn)題的近似最優(yōu)點(diǎn)時(shí)，并不受試驗(yàn)次數(shù)的限制。但是，黃金分割法的不足是，黃金分割數(shù)ω是一個(gè)無(wú)理數(shù)，因此這一方法只具有理論上的意義。在應(yīng)用中，實(shí)際上是無(wú)法使用它來(lái)尋求單峰問(wèn)題的最優(yōu)點(diǎn)的。

4 近似黃金分割法及其對(duì)稱試驗(yàn)最優(yōu)性

從上一節(jié)的介紹，我們知道，用n次斐波那契法來(lái)尋求單峰問(wèn)題的最優(yōu)點(diǎn)，要受到試驗(yàn)次數(shù)的限制；而黃金分割法中的黃金分割數(shù)是一無(wú)理數(shù)，在應(yīng)用中又無(wú)法用它來(lái)進(jìn)行數(shù)值計(jì)算。為了克服這兩個(gè)方法的不足，我們來(lái)考慮在對(duì)稱試驗(yàn)方法中，取第1個(gè)試驗(yàn)點(diǎn)為有理近似黃金分割數(shù)的方法，同時(shí)，考察此類方法是否具有某種最優(yōu)性？若有，則它具有怎樣的最優(yōu)性？

近似黃金分割法設(shè)φ(x)是[0, 1] 上的單峰函數(shù)。

(ii)逐步按對(duì)稱試驗(yàn)方法進(jìn)行。

(iii)直至得到足夠小的留下的單峰區(qū)間，取其中點(diǎn)(或其中任意一點(diǎn))作為問(wèn)題的近似最優(yōu)點(diǎn)。

近似黃金分割法的最優(yōu)性[6]對(duì)于[0, 1]上的單峰問(wèn)題，記有理數(shù)≈ω是近似黃金分割法的第1個(gè)試驗(yàn)點(diǎn)。若n是使

成立的m的最大值，則其n次區(qū)間精度Δn[法] ＜Δn[x法](其中當(dāng)n是偶數(shù)時(shí)，x∈(0.5,1)/當(dāng)n是奇數(shù)時(shí)，x∈(0.5,1)/

上述近似黃金分割法的最優(yōu)性的意義是，對(duì)于[0, 1]上任意一個(gè)單峰問(wèn)題，當(dāng)n是滿足(5)的m的最大值時(shí)，由“法”做n次試驗(yàn)后，其最后留下的n次區(qū)間精度Δn[法]與其他任何“x法”(n是偶數(shù)時(shí)，x∈(0.5,1)/(]；n是奇數(shù)時(shí)，x∈(0.5,1)/[)的n次區(qū)間精度相比是“最小的”。近似黃金分割法的這一性質(zhì)，稱為“法”具有n次對(duì)稱試驗(yàn)最優(yōu)性，其中的n是“法”的最大對(duì)稱試驗(yàn)最優(yōu)性次數(shù)。從近似黃金分割法的第1個(gè)試驗(yàn)點(diǎn)，由(1)用數(shù)學(xué)歸納法可以推得它的n次區(qū)間精度

表2 前5個(gè)近似黃金分割法以及n次斐波那契法和黃金分割法對(duì)應(yīng)的最大對(duì)稱試驗(yàn)最優(yōu)性次數(shù)及其區(qū)間精度

(2013年10月22日收稿)

[1] 華羅庚. 優(yōu)選學(xué)[M]. 北京: 科學(xué)出版社, 1981.

[2] Β о р о б ъ?в НН. Ч и с л а Ф и б о н а ч ч и [M]. М о с к в а: С о в е т с к и х Н а ц и о н а л ь н ы х Т е х н и ч е с к и хК н и г Т е о р и и и П у б л и к а ц и й Б ю р о, 1951.

[3] 胡毓達(dá). 非線性規(guī)劃[M]. 北京: 高等教育出版社, 1990.

[4] KIEFER J. Sequential m inimax search for a m aximun [J]. Proc Amer Math Soc, 1953, 4: 502-506.

[5] 洪加威. 論黃金分割法的最優(yōu)性[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 1973, 2: 34-41.

[6] 胡毓達(dá). 論異側(cè)對(duì)稱策略的最優(yōu)性[J]. 上海交通大學(xué)學(xué)報(bào), 1979, 3: 67-77.

(編輯：沈美芳)

The optimality of symmetry trial on optimum seeking methods

HU Yu-da
Professor, Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, China

Optimum seeking methods are those that in practice seek to obtain approximate optimal alternatives through trials for problem s w ith one optimum value. Approximate golden section methods, which use Fibonacci sequence or golden section number, constitute a class of methods that are most important and most often used. This paper gives the relationships of the fi rst trial point and the maximal number of the optimality of symmetry trials of approximate golden section methods. With these relationships, the maximal number of the optimality of symmetry trials can be determined for any approximate golden section method.

optimum seeking method, Fibonacci sequence, golden section number

10.3969/j.issn.0253-9608.2014.04.008