1、無約束最優(yōu)化與非線性方程的數(shù)值方法J.E. Dennis, Jr. & Robert B. Schnabel介紹這本書討論了三大非線性問題計算的方法、運算法則和思路分析：非線性方程組的解法、非線性函數(shù)的無約束極小化方法和非線性最小二乘參數(shù)選擇。1.1節(jié)介紹了這些問題和我們對此提出的假設(shè)。1.2節(jié)列舉了一些非線性難題并且論述了在實際運算中遇到的這類問題的典型特征；對這類問題很熟悉的讀者可能會想跳過這個章節(jié)。1.3節(jié)總結(jié)了計算機有限精度算術(shù)的特點。為了理解文本中以計算機為依托的算法，這些特點是讀者必須要了解的。1.1 考慮的問題這本書討論了實踐中經(jīng)常遇到的三大非線性問題的實際變量。這些是合

2、理假設(shè)下建立的數(shù)學(xué)等價，但我們不打算用相同的算法來處理，而打算展示當(dāng)前最佳的算法是如何找出每個問題的結(jié)構(gòu)。聯(lián)立非線性方程問題（現(xiàn)在簡稱“非線性方程”）是三大非線性方程問題中最基礎(chǔ)的，并且計算中可利用的結(jié)構(gòu)最少。公式如下：已知在公式中 表示n維歐氏空間。當(dāng)然，(1.1.1)只是表示含未知數(shù)“n”的n非線性方程的標(biāo)準(zhǔn)公式，方程式的右邊通常是零。例如：如果已知且(1.1.1) 公式中計算出來的必然會是的最小值。表示F的第i個組成函數(shù)。這是無約束極小化問題的特殊例子。 （1.1.2）是我們要考慮的第二個問題。通常（1.1.2）是的縮寫。例如： 可以得出在一些應(yīng)用中，有人對解決（1.1.3）受限版本有興

3、趣，其中是一個封閉連通域。如果（1.1.4）的解法來自的內(nèi)部，那么（1.1.4） 仍可以看作是一個無約束極小化問題。然而，如果是的邊界點，的極小化超過成為一個約束極小化問題。我們不考慮約束問題，因為目前已知的該如何去解決這個問題的知識還較少，而且其間有很多無約束問題需要我們考慮。此外，解決無約束問題的技巧是解決約束算法的基礎(chǔ)。事實上，許多解決約束問題的嘗試不是發(fā)現(xiàn)相關(guān)的無約束最小化問題的答案很接近約束問題的答案，就是發(fā)現(xiàn)非線性方程組的聯(lián)立解都等于。最終，我們在實踐中遇到的絕大多數(shù)的問題不是無約束問題就是最簡單的約束問題例如每個都必須非負數(shù)。 我們考慮的第三個問題也是無約束極小化的一個特殊例子，

4、但是由于它的重要性以及它特殊的結(jié)構(gòu)，其本身就構(gòu)成一個研究領(lǐng)域。這就是非線性最小二乘問題： 表示的第i個組成函數(shù)。（1.1.5）在曲線擬合中是最常見的，除此之外當(dāng)線性系統(tǒng)的線性需求比自由度多時它也會出現(xiàn)。當(dāng)非線性函數(shù)、至少有一個、兩個或者分別有兩個連續(xù)不同數(shù)時，我們只考慮最常見的例子。要是函數(shù)是充分平滑的，我們不一定要用假設(shè)，導(dǎo)數(shù)就可通過分析得出。對于今天正在解決的非線性問題的典型規(guī)模以及其它特點的進一步闡釋，可看1.2節(jié)。在非線性問題的數(shù)值解的典型的場景中，計算者須提供評估函數(shù)的一個子程序，并且起始點是的大概近似值。如果可行，計算者還需提供第一個導(dǎo)數(shù)，或許還有第二個導(dǎo)數(shù)。我們這本書的重點是解決

5、在這個框架中遇到的最常見的一些困難：（1）如果起始點和最終的答案（全局方法）不是近似值該如何解決以及如何用區(qū)域變量來有效的聯(lián)合（局部方法）這個問題；（2）以及如果沒得出解析導(dǎo)數(shù)應(yīng)該如何處理；（3）如果問題函數(shù)的求值用精確的算法將會是高效的（算法往往不精確）。我們研究的基本方法以及提供的基本算法思路是當(dāng)前解決這些問題的最好方法。我們也給出了自認為是理解這些方法和，擴展或改進這些問題的相關(guān)分析。尤其是，我們試圖辨別并強調(diào)這些在這個領(lǐng)域已經(jīng)演變?yōu)橹行牡睦砟詈头椒āＮ覀冋J為這個領(lǐng)域已經(jīng)到達了一個可識別技術(shù)的點,這個點很可能還可改進,但不大可能如量子跳躍般超越目前最好的算法。解決非線性方程和無約束最小化

6、的問題的方法很相似。這本書大部分是關(guān)于這兩個問題的。非線性最小二乘問題只是無約束極小化的一個特例,但可以利用非線性最小二乘問題的特殊結(jié)構(gòu)調(diào)整無約束極小化技術(shù)獲取更好的算法。因此第十章用一個廣泛可行的例子說明了如何應(yīng)用和擴展前部分的內(nèi)容。在這本書中,我們沒有解決的問題是找出一個非線性函數(shù)的極小點，這個變量是在出現(xiàn)許多個不同的局部極小值的情況下的絕對最低點。（1.1.2）的解答是，是開放區(qū)域的連接。這是一個非常難的問題,并無廣泛的研究也不像我們已解決的問題那樣容易。涉及此問題的兩個論文集分別是(1975,1978).通觀全書我們會使用到“全局 ”、“全局法” 或者“全局收斂法”這些詞語來表示一種算

7、法，這種算法是專門設(shè)計用來匯集非線性函數(shù)的全局極小點、或者是任何一個非線性方程組的起始點的一些解法。把這些算法叫做“局部”或者“局部收斂”是比較合適的，但在另一個算法上這些說明已經(jīng)被傳統(tǒng)保留了，對于一般算法來說確保從每個起始點收斂的方法或許是低效的（選自Allgower and Georg (1980)）。1.2 “真實世界”問題的特征在這節(jié)中我們提供一些關(guān)于實踐中遇到的非線性問題。首先我們列舉了三個真正的非線性問題的例子和一些參與設(shè)置數(shù)值問題的思考。然后我們對大小、費用和其他非線性問題中遇到的一般特征作出了評價。討論樣品問題的困難之一是在這一領(lǐng)域的背景和代數(shù)描述的問題很少是簡單的。雖然這使得

8、咨詢工作很有趣,但對于介紹性數(shù)值分析的書是沒有什么幫助的。因此,我們盡可能簡化我們的示例。最簡單的非線性問題只包含一個變量。例如,科學(xué)家可能希望確定分子構(gòu)型化合物。研究者得出一個公式f(x)，把可能配置的勢能看作函數(shù)的切線x與兩個組件之間的角度。然后,因為自然會導(dǎo)致分子承擔(dān)最小勢能的配置,所以需要找到f(x)的最小值x。這是一個單變量x的最小化問題。它可能是高度非線性的, 由于x可以取任何值，所以物理函數(shù)真的是無約束。如果問題中只有一個變量，那么就可以用第二章的方法輕易解決。然而我們已經(jīng)得知相關(guān)的問題是一個介于20到100個變量的函數(shù)。雖然它們一個個不難解決，但每個F的值在5美元到100美元之

9、間，因此它們合在一起是難以解決的。第二類常見的非線性問題是曲線族中一些最符合實驗數(shù)據(jù)或人口統(tǒng)計數(shù)據(jù)的曲線選擇的種類。舉出1.2.1的例題：20個太陽光譜曲線數(shù)據(jù)通過衛(wèi)星提供了波長ti，基本理論暗示任一數(shù)據(jù)m如(ri, yi), ., (tm, ym)都符合鐘形的曲線。然而如數(shù)據(jù)顯示,在實踐中這點有實驗上的錯誤。為了從數(shù)據(jù)中得出結(jié)論，我們想要無限接近鐘形曲線的m點。因此大致鐘形的等式為 這意味著所選的x1, x2, x3, x4要將數(shù)據(jù)點與曲線之間的誤差最小化，因此用以下公式最常用的方法是求r的平方和，得出鐘形曲線的解決方案是用非線性最小二乘法：這里是注解。第一點，1.2.1的問題是一個非線性最

10、小二乘法問題，余下的函數(shù)r，x是非線性函數(shù)的變量x1, x2, x3, x4。實際上ri在X1和X2是線性的，我們可以用前面提到的方法利用這一優(yōu)勢（詳見第10章）。 第二點，有一些函數(shù)以外的平方和可以用來測量鐘形函數(shù)數(shù)據(jù)點間的距離。圖1.2.1符合鐘形函數(shù)的數(shù)據(jù)點有兩個明顯的公式： 通常選擇f (x)而不是f1 (x) 或f0(x)，有時候是因為統(tǒng)計的問題，有時候是因為簡化的結(jié)果很難處理。因為最小二乘法函數(shù)是不斷可微分的，但是其它兩個卻不是。在練習(xí)中大多數(shù)數(shù)據(jù)擬合問題都是用最小二乘法解決的。通常是通過余數(shù)進一位，但這對我們的討論不重要。最后一個例子，我們在研究核聚變反應(yīng)堆的過程中遇到了一個問題

11、。核聚變反應(yīng)堆可以在內(nèi)部加入高溫等離子體塑造成圓環(huán)狀。（詳見圖1.2.2）問題可以簡化成：我們要找到內(nèi)圓半徑r、圓環(huán)的寬w和等離子體的溫度t就可以得出每單元能源的最低成本。科學(xué)家得出以下公式計算每單元能源的最低成本：cl、c2, 、c3、c4是常數(shù)。因此非線性問題可以簡化為一個r、w、t的函數(shù)。然而關(guān)于這個問題還有其它重要的方面。第一，不像之前例子最后的那個變量，r、w和t不能隨便賦值。比如說r和w不能是負數(shù)。圖1.2.2 核聚變反應(yīng)堆因此這是一個不能輕視的問題。這三個變量總共有5個將影響到解決方案的限制。當(dāng)約束影響到解決方案時，問題就不能同樣當(dāng)成函數(shù)解決。在核反應(yīng)堆問題上這些限制很重要。因此

12、要用技術(shù)強制解決。然而很多簡單的約束問題，如對變量的界限都可以無約束地解決。因為限制滿足不受限制的最低要求。注意，我們在核反應(yīng)堆中提到的限制通常會起很大作用。這是因為實際上由于cl、c2, 、c3和c4的常數(shù)值不同，我們要解決625個問題。這些常數(shù)的值取決于因素，如電力成本。這將是恒定的反應(yīng)器的運行，但不知到何時。它運行的問題得視不同的情況而定。但是當(dāng)核反應(yīng)堆在運行時，電力成本也在不斷變化。因此有必要不斷改變條件以尋找反應(yīng)堆最佳的特征。通常在實踐中，需要解決在不同情況下的特定問題，這使算法的效率更為重要。這也使我們用不同的算法去評估這些因素特定的級別。最后，這條等式（1.2.2）只是簡單粗略地

13、反映核聚變反應(yīng)堆。在下一小節(jié)的學(xué)習(xí)中，函數(shù)給出的每單元能源消耗并不十分準(zhǔn)確，就像（1.2.2）。因為它是一個用偏微分方程算出的結(jié)果。這里有5個參量（見圖1.2.3）。這類函數(shù)的精確度在非線性問題中很有限，并且它對運算法則的改進有很大作用。第一，這類函數(shù)只是在某些很小的區(qū)域內(nèi)較為準(zhǔn)確，因此解決問題時過多要求準(zhǔn)確性是沒有意義的。第二，這類函數(shù)可能在大多時候是不斷地可以被微分的，通常無法得到它的導(dǎo)數(shù)。這就是為什么導(dǎo)數(shù)的近似值變得如此重要了。最后求值可能就會很困難，需要進一步估算。以上問題給出了一些典型的非線性問題典型的特征的指示。首先是它們的規(guī)模。雖然實際變量比討論的變量多，但大多數(shù)我們看到的變量相

14、對較少，有2到30個。圖1.23以核聚變反應(yīng)堆的函數(shù)估算我們希望能解決大部分的小問題。比如215個的變量。但是其實2個變量就已經(jīng)很復(fù)雜了。現(xiàn)在的運算法則已經(jīng)可以解決有1550個變量的中等難度的問題了。但是多余50個變量的問題確實是難題，除非它們只是簡單的非線性問題或者有人猜想我們不可能將它們簡便地解決。這些大小的估計是非常不穩(wěn)定的，它們較少依賴于算法、更多依賴于快速存儲的實用性和計算環(huán)境的其他方面。第二個問題是，導(dǎo)函數(shù)的可用性。我們經(jīng)常處理的非線性函數(shù)本身是計算機模擬的結(jié)果，或是由一個冗長又繁瑣的代數(shù)公式得來的。因此通常情況下導(dǎo)函數(shù)是不可求的，盡管函數(shù)是可以不斷被微分的。因此在缺乏可分析的導(dǎo)函

15、數(shù)的情況下有一個有效率的運算法則是很重要的。事實上如果計算機子程序庫包括導(dǎo)函數(shù)，用戶也幾乎不會分析它。誰能怪它們呢？ 第三，如上所述，許多非線性問題是很難解決，要么是因為非線性函數(shù)反復(fù)進行，要么是要解決的任務(wù)牽扯到太多問題了。我們都聽說過一個有50個變量的石油工程，其一個功能的每次評估就要花費IBM3033,100小時。算法運行時間和函數(shù)和導(dǎo)函數(shù)的估算效率是發(fā)展非線性算法的一個重要問題。第四，在很多應(yīng)用中，用戶希望答案中只有少數(shù)精確的數(shù)字。這首先是由于其它問題的近似性質(zhì)：函數(shù)，其它模型參數(shù)，數(shù)據(jù)。另一方面用戶通常要求更精確。盡管希望更精確是合乎情理的，但是也要合理地接受會有集合的存在，因為提供

16、的精確度很少能接近電腦的精確度。第五，沒有考慮到縮放比例。這意味著變量的大小不同，結(jié)果也會有很大不同。比如說一個一個變量可能總是在106107之間，而另一個變量在110之間。 在我們的經(jīng)驗中，這種情況經(jīng)常發(fā)生。然而這一領(lǐng)域的大多數(shù)工作一直沒有注意到縮放比例的問題。在這本書中我們嘗試指出忽略縮放比例會降低非線性算法的性能。我們試圖糾正算法中的不足。最后，在這本書中我們只討論這些非線性問題。其中的未知數(shù)是可以有真正的值的，相反那些變量必須是整數(shù)。一般說來，這是一個現(xiàn)實的限制。答案是非線性問題中肯定有些變量必須是整數(shù),因為他們代表等人、卡車或大型工具。然而,這種限制使得問題更加難以解決由于連續(xù)性缺失

17、我們通常通過將離散變量取整來解決這些問題。這一理論并不能保證這種方法能夠解決整數(shù)問題,但實際上它通常能在特殊情況下得出合理的答案。一些離散變量約束只能是數(shù)值0、1或2。在這種情況下,必須使用離散方法（例如Beale(1977), Garfinkel和Nemhauser(1972)。)1.3有限精度算法和測量誤差計算機程序法有一些特點,收斂性的判斷取決于精確實數(shù)在電腦上的表示。有時,算術(shù)編碼也受對計算機運算理解的影響。因此,我們需要簡述有限精度算法,這是真正的電腦版本算術(shù)（更多信息請參考Wilkinson(1963)）。在科學(xué)記數(shù)法中，數(shù)字51.75被寫作+ 0.5175 *10+2寫的。電腦用

18、同樣的方式代表實數(shù),在我們的例子中使用一個標(biāo)志(+),一個基數(shù)(10),一個指數(shù)(+ 2),和一個尾數(shù)(0.5175)，使之具有惟一的代表。通過指定/基地<尾數(shù)<1,第一個數(shù)字的右邊“十進制”點是零。尾數(shù)的長度,稱為表示的精度,這對數(shù)值計算是特別重要的。實數(shù)的表示在電腦上被稱為浮點表示,fl(x)是x的浮點表示。在CDC機器上基數(shù)是2,尾數(shù)有48位。因為2481014.4這意味著我們可以準(zhǔn)確儲存14個小數(shù)位數(shù)。指數(shù)的范圍可以從-976到+ 1070,這樣最小和最大數(shù)字是大約10-294和10322。在IBM機器基數(shù)是16,尾數(shù)單精度6位雙精度14位,分別對應(yīng)于約7和16個小數(shù)位數(shù)。

19、指數(shù)的范圍可以從-64到+ 63,這樣的最小和最大數(shù)字是大約10-77和1076。只有一個有限的精度對存儲實數(shù)非常重要,但他們能被簡單地概括出來。第一,因為并不是每個實數(shù)可以在電腦上準(zhǔn)確顯示,最好可以得到符合計算機精度的準(zhǔn)確答案。其次,根據(jù)計算機和編譯器,每個由機器計算的中間算術(shù)運算的結(jié)果是被刪減或四舍五入的數(shù)據(jù)。因此,由于有限精度的不準(zhǔn)確，可能積累并進一步降低結(jié)果的準(zhǔn)確性。這些錯誤被稱為舍入錯誤。雖然舍入的影響可能相當(dāng)微妙,只是仍然存在三個基本的情況，可以過度影響計算精度。首先是添加一個數(shù)字序列,特別是在數(shù)字絕對值減少；由于中間結(jié)果的表示是有限的，右邊的部分較小的數(shù)據(jù)容易丟失 (例如，練習(xí)4

20、）。第二個是采用兩個幾乎相同的不同數(shù)字；因為左邊主要數(shù)字差異為零而精度丟失 (例如,練習(xí)5) 。第三是近奇異系統(tǒng)的線性方程組的解,這個在第三章討論。這種情況實際上是前兩個的結(jié)果,但它是如此基本和重要,我們更愿意把它看作第三個基本問題。如果一個人在書面作業(yè)或者電腦程序上意識到這三種情況,可以理解和避免許多與有限精度算法有關(guān)的問題。由于有限精度算法的使用,甚至是算法的迭代性,我們不能得到大多數(shù)非線性問題的準(zhǔn)確答案。因此我們經(jīng)常得求出x和y的關(guān)系。我們通常采用的解題思路是取相對誤差在一個非零的x、y作為近似數(shù), 這是可取的,除非x = 0時,使用絕對誤差, 因為后者計算靠x和y的關(guān)系,但前者不是(見

21、練習(xí)6)。在量度誤差和算法討論時需規(guī)定相同符號。i，i，i=1,2,3，寫作i=0（i）。如果存在一常數(shù)c，例如所有的正整數(shù)i,除了一些有限的子集ic*i。這個不等式表明每個i小于或等于它所對應(yīng)的i。（詳見Aho, Hopcroft, and Ullman 1974.）有限精度算法的另一個效應(yīng)是,某些方面的算法,如停止標(biāo)準(zhǔn),將取決于機器的精度。因此,為了描述機器精度的方式介紹討論和計算機程序可以合理地獨立于任何特定的機器.常用的概念“machine epsilon”,縮略為macheps；被定義為最小的正數(shù)t,由此1 + t > 1(見練習(xí)7)。例如，在CDC上，當(dāng)我們討論計算機數(shù)字，數(shù)

22、量和macheps是非常有用的。例如,我們可以很容易地表明,相對誤差在計算機表示任何非零實數(shù)x的fl(x)小于macheps。相反,任何計算機表示實數(shù)x將在如下范圍內(nèi)(x(l - macheps)x(l + macheps)。同理,以下例子非常常見。解決view macheps的關(guān)鍵是根據(jù)題意判斷x的有限精度。我們習(xí)慣于首先將x賦值為0. 在有限精度下，0代表包含0的范圍區(qū)間(1 macheps)*x,（1 + macheps）*x)。在計算的過程中，有限精度數(shù)字(x + y)=(x)。有時,在數(shù)值線性代數(shù)算法上,將y=0代入計算是有效的。最后,任何計算機用戶應(yīng)該知道,溢出和下溢的發(fā)生條件是在機器中計算生成一個非零的數(shù),指數(shù)分別大于或小于0。例如,當(dāng)我們在CDC上的值為10322會出現(xiàn)下溢,在IBM上的值為10-77會上溢。在溢出的情況下,幾乎所有的機器將終止運行并顯示錯誤。下溢的情況下,往往是一個編譯器選項終止,或者代替零的表達。有時后者的選擇是合理的,但也不一定(見練習(xí)8)。幸運的是,當(dāng)一個人使用編寫良好的線性代數(shù)的例程, 算法中通常不容易溢出或下溢。3.1節(jié)中討論的例子，需要細心計算歐幾里得范數(shù)的向量, 1.4