第四章無約束優(yōu)化方法-資料下載頁
2025-08-01 13:40本頁面
【正文】 是在前一構(gòu)造 矩陣的基礎(chǔ)上校正得到，令 推廣到一般的 k+1次構(gòu)造矩陣 {Ak}， k=1， 2， …… A1=A0+△ A0 Ak+1=Ak+△ Ak 矩陣序列的 基本迭代式 △ Ak稱為 校正矩陣 擬牛頓條件 設(shè) F（ x）為一般形式 n階的目標(biāo)函數(shù)，并具有連續(xù)的一、二 階偏導(dǎo)。在點(diǎn) 處的二次泰勒近似展開 該近似二次函數(shù)的梯度是 式中， ，若令 ，則有 上式中 是第 k次迭代中前后迭代點(diǎn)的矢 量差，稱他為位移矢量，并為簡(jiǎn)化書寫 而 是前后迭代點(diǎn)的梯度矢量差 由以上三式得 海賽矩陣與 梯度間的關(guān)系式 由上式，用第 k+1次構(gòu)造矩陣 近似代替 ，則 上式通常稱為 擬牛頓條件 或 擬牛頓方程 DFP法構(gòu)造矩陣 的遞推公式（推導(dǎo)過程略） Ak+1=Ak+△ Ak 由上式可以看出，構(gòu)造矩陣 的確定取決于第 k次迭代 中的下列信息： 上次的構(gòu)造矩陣 Ak，迭代點(diǎn)位移矢量 迭代點(diǎn)的梯度增量 ，因此，不必作二階導(dǎo)數(shù)矩陣及其求逆的計(jì)算 對(duì) DFP法幾個(gè)問題的說明與討論 ⑴ DFP公式總有確切的解 ⑵ 構(gòu)造矩陣的正定性 ⑶ DFP法搜索方向的共軛性 ⑷ 關(guān)于算法的穩(wěn)定性 DFP算法的迭代步驟步驟 ⑴ 任取初始點(diǎn) 給出迭代精度 及其模 若 轉(zhuǎn)步驟⑺， 否則進(jìn)行下一步。 ⑵ 置 k←0 ，取 Ak←E ⑶ 計(jì)算迭代方向 沿 方向做一維搜索求優(yōu)化 步長(zhǎng) ，使 確定下一個(gè)迭代點(diǎn) ⑷ 計(jì)算 的梯度 及其模 ，若 則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)下一步 ⑸ 計(jì)算位移矢量 和梯度矢量 按 DFP公式計(jì)算構(gòu)造矩陣 ⑹ 置 k←k+1 。若 kn(n為優(yōu)化問題的維數(shù) )返回步驟⑶， 否則返回步驟⑵ ⑺ 輸出最優(yōu)解（ x*， F*），終止計(jì)算 例題 用 DFP尺度法求目標(biāo)函數(shù) 的最優(yōu)解。已知初始點(diǎn) ，迭代精度 ε= 解： 第一次迭代： 式中最優(yōu)步長(zhǎng)應(yīng)用一維搜索方法在計(jì)算機(jī)上求解。為了 說明問題，又因?yàn)榇死繕?biāo)函數(shù)簡(jiǎn)單，所以用解析法來求： 為求極小，將上式對(duì) α求導(dǎo)，并令 f’(α)=0 得： 于是： 第二次迭代： 確定 點(diǎn)的擬牛頓方向 按 DFP公式計(jì)算構(gòu)造矩陣 將數(shù)據(jù)代入得 則擬牛頓方向?yàn)? 沿 方向進(jìn)行一維搜索求最優(yōu)點(diǎn) 求一維搜索步長(zhǎng) 則： 迭代即可結(jié)束，輸出優(yōu)化解 討論： ① 該題的理論最優(yōu)點(diǎn)是 。按 DFP搜索方向?yàn)? 共軛的性質(zhì)，本題為二元二次函數(shù)在兩次迭代后即達(dá)到最 優(yōu)點(diǎn)，本題計(jì)算結(jié)果少有誤差，這是由于一維搜索的不精 確性產(chǎn)生的。 ② 若在已知 A1的基礎(chǔ)上，再用 DFP公式遞推下一次的構(gòu)造 矩陣，可計(jì)算得 而計(jì)算目標(biāo)函數(shù)海賽矩陣的逆陣有 DFP法的算法流程圖 ?,n,x )0(輸入：）（計(jì)算： ）（）（ 00)0(xFgIA0k????)()()()1()()()()()()()()(m inkkkkkkkkkkkSxxSxFgAS??????????)( )1()1( ?? ?? kk xFgk=n？ )1()1()1()()1()()()()1()()1(?????????????????kkkkkTkTkTTkkkkgASNMAAyAyyANyMggyxx?????)1()0( ?? kxx入口 出口 *)(*]* )1(xFFxx k?? ??)1( ???kg+ + BFGS變尺度法 DFP算法由于舍入誤差和一維搜索的不精確，有可能 導(dǎo)致 Ak奇異，而使數(shù)值穩(wěn)定性方面不夠理想。所以 1970 年提出更穩(wěn)定的算法，稱為 BFGS算法。 其校正公式為 無約束優(yōu)化問題的評(píng)價(jià)準(zhǔn)則 為了比較各種優(yōu)化方法的特性，必須建立合理 的評(píng)價(jià)準(zhǔn)則。 無約束優(yōu)化方法的評(píng)價(jià)準(zhǔn)則主要包括以下幾個(gè)方面： 可靠性 。 即在合理的精度要求下，在一定允許時(shí)間內(nèi)能解出各種不同類型問題的成功率。能夠解出的問題越多，則算法的可靠性越好。 有效性 。 即算法的解題效率。它有兩個(gè)衡量標(biāo)準(zhǔn)。其一是對(duì)同一題目，在相同精度和初始條件下，比較機(jī)時(shí)多少。其二是在相同精度下，計(jì)算同一題目所需要的函數(shù)的計(jì)算次數(shù)。 簡(jiǎn)便性 。 一方面指實(shí)現(xiàn)該算法的準(zhǔn)備工作量的大小。另一方面指算法占用存儲(chǔ)單元的數(shù)量。 下面討論本章所介紹的幾種優(yōu)化方法的適用范圍 ： 可靠性 ：牛頓法較差，因?yàn)樗鼘?duì)目標(biāo)函數(shù)要求太高，解題成功率較低。 有效性 ：坐標(biāo)變換法和梯度法的計(jì)算效率較低，因?yàn)樗鼈儚睦碚撋喜痪哂卸问諗啃浴? 簡(jiǎn)便性 ：牛頓法和變尺度法的程序編制較復(fù)雜，牛頓法還占用較多的存儲(chǔ)單元。 在選用無約束優(yōu)化方法時(shí)，一方面要考慮優(yōu)化方法的特點(diǎn)，另一方面要考慮目標(biāo)函數(shù)的情況。 一般而言，對(duì)于維數(shù)較低或者很難求得導(dǎo)數(shù)的目標(biāo)函數(shù)，使用坐標(biāo)輪換法或鮑威爾法較合適。 對(duì)于二次性較強(qiáng)的目標(biāo)函數(shù)，使用牛頓法效果好。 對(duì)于一階偏導(dǎo)數(shù)易求的目標(biāo)函數(shù)，使用梯度法可使程序編制簡(jiǎn)單，但精度不宜過高。 綜合而言，鮑威爾法和 DFP法具有較好的性能。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1