第四章無(wú)約束優(yōu)化方法(參考版)
2025-08-04 13:40本頁(yè)面
【正文】 綜合而言，鮑威爾法和 DFP法具有較好的性能。 對(duì)于二次性較強(qiáng)的目標(biāo)函數(shù)，使用牛頓法效果好。 在選用無(wú)約束優(yōu)化方法時(shí)，一方面要考慮優(yōu)化方法的特點(diǎn)，另一方面要考慮目標(biāo)函數(shù)的情況。 有效性 ：坐標(biāo)變換法和梯度法的計(jì)算效率較低，因?yàn)樗鼈儚睦碚撋喜痪哂卸问諗啃?。另一方面指算法占用存?chǔ)單元的數(shù)量。 簡(jiǎn)便性 。其一是對(duì)同一題目，在相同精度和初始條件下，比較機(jī)時(shí)多少。 即算法的解題效率。能夠解出的問(wèn)題越多，則算法的可靠性越好。 無(wú)約束優(yōu)化方法的評(píng)價(jià)準(zhǔn)則主要包括以下幾個(gè)方面： 可靠性 。所以 1970 年提出更穩(wěn)定的算法，稱為 BFGS算法。按 DFP搜索方向?yàn)? 共軛的性質(zhì)，本題為二元二次函數(shù)在兩次迭代后即達(dá)到最 優(yōu)點(diǎn)，本題計(jì)算結(jié)果少有誤差，這是由于一維搜索的不精 確性產(chǎn)生的。已知初始點(diǎn) ，迭代精度 ε= 解： 第一次迭代： 式中最優(yōu)步長(zhǎng)應(yīng)用一維搜索方法在計(jì)算機(jī)上求解。 ⑵ 置 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 。而后的矩陣均是在前一構(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)。 變尺度法的搜索方向 S(k)= Ak gk ， 稱為擬牛頓方向。 式中的 Ak為構(gòu)造的 n? n階對(duì)稱矩陣，它是隨迭代點(diǎn)的位置的變化而變化的。 牛頓法的搜索方向?yàn)? Hk1 g(k) ，不僅需要計(jì)算一 階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣，計(jì)算量 很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu) 點(diǎn)時(shí)，收斂速度很快。 一、變尺度法的基本思想 變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。 計(jì)算復(fù)雜且計(jì)算量大，存儲(chǔ)量大 DFP變尺度法 變尺度法也稱 擬牛頓法 ，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。初始點(diǎn) ， 解 ：函數(shù)的梯度 和海賽矩陣及其逆 在 點(diǎn)處 沿 方向移位搜索求得最優(yōu)步長(zhǎng) 故新迭代點(diǎn)為 該點(diǎn)的梯度 迭代即可結(jié)束 由于目標(biāo)函數(shù)是二次正定函數(shù)， 故迭代一次即達(dá)到最優(yōu)點(diǎn) 三、阻尼牛頓法的特點(diǎn) 優(yōu)點(diǎn) ： 由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對(duì)初始點(diǎn)的選擇沒(méi)有苛刻的要求。 阻尼牛頓法 對(duì)原始牛頓法的改進(jìn) 為解決原始牛頓法的不足，加入搜索步長(zhǎng) ?(k) 因此， 迭代公式變?yōu)椋? x (k+1) = x (k) ?(k) Hk1gk 這就是阻尼牛頓法的迭代公式，最優(yōu)步長(zhǎng) ?(k)也稱為阻尼因子，是沿牛頓方向一維搜索得到的最優(yōu)步長(zhǎng)。 其優(yōu)點(diǎn)是 ：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。 F(x) ?1(x) ?0(x) x0 x1 x2 x* 二、原始牛頓法的迭代公式 設(shè)目標(biāo)函數(shù) F(x)具有連續(xù)的一、二階導(dǎo)數(shù)，在 x(k)點(diǎn)鄰域內(nèi)取 F(x)的二次泰勒多項(xiàng)式作近似式，即 取逼近函數(shù) ?(x)為 設(shè) x(k+1)為 ?(x)極小點(diǎn)，根據(jù)極值的必要條件，應(yīng)有 ??(x(k+1))=0，即 ??(x)= gk+ Hk?x=0 又 ?x= x (k+1) x (k) 得 x (k+1) = x (k) Hk1gk 即牛頓法迭代公式，方向 Hk1gk稱為牛頓方向 三、原始牛頓法的特點(diǎn) 若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。 原始牛頓法 一、原始牛頓法的基本思想 在第 k次迭代的迭代點(diǎn) x(k)鄰域內(nèi)，用一個(gè)二次函數(shù)去近似代替原目標(biāo)函數(shù) F(x)，然后求出該二次函數(shù)的極小點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依次類推，通過(guò)多次重復(fù)迭代，使迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)。 牛頓法可以分為 原始牛頓法 和 阻尼牛頓法 兩種。但是對(duì)于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過(guò) n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開(kāi)始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。 （ 6）構(gòu)造新的共軛方向 Sk+1 = ? f(xk+1) + ?kSk 令 k=k+1，轉(zhuǎn)（ 3） 四、共軛梯度法流程圖 入口 k=0， 計(jì)算 ： ? f(x0) || ? f(xk+1) ||? ? ？ 出口 求 ?(k) ， x(k+1)= x(k) +?(k)S(k) 計(jì)算 ： ? f(xk+1) x*=xk+1 f(x*)=f(xk+1) Y N 給定： x(0)， ? k? n ？ x0=xk+1 N Y Sk+1 = ? f(xk+1) + ?kSk K=K+1 五、共軛梯度法的特點(diǎn) 共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡(jiǎn)單，所需存儲(chǔ)量少。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1