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

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

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

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

5、在這個框架中遇到的最常見的一些困難：（1）如果起始點和最終的答案（全局方法）不是近似值該如何解決以及如何用區域變量來有效的聯合（局部方法）這個問題；（2）以及如果沒得出解析導數應該如何處理；（3）如果問題函數的求值用精確的算法將會是高效的（算法往往不精確）。我們研究的基本方法以及提供的基本算法思路是當前解決這些問題的最好方法。我們也給出了自認為是理解這些方法和，擴展或改進這些問題的相關分析。尤其是，我們試圖辨別并強調這些在這個領域已經演變為中心的理念和方法。我們認為這個領域已經到達了一個可識別技術的點,這個點很可能還可改進,但不大可能如量子跳躍般超越目前最好的算法。解決非線性方程和無約束最小化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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