數學傳播

一、引言

2014年 3 月 8 日淩晨 1 時 20 分, 馬來西亞航空公司航班 MH370 失聯, 機上有乘客 239 人/中國乘客 154 名, 至今搜索失敗, 常常感到有錐心之痛, 原因何在? 搜索失聯客機, 是一個典型的搜索問題, 以最快的方法找到客機, 那就是一個最優搜索問題。 這類問題隨處可見, 例如國防: 敵方的潛水艇沿長江口潛入內陸, 如何及早發現? 又如國家 的宏觀經濟, 如何實現較優的調控? 就看日常生活中的烹調, 放多少水做出來的米飯最好吃 等等。 人們每天都在尋求最佳方案, 本文是這個失聯事件所觸發的關於最優搜索問題的一點 思考, 雖是紙上談兵, 但願對於處理實際搜索問題有所幫助。

本文也希望為如何做數學提供一個案例, 何為創新? 何為好數學? 如何選方向/選題? 如何步 步深入?

從數學上講, 在許多情況下, 這是一個尋找函數的最大/最小值問題。 也許, 大家會覺得這很容易, 我們已經在分析和計算課程中學過不少方法。 問題是那裏預先假定函數的解析表達式 是己知的, 這未必可行, 例如我們並不知道米飯「好吃」的表達式是什麽, 也不知道尋找 MH370 應該用什麽函數來刻畫。 當然, 如果知道函數的類型, 則可通過實驗尋找函數的表達式, 這常常需要做大量的實驗, 成本很高。 退一步說, 即使表達式是己知的, 大多算法也未必高效。 我們要尋找的是直接搜索方法, 無需預知目標函數的表達式, 這好像也不難, 就像 「瞎子爬山」, 哪裏高就往哪裏爬就是了, 此即是一種直接搜索方法, 有時可行, 但太慢, 也缺乏藝術性和數學美感。

從現在開始, 我們要離開 MH370 一陣子, 待有足夠的準備之後, 再回來。

我國著名數學家華羅庚先生把處理這類問題的數學方法稱為「優選法」: 即不僅要求優、 而且要以最好方法求優。 早在 1970 年代, 他帶領推廣優選法小分隊到全國各地開展推廣優選法的實踐活動。 我本人曾有幸參加 1975 年在山西省的「推優小分隊」。 這項工作的困難程度遠非現在可以想像。 首先, 需從浩繁的文獻中, 找出在理論上可靠、又在實際中可用、並適合於科普的方法, 須知那時候的大多數工人群眾只有小學文化程度, 懂算術、但不懂代數, 到工廠、車間去給工人們講解優選法, 既無黑版、 又無粉筆可用, 如何講解？ 為此, 先介紹華先生所發明了一種「折紙條法」。

在開始介紹我們的方法之前, 請大家先記住一個常數： 0.618, 假定我們所關心的試驗範圍是 1000 到 2000 個單位, 那麽, 第一個試驗點就選在這個範圍內的 0.618 處：

把紙條在中間對折過來, 剛才的試驗點 ① 對應過來就有第二個試點 ②:

有了兩次試驗, 就可以進行比較。 如 ① 比 ② 好, 就可去掉 不好的那一段(即 ② 左邊的那一段)；反之, 如 ② 比 ① 好, 則可去掉 ① 右邊 的那一段：

現在, 餘下的範圍是

中間是上次留下的已試好點 ②。 下一步, 再將紙條對折, 由 ② 可 找到它的對稱點 ③；在此處做第 3 次試驗。

然後再去掉不好的那一段, 例如說, 此時 ② 比 ③ 好, 去掉 ③ 左邊的那一段,

留下

再折紙條, 得到 ② 所對應的第 4 個試驗點：

如此繼續「去掉」和「對折」程序, 經過 $2\sim 5$ 次試驗, 常可找到滿意的解答。 概括起來, 除了牢記常數 0.618 和決定初始搜索範圍而外, 僅有兩個要點：

• 第一個試驗點為: 起點 $+$ (試驗範圍的)長度 $\times 0.618$。
• 為計算對折所找的新試驗點, 使用口訣：加兩頭、減中間, 即新試驗點等於上次試驗所餘範圍的兩頭相加、再減去中間的已試驗點。

這裏所用到數學僅有算術而已, 無需粉筆、黑版, 隨時隨地可以宣講。 在歷史上, 將如此先進的現代數學方法用這麽通俗的方式直接交到廣大工人手裏, 相信這是前無古人的, 意義非凡, 價值非凡。 「折紙條法」 也俗稱為「0.618 法」, 後面我們還會給出其學名。 其實, 講到這裏, 已經可以討論 MH370 的搜索問題了, 但我們寧願讓大家再想想, 後面再來討論。

二、最優試驗方法的探求與發展

單峰函數與試驗策略

粗略地說, 我們的目標是尋找函數的最大值, 研究任何問題的要點之一是從簡單入手。 因此, 我們先限於單個變數的單峰函數: 它僅有一個最大值, 在 $c_f$ 處取到； 在其兩邊, 函數嚴格單調(但未必連續), 如圖 1 所示。 我們需要細心考察單峰函數的性質。 如圖2, 放進一個試驗點 $x_1$, 對於圖 2 中的單峰函數, $c_f\gt x_1$, 但對於另外的單峰函數, 可能有 $c_f\lt x_1$。 這樣, 對於一般的單峰函數, 一個試點 不足以判定最大值點處於何處: 左邊或右邊？

我們指出, 在一些特別情形, 有一個試點便可決定存留。 例如修水管,。 假定左邊有水, 右邊無水。 那就查中點, 如有水, 左半邊可忽略, 然後如法炮製處理右半邊, 規則是： 每次新試點取為上次餘下範圍的中點。 在這種特殊情況下, 這種方法是最優的, 稱為「 對分法」。

回到單峰函數情形, 需要兩個試點(圖 3), 有了兩個結果, 就可以進行比較, 並去掉一部分範圍, 見圖4$\sim$6。

在確定了函數類之後, 自然要分析一下我們所應採用的試驗策略(方法)。 圖 4$\sim$6 引導我們去考慮序貫求優, 即通過已試驗的位置和結果安排下一個試驗, 無妨設試驗範圍為單位區間 $[0, 1]$, 我們用 ${\scr F}$ 表示 $[0, 1]$ 上單峰函數的全體, 定義試驗策略 ${\scr P}$ 如次: 它的第 1 個試驗點 $x_1$ $({\scr P})$ 與 $f\in {{\scr F}}$ 無關; 第 $n$ $(n\ge 2)$ 個試驗點 $x_n$ 由策略 ${\scr P}$、 前 $n-1$ 個試驗點及其試驗結果決定： $$x_n=x_n\big({{\scr P}}; x_1, \ldots, x_{n\!-\!1}; f(x_1), \ldots, f(x_{n-1})\big). $$

上節所述的 0.618 法是一種簡明的策略, 也是上述策略類中的最優策略, 下面是另一個代表。

分數法

分數法使用 Fibonacci 數列： $F_0=F_1=1$,$\;$ $F_n=F_{n-1}+F_{n-2}$,$\;$ $n\ge 2$。$\\$ 它很像 0.618 法, 但需預先確定試驗的總次數 $n$ $(\ge 1)$。 此時, 分數法 ${{\scr F}}_n$ 的第一個試點取為 $x_1({{\scr F}}_n)\!=\!F_n/F_{n+1}$; 如同 0.618 法那樣, 以後各個試點依照對稱規則安排, 在最後的第 $n$ 步, 試點安排在第 $n-1$ 步留下的剩餘區間的中點, 其兩邊的長度恰好為 $1/F_{n+1}$, 往後對稱規則不能用了, 所以試驗到此終止; 除非重新開始, 但那就不是最優方法了。

三類最優試驗策略

我們以發展的時間順序, 介紹三類最優試驗策略。 為此, 需要判斷試驗策略優劣的標準, 即試驗精度。 回顧對於每一個 $f\in {\scr F}$, 都有峰值點 $c_f$: $f$ 在 $c_f$ 處達到最大。 另一方面, 經過 $n$ 步試驗, $n$ 個試點中, 必定有 $c_f({\scr P}, n)\in \{x_1, \ldots, x_n\}$ 使得 $f$ 在此處達到最大: $$f(c_f({\scr P}, n))=\max \{f(x_i): i=1,\ldots, n\}. $$ $c_f({\scr P}, n)$ 就是策略 ${\scr P}$ 在前 $n$ 步試驗中的最大值點, 因為我們期望我們的試驗策略適用於一切單峰函數, 所以定義 $$\delta({\scr P}, n)=\sup_{f\in {\scr F}} |c_f({\scr P}, n)-c_f|$$ 為 策略 $\pmb {\scr P}$ 的 $\pmb n$ 步精度, 這個概念以後在更廣的意義下保持不變, 這裏使用「$\sup_f$」 表示以最差情形 (即最大誤差) 作標準, 而不是以常用的平均作標準。 要理解它們之間的差別, 講個小例子, 我說我們學校有一個小團隊, 平均年齡 20 歲。 大家心裏會猜想, 這沒準是他們學校的排球隊, 隊員們個個身強力壯。 其實, 我心裏想的是我校的托兒所: 一個班的 6 個嬰兒加上 3 位老婆婆, 他們的平均年齡也是 20 歲, 「平均」當然好, 也常用, 例如在昆明, 「平均氣溫」好用, 因為每天溫差不大; 但「平均氣溫」在北京就不好用, 因為早晚的溫差較大, 這裏使用最大偏差做標準, 是因為對於不同函數的偏差可能相差很大, 非簡單地平均所能刻畫, 所以使用最大偏差最保險。 我們的目標是尋找某個試驗策略 ${\scr P}_0$, 使得最壞估計 $\delta({\scr P}, n)$ 在 ${\scr P}_0$ 處達到最小: $\inf_{\scr P}\delta({\scr P}, n)$。 在最優化理論中, 這稱為 極大極小化原理。

定理1[Jack Carl Kiefer (1953)] 分數法 ${\scr F}_n$ 是 $n$ 步最優策略: $$ \delta({\scr F}_n, n)=\inf_{\scr P}\delta({\scr P}, n) =F_{n+1}^{-1}. $$

Kiefer 在他的論文的末尾也指出: 預定試驗次數在實際應用中恐有不便, 他建議使用 $$\lim_{n\to\infty} x_1({\scr F}_n)=\lim_{n\to\infty}\frac{F_n}{F_{n+1}} =\frac{\sqrt{5}-1}{2}=:\omega $$ 作為近似, 代替 $x_1({\scr F}_n)$ 作為第 1 個試點, 然後依照對稱規則安排隨後的試驗, 這就是 黃金分割法(即 0.618) 法的原始來歷。 要證明上面的極限, 只需使用 $F_n$ 的遞推方程, 寫出連分數 $$\frac{F_n}{F_{n+1}}=\frac{1}{1+F_{n-1}/F_n}= \cfrac{1} {1+\cfrac{1} {1+\cfrac{1}{\ddots}}}. $$ 這樣, 極限 $\omega$ 滿足方程 $\omega={1}/{(1+\omega)}$。 由此解出 $$\omega=\frac{\sqrt{5}-1}{2}\approx {0.618}.$$ 之所以稱為黃金分割法, 因為 $\omega$ 乃是歷史上很有名的黃金分割常數。

上述 Kiefer 的開天辟地的論文僅有 4 頁加 4 行, 令人吃驚的是, 這是他的碩士學位論文; 更令人吃驚的是他於 1942 年上大學 MIT, 第 2 年因第二次世界大戰入伍美國空軍, 3 年後 (1946) 回到 MIT, 於 1948 年獲得本科和碩士學位。 這樣, 他真正的本科和碩士總共只讀了 3 年, 所以無法不讓人佩服。 他後來的主要貢獻是在《試驗設計》這門學科前加上了「最優」。 他於 1975 年當選美國科學院院士。

下面, 我們轉到第二類最優試驗策略。 與 Kiefer 的看法不同, 華先生認為黃金分割法 ${{\scr W}}$ 是最優的, 而分數法 ${{\scr F}}_n$ 是其近似, 簡單的理解可用數論中的丟番圖逼近: 如同前面的連分數所示, 分數列 $\{F_n/F_{n+1}\}_{n\ge 1}$ (有理數) 構成 (無理數) $\omega$ 的最佳逼近。 為闡述這一理論結果, 我們先定義來回調試策略 $\pmb{\scr P}$: 它從第 3 步開始, 每一步都在剩餘區間上安排試點。

定理2[華羅庚 (1971, 1981)] 對於每一來回調試策略 ${\scr P}$, 當 $n\gg 1$ 時, 有 $\delta({{\scr P}}, n)\ge \delta({{\scr W}}, n)=\omega^n$。 換言之, 黃金分割法是來回調試策略中在無窮遠處的最優策略。

後來, 洪加威 (1973, 1974) 將此定理中的來回調試策略拓廣為一般策略。

1970 年代, 華先生帶領他的小分隊, 到全國各地推廣優選法, 期間出版了不少優選法的科普著作和應用專集, 下面是我所見到的第一本, 也是影響我一生的一本小冊子。

此書購於 1971 年 6 月 3 日, 全書共 23 頁, 定價 7 分錢, 留心這裏的作者署名「齊念一」(我至今不知其含義), 那時候「華羅庚」的名字不能用! 下面是我所保存的其它幾種版本。

現在, 轉來研究第三種最優試驗策略。 仔細想想, Kiefer 和華先生的最優化策略都是預定了試驗的次數: Kiefer 定在有限 $n$ 步, 而華定在無窮遠處。 為適用於所有試驗次數, 如同取最壞情形以適用於所有單峰函數, 依「極大極小化」原理, 需尋求使 $$\sup_{n\ge 1}\sup_{f\in {{\scr F}}}\big|c_f-c_f({{\scr P}}, n)\big| =\sup_{n\ge 1}\delta ({{\scr P}}, n) $$ 達到最小的試驗策略 ${\scr P}$, 細加琢磨, 這裏有漏洞。 因為對於不同的 $n$, 試驗區間的長度可能相差太遠, 不可同等對待。 這就引導我們以相對誤差代替絕對誤差, 現在, $n$ 步的相對誤差為 $$ \frac{\delta ({{\scr P}}, n)-\delta ({{\scr F}}_n, n)}{\delta ({{\scr F}}_n, n)} =F_{n+1}\delta ({{\scr P}}, n)-1. $$ 因此, 略去常數 $-1$, 可定義 $\delta ({{\scr P}})=\sup_{n\ge 1} F_{n+1}\delta ({{\scr P}}, n)$ 並稱之為 策略 $\pmb{\scr P}$ (在不定次數意義下) 的精度。 留心這裏從 $\delta ({{\scr P}}, n)$ 到 $\delta ({{\scr P}})$, 因為考慮相對誤差而增加了因子 $F_{n+1}$, 這個觀察以後有用。

稱 ${\scr P}$ 為 對稱策略, 如從第 2 步開始, 它在上次試驗的剩餘區間上依對稱規則安排新試點。 之所以限於對稱策略, 是因為在實踐中, 構造複雜的策略用處不大。

定理3[陳 (1977)] 對於每一對稱策略 ${\scr P}$, 有 $\delta({{\scr P}})\ge \delta({{\scr W}})$。 換言之, 黃金分割法是對稱策略中在不定次數意義下的最優策略。

此結果並不過癮, 因為它只是已有方法的新解釋, 並沒有提供新方法。 進一步的結果見本文的末節。

三、MH370

也許, 一開頭看不出搜索失聯飛機與上面所介紹的優選法有何關聯。

這需要一點思考。 大家知道, 飛機上有一個信號源: 黑匣子。 這樣, 找飛機就等於找信號最大的位置。 有一訊息還可以大大簡化我們尋找的精力, 那就是失聯飛機的飛行路線。 上圖的時間點是重要的, 因為黑匣子的電能尚未耗盡, 可惜路線圖比較粗糙。 反之, 下圖 (左邊為北、右邊為南)的路線已經很清晰, 可惜黑匣子已過期。 這樣, 我們就喪失了寶貴的機會。

真是機不可失, 時不再來。 其實, 有了這張圖, 我們的搜索就可以大大簡化, 可將三維的搜索問題簡化為一維：首先, 在這條曲線找到信號最大的位置, 然後垂直向下的海底就應該是我們所要的地方, 而沿曲線搜索問題就可用我們前面所講的優選法。 為說明我們的分析是有道理的, 只需看看九個多月後失聯亞航 QZ8501 的搜索, 它很快被找到, 是因為有一乘客忘了關手機, 發出了微弱信號。

四、每批多個試點的優選法

馬航 MH370 的搜索, 最多的時候有 26 國家參加, 所以是 26 國聯軍, 與前面不同, 每步(批)可安排多個試點(並行算法), 此時最優策略是什麽？ 為討論此問題, 我們先限於以下試驗策略類, 稱 ${\scr P}$ 為 基本策略, 如在第 $j$ 步, 新試點和上次留下來的好點將實驗區間分為長度分別為 $\alpha_j$ 和 $\beta_j$ 兩兩相間的諸段。

固定 $i\!\ge\!1$。 我們先考慮每步(批) $2i$ $(i\!\ge\! 1)$ 個試點情形, 定義兩種策略如下。

• 預定 $n$ 步的基本策略 ${{\scr E}}_n^{(i)}$: $$\alpha_1=\frac{2(i+1)^{n-1}-1}{2(i+1)^{n}-1},\qquad \beta_1=\frac{1}{2(i+1)^{n}-1}. $$
• 不定步數的基本策略 ${{\scr E}}^{(i)}$: 對於每一個 $j,\;$ $\alpha_j=\beta_j$, 即每一步將區間等分。

與前面一樣, 可定義策略 ${\scr P}$ 的 $\pmb n$ 步精度： $\delta({{\scr P}}, n)=\sup_{f\in {{\scr F}}}|c_f-c_f({{\scr P}}, n)|$。 然後可算出 \begin{eqnarray*} &\delta\big({{\scr E}}_n^{(i)}, n\big)&=[2(i+1)^n-1]^{-1}=:{E_n^{(i)}}^{-1}\\ &\delta\big({{\scr E}}^{(i)}, n\big)&=[(2i+1)(i+1)^{n-1}]^{-1}. \end{eqnarray*} 由此可定義每步 $2\, i$ 個試點, 不定步數的精度 $\delta({{\scr P}})=\sup_{n\ge 1} {E_n^{(i)}}\delta({{\scr P}}, n) $。 我們注意, 當 $n\to\infty$ 時, ${{\scr E}}_n^{(i)}$ 退化, 此時不存在無窮遠處的最優策略, 但在我們不定步數意義下, 此問題有 很簡單的解答。

定理4[陳, 1977] 設每步 $2\,i$ 個試點。

• 當 $i\ge 2$ 時, 策略 ${{\scr E}}^{(i)}$ 在不定步數意義下最優。
• 當 $i=1$ 時, 第一步的兩個試點為 $$\alpha_1=\frac 3 7,\qquad \beta_1=\frac 1 7\qquad \mbox{ (非均分)}\hbox{。} $$

最後考慮每步 $2\,i-1\,(i\ge 1)$ 個試點。 此時, 依照定與不定步數兩種情形, 我們分別有廣義分數法與廣義黃金分割法。 先定義 廣義 Fibonacci 數列： $$F_0^{(i)}=F_1^{(i)}=1, \quad F_n^{(i)}=i\big(F_{n-1}^{(i)}+F_{n-2}^{(i)}\big),\quad n\ge 2.$$ 現在可陳述這兩種方法。 為此, 只需寫出相應的 $\alpha_1$ 和 $\beta_1$。 自此以後, 除非確有必要, 我們略去 $F_n^{(i)}$ 的上標 $i$ 不寫。

• $\pmb n$ 步廣義分數法: $\alpha_1={F_n}/{F_{n+1}},\quad \beta_1={F_{n-1}}/{F_{n+1}}$。
• 廣義黃金分割法: $\alpha_1=\omega(i)$, $\beta_1=\omega(i)^2$, 其中 $$\omega(i)=\lim_{n\to\infty} \frac{F_n}{F_{n+1}}=\frac{\sqrt{i(i+4)}-i}{2i}. $$

每步 $2\, i-1$ 個試點, 不定步數的精度定義為 $\delta({{\scr P}})\!=\!\sup_{n\ge 1}\! {F_n^{(i)}}\delta({{\scr P}}, n)$。

定理5[陳與黃, 1995] 設每批 $2i\!-\!1$ 個試點, 則在不定批數意義下基本策略類中的最優者為 $$\alpha_1= \bigg\{\frac 1 i \bigg[\frac{i+1}{2}\bigg]+\chi(i)\omega\bigg\}\omega,\qquad \beta_1=\frac 1 i -\alpha_1, $$ 其中 $[x]$ 為不超過 $x$ 的最大整數, \begin{eqnarray*} \chi(i)=\left\{\begin{array}{l} 0 &\quad \mbox{如 i 為奇數},\\ 1 &\quad \mbox{如 i 為偶數}。 \end{array}\right. \end{eqnarray*}

除非 $i=1$, 這不同於廣義黃金分割法 ${{\scr W}}^{(i)}$。

對於更一般情形, 每批的試驗次數任意給定, 在不定批數意義下的最優策略目前還是一個待解問題。 當然, 在給定批數條件下的解答早就知道了, 例如見 。 這裏, 我們只討論了單因素, 對於多因素情形, 自然有更多的選擇, 有更大的靈活性。 我們順便指正: 如同在其它領域一樣, 在數學上, 也需要有很強的鑑賞能力和批判意識, 例如在多因素情形, 有單純形法 (俗稱翻跟鬥法)及其變形, 如矩形調優法。 但這兩種方法表面上雷同, 但在數學原理上卻有 優劣之分。 詳見[第 83、 84 頁] 或 [第c91--93 頁]。 更多方法可參考 -- 和 。 對於優選法更新一些的進展, 也許可參考 。 本文涉及 MH370 的想法也許將來在處理相關課題時會有點用處。 作者衷心希望《優選學》這門數學分支學科能夠有更大的發展。

從作者的主頁 (http://math0.bnu.edu.cn/\~chenmf) 中可找到更多的科普文章和視頻。

致謝: 本文根據以下 8 次講座整理而成： 江蘇師範大學 (2014/10), 北京師範大學第七屆數學夏令營 (2015/7), 東北師範大學 (2015/8), 吉林大學 (2016/6), 浙江大學 (2016/9), 四川大學 (2016/11), 山東大學(威海) (2016/12) 和臺灣國立中央大學 (2017/4)。 作者衷心感謝 謝穎超、許孝精、史寧中、白誌東、郭建華、陶劍、王德輝、韓月才、李勇、包鋼、呂克寧、彭聯剛、劉建亞、李娟和許順吉等教授的熱情款待和他們單位的資助。 中研院的黃啟瑞、姜祖恕和周雲雄等研究員及弟子也專程赴中央大學參加報告會, 謹致謝忱。 同時感謝國家自然科學基金重點項目 (No.11131003), 教育部 973 項目和江蘇高校優勢學科建設工程項目的資助。 作者非常感謝黃馨霈和王靜雯兩位助理的精心排版, 再次感謝李宣北教授的大力支持和幫助。

參考資料

---本文作者任教中國北京師範大學數學學院---