信賴域方法信賴域方法1信賴域方法信賴域方法是求解最優(yōu)化問題的另一類有效方法．其最初的設(shè)計思想可追溯至Levenberg和Marquart對Gauss－Newton法的修正．線搜索方法是把一個復(fù)雜的最優(yōu)化問題轉(zhuǎn)化成一系列簡單的一維尋優(yōu)問題．信賴域方法是把最優(yōu)化問題轉(zhuǎn)化為一系列相對簡單的局部尋優(yōu)問題．信賴域方法信賴域方法是求解最優(yōu)化問題的另一類有效方法．其最初2基本思想牛頓法的基本思想是在迭代點附近用二次函數(shù)逼近并以的的極小點修正得到：以上方法只能保證算法的局部收斂性，為了建立總體收斂性算法，我們采用了線搜索技術(shù)．雖然這種策略是成功的，但它有一個缺點，即沒有進一步利用二次模型．基本思想牛頓法的基本思想是在迭代點附近用二次函數(shù)逼近并以的的3基本思想牛頓法的基本思想是在迭代點附近用二次函數(shù)逼近并以的的極小點修正得到：以上方法只能保證算法的局部收斂性，為了建立總體收斂性算法，我們采用了線搜索技術(shù)．雖然這種策略是成功的，但它有一個缺點，即沒有進一步利用二次模型．信賴域方法是另一種新的保證算法總體收斂的方法．基本思想牛頓法的基本思想是在迭代點附近用二次函數(shù)逼近并以的的4信賴域方法的模型子問題其中是Hesse陣的近似為信賴域半徑．信賴域方法的模型子問題其中是Hesse陣的近似為信賴域半徑．5注：(1)這種方法既具有牛頓法的快速局部收斂性，又具有理想的總體收斂性．(2)不要求目標函數(shù)的Hesse陣是正定的．(3)利用了二次模型來求修正量，使得目標函數(shù)的下降比線性搜索方法更有效．(4)由于步長受到使Taylor展開式有效的信賴域的限制，故方法又稱為有限步長法．注：(1)這種方法既具有牛頓法的快速局部收斂性，又具有理想的6信賴域半徑的選擇根據(jù)模型函數(shù)對目標函數(shù)的擬合程度來調(diào)整信賴域半徑對于問題(1)的解定義比值：它衡量模型函數(shù)與目標函數(shù)的一致性程度．信賴域半徑的選擇根據(jù)模型函數(shù)對目標函數(shù)的擬合程度來調(diào)整信賴域7注：(1)越接近于１，表明模型函數(shù)與目標函數(shù)的一致性程度越好，可以增大以擴大信賴域．(2)不接近于１，可以保持不變．(3)接近于零或取負值，表明模型函數(shù)與目標函數(shù)的一致性程度不好，可以減小以縮小信賴域．注：(1)越接近于１，表明模型函數(shù)與目標函數(shù)的一致性程度越好8信賴域算法Step1:給出信賴域半徑的上界Step2:如果停止．Step3:求解子問題(1)得到Step4:計算和令：信賴域算法Step1:給出信賴域半徑的上界Step2:如果停9Step5:校正信賴域半徑，令：Step6:產(chǎn)生校正令轉(zhuǎn)Step2注：參數(shù)建議?。篠tep5:校正信賴域半徑，令：Step6:產(chǎn)生校正令轉(zhuǎn)St10信賴域子問題信賴域子問題11折線法基本思想如果令信賴域的半徑在區(qū)間內(nèi)連續(xù)變化，則問題(1)的解在空間中形成一條光滑的連續(xù)曲線，記為此時，問題(1)等價于在信賴域內(nèi)在最優(yōu)曲線上確定一點使二次函數(shù)取極小，即：由于最優(yōu)曲線的確定需要計算矩陣的所有特征值和特征向量，相當(dāng)費時．折線法基本思想如果令信賴域的半徑在區(qū)間內(nèi)連續(xù)變化，則問題(112折線法在于用低維空間內(nèi)滿足一定要求的折線，記為代替最優(yōu)曲線．通過求解：得問題(1)的近似解注：(1)求解(2)的一個突出特點在于：近似折線一經(jīng)確定，對于給定的無需再解任何線性方程組，即能相當(dāng)有效的確定問題(1)的近似解．折線法在于用低維空間內(nèi)滿足一定要求的折線，記為代替最優(yōu)曲線．13(2)構(gòu)造近似最優(yōu)曲線的折線時，一般應(yīng)滿足下面基本要求：當(dāng)點從出發(fā)沿著折線前進時:(P1)點到的距離單調(diào)增；(P2)函數(shù)值嚴格單調(diào)降；性質(zhì)(P1)確保對任意給定的折線上的近似解惟一．性質(zhì)(P2)確保在折線上所確定的近似解能滿足收斂性定理的條件．(2)構(gòu)造近似最優(yōu)曲線的折線時，一般應(yīng)滿足下面基本要求：當(dāng)點14折線法算法原理(1970)連接Cauchy點(由最速下降法產(chǎn)生的極小點C.P.)和牛頓點(即由牛頓法產(chǎn)生的極小點）,其連線與信賴域的邊界的交點取為顯然,當(dāng)牛頓步的長度時，就取為對二次模型：折線法算法原理(1970)連接Cauchy點(由最速下降法產(chǎn)15精確線搜索下Cauchy步為：若取若再計算牛頓步若取否則取其中由方程得到．精確線搜索下Cauchy步為：若取若再計算牛頓步若取否則取其16綜上：綜上：17雙折線法(1979)讓信賴域迭代中產(chǎn)生的點偏向牛頓方向，于是把Cauchy點和牛頓方向上的點連接起來，并將這條連線與信賴域邊界的交點取為折線稱為單折線．把稱為雙折線．雙折線法(1979)讓信賴域迭代中產(chǎn)生的點偏向牛頓方向，于18在雙折線情形下：其中一般取在雙折線情形下：其中一般取19例