無約束最優(yōu)化與非線性方程的數(shù)值方法

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

2、本中以計算機為依托 的算法，這些特點是讀者必須要了解的。1.1考慮的問題這本書討論了實踐中經(jīng)常遇到的三大非線性問題的實際變量。 這些是 合理假設下建立的數(shù)學等價，但我們不打算用相同的算法來處理， 而 打算展示當前最佳的算法是如何找出每個問題的結構。聯(lián)立非線性方程問題（現(xiàn)在簡稱“非線性方程”）是三大非線性方程問題中最基礎的，并且計算中可利用的結構最少。公式如下：已知Given F:才* find x. g R* for which F（x.） = 0 w FT*（LL1）在公式中表示n維歐氏空間。當然，（1.1.1）只是表示含未知數(shù)“n”的n非線性方程的標準公式，方程式的右邊通常是零。例如：如果

3、已知門耳）7且S i山xia（x）2（1.1.1）公式中計算出來的J必然會是廠的最小值。門表示F的第i個組成函數(shù)。這是無約束極小化問題的特殊例子。Given f: R *find jc. e R for which /（xj for every x g R （l丄2）（1.1.2）是我們要考慮的第二個問題。通常（1.1.2）是min f: Rn * 喘.的縮寫。例如：min /（xn x3） = （x - 3）2 + x2 + 5）4 + （x3 - 8）2,X X可以得出丄* _ X *在一些應用中，有人對解決（1.1.3 ）受限版本有興趣，其中Q 是一個封閉連通域。如果（1.1.4 ）的解

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

5、是無約束極小化的一個特殊例子， 但是 由于它的重要性以及它特殊的結構， 其本身就構成一個研究領域。這 就是非線性最小二乘問題：Given R : R勵王略IHfinde R* for which 力（幾（*護 is minimized* （LL5）21川劉表示丘的第i個組成函數(shù)。（1.1.5 ）在曲線擬合中是最常見 的，除此之外當線性系統(tǒng)的線性需求比自由度多時它也會出現(xiàn)。當非線性函數(shù)卜、；、X至少有一個、兩個或者分別有兩個連續(xù) 不同數(shù)時，我們只考慮最常見的例子。要是函數(shù)是充分平滑的，我們 不一定要用假設，導數(shù)就可通過分析得出。對于今天正在解決的非線 性問題的典型規(guī)模以及其它特點的進一步闡釋，可

6、看1.2節(jié)。在非線性問題的數(shù)值解的典型的場景中，計算者須提供評估函數(shù) 的一個子程序，并且起始點5是的大概近似值。如果可行，計算 者還需提供第一個導數(shù)，或許還有第二個導數(shù)。我們這本書的重點是 解決在這個框架中遇到的最常見的一些困難：（1）如果起始點5和最終的答案U （全局方法）不是近似值該如何解決以及如何用區(qū)域 變量來有效的聯(lián)合（局部方法）這個問題；（2）以及如果沒得出解 析導數(shù)應該如何處理；（3）如果問題函數(shù)的求值用精確的算法將會 是高效的（算法往往不精確）。我們研究的基本方法以及提供的基本算法思路是當前解決這些問題的最好方法。 我們也給出了自認為是理解這些方法和，擴展或改進這些問題的相關分析

7、。尤其是，我們試圖 辨別并強調這些在這個領域已經(jīng)演變?yōu)橹行牡睦砟詈头椒āＮ覀冋J為這個領域已經(jīng)到達了一個可識別技術的點，這個點很可能還可改進， 但不大可能如量子跳躍般超越目前最好的算法。解決非線性方程和無約束最小化的問題的方法很相似。這本書大部分是關于這兩個問題的。非線性最小二乘問題只是無約束極小化的 一個特例,但可以利用非線性最小二乘問題的特殊結構調整無約束極 小化技術獲取更好的算法。因此第十章用一個廣泛可行的例子說明了 如何應用和擴展前部分的內容。在這本書中，我們沒有解決的問題是找出一個非線性函數(shù)的極小點，這個變量是在出現(xiàn)許多個不同的局部極小值的情況下的絕 對最低點。(1.1.2 )的解答是

8、，上 是開放區(qū)域的連接。這是一個 非常難的問題，并無廣泛的研究也不像我們已解決的問題那樣容易。 涉及此問題的兩個論文集分別是DlXCn an1 “心門(1975,1978). 通觀全書我們會使用到“全局 ”、“全局法”或者“全局收斂法”這些詞語來表示一種算法，這種算法是專門設計用來匯集非線性函數(shù) 的全局極小點、或者是任何一個非線性方程組的起始點的一些解法。 把這些算法叫做“局部”或者“局部收斂”是比較合適的，但在另一 個算法上這些說明已經(jīng)被傳統(tǒng)保留了，對于一般算法來說確保從每個 起始點收斂的方法或許是低效的(選自Allgower and Georg (1980)。 1.2 “真實世界”問題的特

9、征在這節(jié)中我們提供一些關于實踐中遇到的非線性問題。首先我們列舉了三個真正的非線性問題的例子和一些參與設置數(shù)值問題的 思考。然后我們對大小、費用和其他非線性問題中遇到的一般特征作 出了評價。討論樣品問題的困難之一是在這一領域的背景和代數(shù)描述的問 題很少是簡單的。雖然這使得咨詢工作很有趣，但對于介紹性數(shù)值分 析的書是沒有什么幫助的。因此，我們盡可能簡化我們的示例。最簡單的非線性問題只包含一個變量。例如，科學家可能希望確 定分子構型化合物。研究者得出一個公式 f(x)，把可能配置的勢能 看作函數(shù)的切線x與兩個組件之間的角度。然后，因為自然會導致分 子承擔最小勢能的配置，所以需要找到f(x)的最小值X

10、。這是一個單 變量X的最小化問題。它可能是高度非線性的，由于X可以取任何值， 所以物理函數(shù)真的是無約束。如果問題中只有一個變量，那么就可以用第二章的方法輕易解 決。然而我們已經(jīng)得知相關的問題是一個介于 20到100個變量的函數(shù)。 雖然它們一個個不難解決，但每個F的值在5美元到100美元之間，因 此它們合在一起是難以解決的。第二類常見的非線性問題是曲線族中一些最符合實驗數(shù)據(jù)或人口統(tǒng)計數(shù)據(jù)的曲線選擇的種類。舉出1.2.1的例題：20個太陽光譜曲 線數(shù)據(jù)通過衛(wèi)星提供了波長ti，基本理論暗示任一數(shù)據(jù)m如(ri, y)，(t 丐y m)都符合鐘形的曲線。然而如數(shù)據(jù)顯示，在實踐中這點有實驗上的錯誤。為了從

11、數(shù)據(jù)中得出結論，我們想要無限接近鐘形曲線的m點。因此大致鐘形的等式為v（xu x2, x3, x4? 0 =+ x2etX32/x這意味著所選的x1, x2, x3, x4 要將數(shù)據(jù)點與曲線之間的誤差最小化，因此用以下公式Mx）全只小，衍，乂3，X4 Mi）-兒最常用的方法是求r的平方和，得出鐘形曲線的解決方案是用非線性最小二乘法：min/U) = yfj(x)2 = yUi + 盤廠依切 一 力J心f=li=l這里是注解。第一點，1.2.1的問題是一個非線性最小二乘法問題，余下的函數(shù)r，x是非線性函數(shù)的變量xi, X2, x 3, x 4。實際上ri在X和X2是線性 的，我們可以用前面提到的

12、方法利用這一優(yōu)勢（詳見第10章）。第二點，有一些函數(shù)以外的平方和可以用來測量鐘形函數(shù)數(shù)據(jù)點 間的距離。圖121符合鐘形函數(shù)的數(shù)據(jù)點有兩個明顯的公式:辦(x)= f 皿)1! 因為后者計算靠x和y的關系,但前者不是(見練習6)。在量度誤差 和算法討論時需規(guī)定相同符號。a i，B i , i=1,2,3，寫作a i=0(Bi)。如果存在一常數(shù)c,例如所有的正整數(shù)i,除了一些有限的 子集a i 1(見 練習7)。例如，在CDC上，當我們討論計算機數(shù)字，數(shù)量和 macheps 是非常有用的。例如,我們可以很容易地表明，相對誤差在計算機表示 任何非零實數(shù)x的fl(x)小于macheps相反，任何計算機表示實數(shù)x將 在如下范圍內(x(l - macheps)x(l + macheps) 。同理，以下例子非比匚 1 IX)的整數(shù)幕，這樣你的算法可以像卜保持計算,使你知道程序最后的運行答案。輸出這個值和十進制值。(注意:macheps的價值將取決于2個不同的因素舍入或刪除