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

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