如何做網(wǎng)站的的關(guān)鍵詞在線bt磁力搜索
?? 本系列文章主要是我在學(xué)習(xí)《數(shù)值優(yōu)化》過程中的一些筆記和相關(guān)思考，主要的學(xué)習(xí)資料是深藍(lán)學(xué)院的課程《機(jī)器人中的數(shù)值優(yōu)化》和高立編著的《數(shù)值最優(yōu)化方法》等，本系列文章篇數(shù)較多，不定期更新，上半部分介紹無約束優(yōu)化，下半部分介紹帶約束的優(yōu)化，中間會(huì)穿插一些路徑規(guī)劃方面的應(yīng)用實(shí)例
?? 九、修正阻尼牛頓法
?? 1、基本牛頓方法
?? （1）基本牛頓方法介紹
?? Newton方法是Newton型方法的基礎(chǔ).本文主要討論基本Newton方法、阻尼Newton方法及修正Newton方法的構(gòu)造與性質(zhì).這類方法適宜于解決中小型最優(yōu)化問題.
?? 設(shè)f(x)具有連續(xù)的二階偏導(dǎo)數(shù),當(dāng)前迭代點(diǎn)是 x k x_k xk?，f(x)在 x k x_k xk?處的Taylor展式為
?? f ( x k + d ) = f k + ? f ( x k ) T d + 1 2 d T ? 2 f ( x k ) d + o ( ∥ d ∥ 2 ) . f(x_k+d)=f_k+\nabla f\left(x_{k}\right)^\mathrm{T}d+\dfrac12d^{\mathrm T}\nabla^2 f(x_k) d+o(\|d\|^2). f(xk?+d)=fk?+?f(xk?)Td+21?dT?2f(xk?)d+o(∥d∥2).
?? 其中 d = x ? x k d= x - x_k d=x?xk? ,在點(diǎn) x k x_k xk?的鄰域內(nèi),用如下二次函數(shù)來近似 f ( x k ＋ d ) f(x_k ＋ d) f(xk?＋d)，求解問題
?? q k ( d ) ? f k + ? f ( x k ) T d + 1 2 d T ? 2 f ( x k ) d q_k(d)\triangleq f_k+ \nabla f\left(x_{k}\right)^\mathrm{T}d+\dfrac12d^{\mathrm T}\nabla^2 f(x_k)d qk?(d)?fk?+?f(xk?)Td+21?dT?2f(xk?)d
?? 上式中的d也就是 x ? x k x-x_k x?xk?,所以上式也可寫為如下的形式：
?? q k ( d ) ? f ( x k ) + ? f ( x k ) T ( x ? x k ) + 1 2 ( x ? x k ) T ? 2 f ( x k ) ( x ? x k ) q_k(d)\triangleq f(\boldsymbol{x}_{k})+\nabla f(\boldsymbol{x}_{k})^{T}(\boldsymbol{x}-\boldsymbol{x}_{k})+{\frac{1}{2}}(\boldsymbol{x}-\boldsymbol{x}_{k})^{T}\nabla^{2}f(\boldsymbol{x}_{k})(\boldsymbol{x}-\boldsymbol{x}_{k}) qk?(d)?f(xk?)+?f(xk?)T(x?xk?)+21?(x?xk?)T?2f(xk?)(x?xk?)
?? 只要上式中的 ? 2 f ( x k ) \nabla^2f(x_k) ?2f(xk?)在 x k x_k xk?處是正定的，就可以對(duì)上式求導(dǎo)，即求梯度等于0的點(diǎn)，得到以下方程組：
?? ? 2 f ( x k ) ( x ? x k ) + ? f ( x k ) = 0 \nabla^2f(\boldsymbol{x}_k)(\boldsymbol{x}-\boldsymbol{x}_k)+\nabla f(\boldsymbol{x}_k)=\boldsymbol{0} ?2f(xk?)(x?xk?)+?f(xk?)=0
?? 即：
?? ? 2 f ( x k ) d = ? ? f ( x k ) \nabla^2 f(x_k) d=-\nabla f\left(x_{k}\right) ?2f(xk?)d=??f(xk?)
?? 若 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)正定,則方程組的解 d k = ? ? 2 f ( x k ) ? 1 ? f ( x k ) d_k=-\nabla^2 f(x_k)^{-1}\nabla f\left(x_{k}\right) dk?=??2f(xk?)?1?f(xk?)為上述問題的唯一解，因?yàn)榛九ｎD法步長(zhǎng)取1，因此其迭代式為： x k + 1 = x k ? [ ? 2 f ( x k ) ] ? 1 ? f ( x k ) \boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-\left[\nabla^{2}\boldsymbol{f}(\boldsymbol{x}_{k})\right]^{-1}\nabla f(\boldsymbol{x}_{k}) xk+1?=xk??[?2f(xk?)]?1?f(xk?)。
–
?? 由上圖可以看出通過不斷迭代，可以很快收斂到局部最優(yōu)解，此外，若目標(biāo)函數(shù) f ( x ) f(x) f(x)本來就是一個(gè)二次函數(shù)，其泰勒展開式 q k ( d ) q_k(d) qk?(d)近似于它自己，此時(shí)，采用牛頓方向，就可以從任何地方經(jīng)過一次迭代就能到達(dá)局部最優(yōu)解。
?? 所以，對(duì)于嚴(yán)格正定的二次函數(shù)，采用牛頓方向（步長(zhǎng)），可以一步收斂到精確解。
?? 我們稱方程組 ? 2 f ( x k ) d = ? ? f ( x k ) \nabla^2 f(x_k) d=-\nabla f\left(x_{k}\right) ?2f(xk?)d=??f(xk?)為Newton方程,由該方程組得到的方向 d p d_p dp?為Newton方向.用Newton方向作為迭代方向的最優(yōu)化方法稱為Newton方法.用Newton方法迭代的意義如下圖所示，其中粗虛線表目標(biāo)函數(shù) f ( x ) f(x) f(x)的等高線,細(xì)虛線表 q k ( d ) q_k(d) qk?(d)的等高線。
?? 再例如下圖中的例子，其中品紅色曲線為 x 0 x_0 x0?處的二次逼近的等值線，棕色曲線為 x 1 x_1 x1?處的二次逼近的等值線
–
?? （2）基本牛頓方法算法流程
?? 基本Newton方法指取全步長(zhǎng) a k = 1 a_k=1 ak?=1的Newton方法, 下面給出基本Newton方法的迭代步驟:
?? 此外，只要 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)正定，Newton方向 d k d_k dk?就是下降方向，只要在 x k x_k xk?（k=0，1，2，3，…）處 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)均正定，迭代就能不停的進(jìn)行下去
?? 附：判斷一個(gè)矩陣是否是正定的方法
??
?? 一個(gè)矩陣是正定的，當(dāng)且僅當(dāng)它是對(duì)稱的（即等于它的轉(zhuǎn)置矩陣）且所有特征值都是正數(shù)。特別地，一個(gè)正定矩陣是一個(gè)非奇異（可逆）矩陣。
??
?? 判斷一個(gè)矩陣是否是正定的方法有多種，以下是其中兩種常用的方法：
??
?? 方法① 判斷所有特征值是否為正數(shù)：設(shè)矩陣 A A A 的特征值為 λ 1 , λ 2 , ? , λ n \lambda_1,\lambda_2,\cdots,\lambda_n λ1?,λ2?,?,λn?，則 A A A 是正定的當(dāng)且僅當(dāng) λ i > 0 \lambda_i>0 λi?>0 對(duì)于所有 i = 1 , 2 , ? , n i=1,2,\cdots,n i=1,2,?,n。
??
?? 方法②判斷所有主子矩陣的行列式是否為正數(shù)：設(shè)矩陣 A A A 的 k k k 階主子矩陣為 A k A_k Ak?，即 A k A_k Ak? 由 A A A 的前 k k k 行和前 k k k 列組成，則 A A A 是正定的當(dāng)且僅當(dāng) A k A_k Ak? 的行列式 det ? ( A k ) > 0 \det(A_k)>0 det(Ak?)>0 對(duì)于所有 k = 1 , 2 , ? , n k=1,2,\cdots,n k=1,2,?,n。
??
?? 需要注意的是，這些方法只適用于實(shí)對(duì)稱矩陣，而對(duì)于復(fù)數(shù)矩陣，需要使用其他定義和方法來判斷是否是正定的。
?? 一個(gè)簡(jiǎn)單的牛頓法例子如下（拖動(dòng)或者雙擊可查看大圖）：
?? 下面給出了其迭代過程，并與采用恒定步長(zhǎng)0.1的梯度下降法進(jìn)行了對(duì)比，從收斂速度來看，牛頓法更優(yōu)，從穩(wěn)定性和占用計(jì)算資源來看，牛頓法不占優(yōu)，如果該凸函數(shù)的Hesse矩陣是嚴(yán)格正定的就可以滿足穩(wěn)定性，如果有高效的求解Hesse矩陣的方法，就可以減少計(jì)算資源的占用。
?? 一般從以下三個(gè)方面評(píng)價(jià)一種數(shù)值優(yōu)化方法：
?? ①、收斂速度：一般認(rèn)為在對(duì)數(shù)精度曲線上隨著迭代次數(shù)的增加，呈直線下降，一般認(rèn)為收斂較快，如果是朝下的二次曲線，則認(rèn)為收斂速度更快，如果是朝上的曲線，則認(rèn)為收斂速度不佳。
?? ②、適用于不同函數(shù)時(shí)的穩(wěn)定性：有的要求是強(qiáng)凸的或者凸的，有的可以適應(yīng)于非凸的函數(shù)，甚至是非光滑的函數(shù)，甚至是不連續(xù)的函數(shù)。
?? ③、每次迭代的計(jì)算量：每次迭代需要計(jì)算多大的計(jì)算量，一般跟維度和約束個(gè)數(shù)有關(guān)，一般可用收斂速度和計(jì)算量（計(jì)算耗時(shí)）的乘積來衡量
?? （3）基本牛頓方法收斂性
?? Newton方法的收斂性依賴于初始點(diǎn)的選擇.當(dāng)初始點(diǎn)接近極小點(diǎn)時(shí),迭代序列收斂于極小點(diǎn),并且收斂很快; 否則就會(huì)出現(xiàn)迭代序列收斂到鞍點(diǎn)或極大點(diǎn)的情形,或者在迭代過程中出現(xiàn)矩陣奇異或病態(tài)的情形,使線性方程組不能求解或不能很好地求解，導(dǎo)致迭代失敗.
?? 由基本Newton方法的收斂性定理可知，只有當(dāng)?shù)c(diǎn)充分接近a*時(shí),基本Newton方法的收斂性才能保證。
?? （4）基本牛頓方法的優(yōu)缺點(diǎn)
?? 優(yōu)點(diǎn):
?? （1）當(dāng) x 0 x_0 x0?充分接近問題的極小點(diǎn)x * 時(shí),方法以二階收斂速度收斂;
?? （2）方法具有二次終止性.
?? 缺點(diǎn):
?? （1）當(dāng) x 0 x_0 x0?沒有充分接近問題的極小點(diǎn)x * 時(shí), ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)會(huì)出現(xiàn)不正定或奇異的情形,使{ x k x_k xk?}不能收斂到x * ,或使迭代無法進(jìn)行; 即使 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)正定也不能保證{ f k f_k fk?}單調(diào)下降。
?? （2）每步迭代需要計(jì)算Hesse矩陣,即計(jì)算n(n ＋1)/2個(gè)二階偏導(dǎo)數(shù).
?? （3）每步迭代需要解一個(gè)線性方程組,計(jì)算量為O( n 3 n^3 n3) 。
?? （4）在很多非凸的函數(shù)中曲率可能不是正向的曲率，即使Hesse矩陣是半正定的也會(huì)出現(xiàn)奇異值是0的情況，不能對(duì)Hesse矩陣求逆也就完成不了一次迭代，因此需要規(guī)避Hesse矩陣奇異或者不定的情況，才能快速收斂。
?? （5）只有當(dāng)Hesse是正定的時(shí)候，它的逆才是正定的，此時(shí)乘以一個(gè)負(fù)梯度方向才能保證牛頓方向與負(fù)梯度方向夾角是小于90度的，若Hesse是不定的，則夾角可能是鈍角，此時(shí)，不能保證牛頓方向是下降方向。即我們要保證牛頓方向與最速下降方向夾角小于90度
?? 2、阻尼牛頓方法
?? 為改善Newton方法的局部收斂性質(zhì),我們可以采用帶一維搜索的Newton方法,即
?? x k + 1 = x k + α k d k x_{k+1}=x_{k}+\alpha_k d_k xk+1?=xk?+αk?dk?
?? 其中 a k a_k ak? 是一維搜索的結(jié)果.該方法稱為阻尼Newton方法.此方法能夠保證對(duì)正定的 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)，{ f k f_k fk?}單調(diào)下降;即使 x k x_k xk?離 x ? x^* x?稍遠(yuǎn),該方法產(chǎn)生的點(diǎn)列{ x k x_k xk?}仍可能收斂至 x ? x^* x?
?? 對(duì)嚴(yán)格凸函數(shù),采用Wolfe 準(zhǔn)則的阻尼Newton方法具有全局收斂性,且采用Wolfe準(zhǔn)則的阻尼Newton方法產(chǎn)生的{ x k x_k xk?}滿足下列二者之一:
?? ① { x k x_k xk?}為有窮點(diǎn)列,即存在N，使得 ? f ( x N ) \nabla f\left(x_{N}\right) ?f(xN?)= 0;
?? ② { x k x_k xk?}為無窮點(diǎn)列, { x k x_k xk?}收斂到 f f f的唯一極小值點(diǎn) x ? x^* x?
?? 此外，采用精確線搜索、Goldstein 準(zhǔn)則等線搜索準(zhǔn)則，阻尼Newton方法對(duì)嚴(yán)格凸函數(shù)的全局收斂性亦存在.
?? 3、修正阻尼牛頓方法（混合方法）
?? Newton方法在迭代的過程中會(huì)出現(xiàn) Hesse矩陣奇異、不正定的情形，Newton方向會(huì)出現(xiàn)與梯度 ? f ( x k ) \nabla f\left(x_{k}\right) ?f(xk?)幾乎正交的情形.為解決這些問題,人們提出了許多修正Newton方法.這些方法或采用與其他方法混合的方式,或采用隱式地、顯式地對(duì)Hesse矩陣進(jìn)行修正的方式對(duì)Newton方法進(jìn)行修正.
?? 籠統(tǒng)來說，修正阻尼牛頓法滿足以下框架，其中M是對(duì)Hessian矩陣的近似，根據(jù)不同的情況，可以選擇不同的近似方法，得到不同的M，多種方法組合在一起也就成了混合方法
–
?? （1）
?? 最簡(jiǎn)單的修正 Newton方法是針對(duì) ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)可逆但不正定情形的.即當(dāng) ? f ( x k ) \nabla f\left(x_{k}\right) ?f(xk?) ? 2 f ? 1 ( x k ) \nabla^2 f^{-1}(x_k) ?2f?1(xk?) ? f ( x k ) \nabla f\left(x_{k}\right) ?f(xk?) <0時(shí),我們可以簡(jiǎn)單地取
?? d k = ? 2 f ? 1 ( x k ) ? f ( x k ) d_k=\nabla^2 f^{-1}(x_k)\nabla f\left(x_{k}\right) dk?=?2f?1(xk?)?f(xk?)
?? 使 d k d_k dk?是下降方向.然而這樣的修正不能處理Newton方法可能遇到的各種情形,如下的混合方法可以處理Newton方法可能遇到的各種情形。
?? （2）一種混合方法
?? 所謂的混合方法就是一種方法與另外一種或多種方法混合使用的方法.混合的方式有多種,混合的目的是取各方法所長(zhǎng),或者是在一種方法無法繼續(xù)迭代下去時(shí),采用另一種方法.使迭代得以繼續(xù)進(jìn)行.下面我們要考慮的方法是Newton方法與負(fù)梯度方法的混合.該方法采用Newton方向,但在 Hesse矩陣 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)奇異或 ? f ( x k ) \nabla f\left(x_{k}\right) ?f(xk?)與 d k d_k dk?幾乎正交時(shí)，采用負(fù)梯度方向;在 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)負(fù)定,但 ? 2 f ? 1 ( x k ) \nabla^2 f^{-1}(x_k) ?2f?1(xk?)存在時(shí),取 d k d_k dk?= ? 2 f ? 1 ( x k ) \nabla^2 f^{-1}(x_k) ?2f?1(xk?) ? f ( x k ) \nabla f\left(x_{k}\right) ?f(xk?).考慮到Newton方法在迭代過程中可能出現(xiàn)的各種情形,我們有如下算法:
?? 該方法的缺點(diǎn)在于,若迭代過程中連續(xù)多步使用負(fù)梯度方向,收斂速度會(huì)趨于負(fù)梯度方法的收斂速度.雖然該方法不是非常有效的方法,然而為了讓迭代進(jìn)行下去,它所采用的混合方式還是有代表意義的。
?? （3）LM方法
?? LM (Levenberg-Marquardt)方法是處理 ? 2 f ( x k ) \nabla^2 f(x_k) ?2f(xk?)奇異、不正定等情形的一個(gè)最簡(jiǎn)單且有效的方法,它是指求解
?? ( ? 2 f ( x k ) + ν k I ) d = ? ? f ( x k ) (\nabla^2 f(x_k)+\nu_kI)d=-\nabla f\left(x_{k}\right) (?2f(xk?)+νk?I)d=??f(xk?)
?? 來確定迭代方向的Newton型方法，這里 v k v_k vk? >0，Ⅰ是單位陣．顯然,若 v k v_k vk?足夠大,可以保證 ? 2 f ( x k ) + ν k I \nabla^2 f(x_k)+\nu_kI ?2f(xk?)+νk?I正定，當(dāng) v k v_k vk?很小時(shí),上述方程的的解偏向于Newton方向,此時(shí)能夠保證正定性，隨著 v k v_k vk?的增大,上述方程的解向負(fù)梯度方向偏移.這種修正Newton方法的思想來自解最小二乘問題的LM方法，在后續(xù)的文章中討論關(guān)于修正 v k v_k vk?的方法.這里當(dāng) ? 2 f ( x k ) + ν k I \nabla^2 f(x_k)+\nu_kI ?2f(xk?)+νk?I不正定時(shí),我們可以簡(jiǎn)單地取 v k v_k vk?=2 v k v_k vk?
?? 當(dāng) ( ? 2 f ( x k ) + ν k I ) (\nabla^2 f(x_k)+\nu_kI) (?2f(xk?)+νk?I)正定時(shí)可以對(duì)其進(jìn)行Cholesky分解，分解成一個(gè)下三角陣乘一個(gè)上三角陣的形式，即 ( ? 2 f ( x k ) + ν k I ) (\nabla^2 f(x_k)+\nu_kI) (?2f(xk?)+νk?I)= L L T LL^T LLT,其中L為下三角陣，通過Cholesky分解可以快速求出以上方程。
?? LM方法比 Newton方法有效,它能夠處理Newton方法所不能處理的情況.
?? （4）
?? 對(duì)于一般的非凸函數(shù)，它的Hessian矩陣是不定的，我們可以將Hessian矩陣進(jìn)行Bunch-Kaufman因式分解，分解成 L B L T LBL^T LBLT，L為下三角陣，B為分塊對(duì)角陣， L T L^T LT為上三角陣。假設(shè)B由1個(gè)1x1的對(duì)角塊，和1個(gè)2x2的對(duì)角塊組成。對(duì)于1x1的塊，要求其為正數(shù)，對(duì)于2x2的塊的兩個(gè)特征值必然為1正1負(fù)，所以在將Hessian矩陣分解成 L B L T LBL^T LBLT后，將其中的B陣的2x2的塊更改為與其最接近的正定陣，即2x2的塊的兩個(gè)特征值均為正，然后再利用修改后的方程求出迭代方向。
?? 參考資料：
?? 1、數(shù)值最優(yōu)化方法（高立 編著）
?? 2、機(jī)器人中的數(shù)值優(yōu)化