最優(yōu)化理論與方法.ppt

使用導(dǎo)數(shù)的無(wú)約束最優(yōu)化方法 策略表現(xiàn)形式方法線性近似最速下降法二次近似Newton法共軛梯度法用布魯?shù)?Broyden 族或黃 Huang 族擬Newton法修正公式 最速下降法 SteepestMethod 考慮無(wú)約束問題下降算法對(duì)于下降方向的要求 最速下降法的要求 最速下降法 SteepestMethod 最速下降法的計(jì)算步驟 1 給出初始點(diǎn)和精度 2 計(jì)算 如果 則令 停止 否則 轉(zhuǎn) 3 3 令 求解得到 4 令 轉(zhuǎn) 2 最速下降法 SteepestMethod 對(duì)于最速下降法的幾點(diǎn)說(shuō)明 1 鋸齒現(xiàn)象 目標(biāo)函數(shù)在負(fù)梯度方向下降得最快只是局部性質(zhì) 2 改進(jìn)策略 在計(jì)算的開始階段使用最速下降法 在迭代數(shù)次后 改用其他算法 最速下降法 SteepestMethod 二次函數(shù)情形下最速下降法的收斂速度定理考慮無(wú)約束最優(yōu)化問題其中G是n階對(duì)稱正定矩陣 和分別是G的最大特征值和最小特征值 設(shè)是問題的解點(diǎn) 則最速下降法至少具有線性的收斂速度 并且滿足下面的界 最速下降法 SteepestMethod 對(duì)于定理的說(shuō)明 1 在上面定理中 如果考慮的是如下一般二次目標(biāo)函數(shù) 其中G是n階對(duì)稱正定矩陣 則有類似的證明方法證明定理同樣成立 2 當(dāng)目標(biāo)函數(shù)是二階連續(xù)可微的一致凸函數(shù)時(shí) 由上章的推導(dǎo)可知 采用精確線性搜索的最速下降法產(chǎn)生的迭代點(diǎn)列至少是線性收斂的 最速下降法 SteepestMethod 定理 設(shè)最速下降法產(chǎn)生的點(diǎn)列收斂到 在附近二階連續(xù)可微 且 正定 則線性收斂到 即其中M和m滿足 和分別是的最小特征值和最大特征值 Newton法及其改進(jìn) Nowton法的主要內(nèi)容 1 牛頓法的基本思想 2 阻尼牛頓法 3 帶保護(hù)措施的阻尼牛頓法 4 吉爾 默里穩(wěn)定牛頓法 5 信賴域方法 一 Newton法及其改進(jìn) 1 牛頓法的基本思想 在目標(biāo)函數(shù)的極小點(diǎn)的近似點(diǎn)附近將二階Tayler展開 用展開的二次函數(shù)去逼近 將這個(gè)二次函數(shù)的極小點(diǎn)作為的一個(gè)新的近似點(diǎn)依次下去 用一系列二次函數(shù)的極小點(diǎn)去逼近的極小點(diǎn) Newton法及其改進(jìn) 設(shè)二次連續(xù)可微 則在處的二次近似為 令即 Newton法及其改進(jìn) 若正定 對(duì)稱 則存在 Newton迭代公式Newton方向 Newton法及其改進(jìn) 定理 Newton法收斂定理 設(shè)二階連續(xù)可微 是的局部最優(yōu)解 正定 Hesse矩陣滿足Lipschitz條件 即存在 使得對(duì)所有的i j 有其中是Hesse矩陣的元素 則當(dāng)初始點(diǎn)充分靠近時(shí) 對(duì)于一切的k 牛頓迭代公式有定義 并且所得迭代點(diǎn)列收斂到 并且具有二階收斂速度 Newton法及其改進(jìn) 牛頓法面臨的主要困難 1 很難檢驗(yàn)初始點(diǎn)是否靠近最優(yōu)解因而不能保證Hesse矩陣是否正定 得到的方向是下降方向 迭代點(diǎn)列的收斂性及收斂速度 2 牛頓法對(duì)目標(biāo)函數(shù)要求高 二階連續(xù)可微 且需較多的存儲(chǔ)單元 每次迭代均要進(jìn)行矩陣求逆運(yùn)算 3 二次終止性 對(duì)于二次凸函數(shù) 用牛頓法求解 經(jīng)1次迭代即達(dá)極小點(diǎn) Newton法及其改進(jìn) 2 阻尼牛頓法 在標(biāo)準(zhǔn)牛頓法增加了沿牛頓方向的直線搜索 阻尼牛頓法在適當(dāng)?shù)臈l件下具有全局收斂性 且為2級(jí)收斂 Newton法及其改進(jìn) 阻尼牛頓法的缺點(diǎn) 阻尼牛頓法克服了牛頓法要求初始點(diǎn)充分靠近目標(biāo)函數(shù)的極小點(diǎn)的缺點(diǎn) 但只有當(dāng)目標(biāo)函數(shù)的Hesse矩陣處處正定時(shí) 才具有全局收斂性 如果Hesse矩陣不是處處正定 當(dāng)初始點(diǎn)遠(yuǎn)離局部極小點(diǎn)時(shí) Hesse矩陣可能不正定 這時(shí)Hesse矩陣可能奇異也可能是非奇異 若Hesse矩陣奇異 求解方向的方程組可能無(wú)解 或者雖然有解 但求出的方向不能使迭代過程繼續(xù)進(jìn)行下去 若Hesse矩陣非奇異 但不正定 則求得的方向可能不是下降方向 Newton法及其改進(jìn) 例 取 則 顯然 是可逆矩陣 但不正定 其逆矩陣為于是 沿此方向進(jìn)行線性搜索 其極小點(diǎn)為 因此迭代不能繼續(xù)進(jìn)行下去 Newton法及其改進(jìn) 3 帶保護(hù)措施的阻尼牛頓法 Goldstein和Price 1967 假設(shè)可逆 若正定 否則 Newton法及其改進(jìn) 4 吉爾 默里穩(wěn)定牛頓法 Gill和Murray 1974 定義 設(shè)在開集D上二次連續(xù)可微 i 如果Hesse矩陣至少有一個(gè)負(fù)特征值 則叫做不定點(diǎn) ii 如果X是一個(gè)不定點(diǎn) 若方向d滿足則稱d為在X處的負(fù)曲率方向 Newton法及其改進(jìn) 負(fù)曲率方向的性質(zhì) 1 若方向d為負(fù)曲率方向 則也是負(fù)曲率方向 2 在鞍點(diǎn)處 負(fù)曲率方向必是下降方向 3 在一般點(diǎn)處 若負(fù)曲率方向d滿足 則d與均是下降方向 則d是下降方向 則是下降方向 Newton法及其改進(jìn) Gill Murray穩(wěn)定牛頓法的基本思想 當(dāng)Hesse矩陣在迭代點(diǎn)處為不定矩陣時(shí) 對(duì)其進(jìn)行強(qiáng)迫正定的分解 當(dāng)趨于零時(shí) 采用負(fù)曲率方向使函數(shù)值下降 構(gòu)造一個(gè)對(duì)稱正定矩陣在處做下降方向 Newton法及其改進(jìn) 算法 Gill Murray穩(wěn)定牛頓法 1 給定初始點(diǎn) 精度 常數(shù)令 2 計(jì)算梯度和Hesse矩陣 令 3 若 則停止計(jì)算 輸出 4 判斷是否正定 若正定 轉(zhuǎn) 6 否則轉(zhuǎn) 5 5 計(jì)算 轉(zhuǎn) 4 Newton法及其改進(jìn) 算法 Gill Murray穩(wěn)定牛頓法 6 求解求出搜索方向 7 直線搜索 且令 8 令 轉(zhuǎn) 2 Newton法及其改進(jìn) 定理 設(shè)二階連續(xù)可微 且存在 使得為有界閉凸集 假定在吉爾 默里穩(wěn)定牛頓法中取 且初始點(diǎn) 則吉爾 默里穩(wěn)定牛頓法產(chǎn)生的迭代序列滿足 i 當(dāng)為有窮點(diǎn)列時(shí) 其最后一個(gè)元素必為的穩(wěn)定點(diǎn) ii 當(dāng)為無(wú)窮點(diǎn)列時(shí) 它必有聚點(diǎn) 且它的所有聚點(diǎn)都是的平穩(wěn)點(diǎn) 共軛方向法 概述 共軛方向法是介于最速下降法與牛頓法之間的一類方法 它僅需利用一階導(dǎo)數(shù)信息 但克服了最速下降法收斂慢的缺點(diǎn) 又避免了存儲(chǔ)和計(jì)算牛頓法所需要的二階導(dǎo)數(shù)信息 因而簡(jiǎn)便 易實(shí)現(xiàn) 且十分適合大規(guī)模 稀疏 優(yōu)化問題的計(jì)算 通常只經(jīng)過較少的迭代次數(shù)就能獲得滿足所要求精度的近似解 共軛方向法是從研究二次函數(shù)的極小化產(chǎn)生的 但是它可以推廣到處理非二次函數(shù)的極小化問題 最典型的共軛方向法就是本節(jié)研究的共軛梯度法 下一節(jié)介紹的擬牛頓法也是共軛方向法 共軛方向法 概述 例 設(shè) 其中A為正定矩陣 能否從任意初始點(diǎn)出發(fā) 經(jīng)過至多兩步迭代達(dá)到其極限點(diǎn) 最優(yōu)解 定義 共軛方向 設(shè)A為n階對(duì)稱正定矩陣 是n維非零向量 如果 則稱向量和是關(guān)于A共軛的 類似地 設(shè)是m個(gè)n維向量 如果 則稱是關(guān)于A共軛的向量組 共軛方向法 概述 定理 設(shè)A為n階對(duì)稱正定矩陣 則關(guān)于A共軛的非零向量是線性無(wú)關(guān)的 定理 共軛方向法基本定理 設(shè)二次函數(shù)的極小化問題為 其中A是n階對(duì)稱正定矩陣 是任意一組關(guān)于A共軛的非零向量 若從任意初始點(diǎn)出發(fā) 依次沿方向進(jìn)行精確線性搜索 則至多經(jīng)過n次迭代就可達(dá)到問題的最優(yōu)解 共軛梯度法 定理 設(shè)向量線性無(wú)關(guān) 則由這組向量可以構(gòu)造m個(gè)關(guān)于A共軛的向量 共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合 利用已知點(diǎn)處的梯度構(gòu)成一組共軛方向 并沿這組方向進(jìn)行搜索 求出目標(biāo)函數(shù)的最小點(diǎn) 根據(jù)共軛方向的基本性質(zhì) 這種方法具有二次終止性 共軛梯度法 二次函數(shù) 考慮其中A為對(duì)稱正定矩陣 給定初始點(diǎn) 計(jì)算若 則 停止計(jì)算 否則 令 若已知點(diǎn)和搜索方向 則其中使用精確線性搜索得到 共軛梯度法 二次函數(shù) 此時(shí) 令則有對(duì)于二次函數(shù) 有即解得 共軛梯度法 二次函數(shù) 計(jì)算在處的梯度若 則停止計(jì)算 否則 用和構(gòu)造 設(shè)要求與關(guān)于A共軛 解得再?gòu)某霭l(fā) 沿方向搜索 共軛梯度法 二次函數(shù) 共軛梯度法的迭代公式為 對(duì)于二次函數(shù)有 共軛梯度法 二次函數(shù) FR 1964 共軛梯度法 二次函數(shù) 定理 設(shè)目標(biāo)函數(shù)為正定二次函數(shù)則采用精確線性搜索的共軛梯度法經(jīng)步終止 且對(duì)所有成立下列關(guān)系式 共軛梯度法 二次函數(shù) FR 1964 PRP 1969 CW 1972 Dixon 1972 共軛梯度法 二次函數(shù) 例3 30 用共軛梯度法求解取初始點(diǎn)為 共軛梯度法 二次函數(shù) 共軛梯度法的計(jì)算步驟 1 給定初始值 令 2 計(jì)算 若 則 停止計(jì)算 否則 轉(zhuǎn) 3 3 計(jì)算共軛系數(shù) 共軛梯度法 二次函數(shù) 共軛梯度法的計(jì)算步驟 4 構(gòu)造搜索方向 5 計(jì)算令 6 令 轉(zhuǎn) 2 共軛梯度法 非二次函數(shù) 1 步長(zhǎng)不能用顯式格式計(jì)算 必須用其他直線搜索方法來(lái)確定 2 矩陣A不再是常數(shù)矩陣 需要用現(xiàn)行點(diǎn)處的Hesse矩陣 改進(jìn)思路 將共軛梯度法應(yīng)用于非二次函數(shù)的極小化時(shí) 每迭代n次就周期地選取負(fù)梯度方向作為搜索方向 所以這種算法稱作重新開始的共軛梯度法 即令 共軛梯度法 非二次函數(shù) 鮑威爾 對(duì)非二次函數(shù) 在計(jì)算中可能出現(xiàn)與幾乎正交的情況 此時(shí)FR PRP 共軛梯度法 二次函數(shù) 共軛梯度法的計(jì)算步驟 1 給定初始值 令 2 計(jì)算 若 則 停止計(jì)算 否則 轉(zhuǎn) 3 3 計(jì)算共軛系數(shù) 共軛梯度法 二次函數(shù) 共軛梯度法的計(jì)算步驟 4 構(gòu)造搜索方向 5 做直線搜索計(jì)算令 6 若 則 停止計(jì)算 否則 令 轉(zhuǎn) 2 共軛梯度法 非二次函數(shù) 重新開始的共軛梯度法允許采用近似線性搜索過程 只是在采用近似線性搜索時(shí) 要采取一定的檢查措施 以保證所得到的搜索方向是下降方向 但是 如果頻繁地利用負(fù)梯度方向作為搜索方向 將大大降低共軛梯度法的效率 而使算法的性態(tài)變得更象最速下降法 采取檢查措施可以克服這個(gè)困難 擬牛頓法 最速下降法具有結(jié)構(gòu)簡(jiǎn)單 計(jì)算量小的優(yōu)點(diǎn) 但其收斂速度較慢 共軛梯度類算法具有計(jì)算存儲(chǔ)量小的優(yōu)點(diǎn) 一般使用于大規(guī)模優(yōu)化問題 而牛頓法及各種改進(jìn)的牛頓法具有收斂速度快的優(yōu)點(diǎn) 但要求在迭代過程中每次構(gòu)造搜索方向時(shí) 首先要計(jì)算目標(biāo)函數(shù)的Hesse矩陣 然后需要求解一個(gè)線性方程組 從而計(jì)算量大 存儲(chǔ)量也大 而且有的目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算 甚至不好求出 這就抵消了牛頓法收斂速度快的優(yōu)點(diǎn) 這類算法只適用于中小規(guī)模的優(yōu)化問題 擬牛頓法 擬牛頓算法只需利用目標(biāo)函數(shù)及其一階導(dǎo)數(shù)的信息 構(gòu)造對(duì)稱正定的矩陣來(lái)近似牛頓法中的Hesse矩陣或者其逆矩陣 產(chǎn)生較好的近似牛頓方向 避免了Hesse矩陣的計(jì)算 減少了計(jì)算量 并且具有超線性收斂的優(yōu)點(diǎn) 該法被認(rèn)為是無(wú)約束優(yōu)化 中小規(guī)模 問題中最有效的算法 擬牛頓法 設(shè)二次連續(xù)可微 則在處的二次近似為 則即擬牛頓法的基本迭代格式 擬牛頓法 記則若Hesse矩陣可逆 則擬牛頓條件或擬牛頓方程 擬牛頓法 二次近似滿足性質(zhì) 擬牛頓法 擬牛頓算法的一般框架與牛頓法相比 擬牛頓法還要求以下幾點(diǎn) 1 或 是對(duì)稱正定矩陣 從而是下降方向 使得方法具有下降性質(zhì) 2 或稱 或 為校正矩陣 上兩個(gè)方程為校正條件 擬牛頓法 擬牛頓算法框架 1 給出初始值 令 2 計(jì)算 如果 則令 停止迭代 否則 計(jì)算 3 沿方向d作線性搜索求 令 4 計(jì)算校正產(chǎn)生使得擬牛頓條件成立的 令 返回 2 擬牛頓法 秩1校正解得 設(shè)則有即從而 擬牛頓法 這時(shí) 稱為秩1校正公式 為了保證矩陣的對(duì)稱性 若取稱為對(duì)稱秩1校正公式 擬牛頓法 若取稱為布魯?shù)?Broyden 秩1校正公式 擬牛頓法 對(duì)稱秩2校正公式 第3 2 5節(jié)信賴域方法 信賴域方法的基本思想 首先選取一個(gè)信賴域半徑 并由此定義的一個(gè)鄰域使得n維二次模型是目標(biāo)函數(shù)的一個(gè)合適的模擬 然后求解具有信賴域約束的子問題 第3 2 5節(jié)信賴域方法 實(shí)際下降量 預(yù)測(cè)下降量 衡量二次模型近似目標(biāo)函數(shù)的指標(biāo) 第3 2 5節(jié)信賴域方法 1 給定初始點(diǎn) 初始步長(zhǎng) 精度 閾值 滿足放大系數(shù)令 2 計(jì)算 如果 則 停止 否則 形成矩陣 3 求解子問題 求出 第3 2 5節(jié)信賴域方法 4 計(jì)算和的值 如果 那么 如果和 那么 否則 令 5 如果 那么