?? 本系列文章主要是我在學(xué)習(xí)《數(shù)值優(yōu)化》過(guò)程中的一些筆記和相關(guān)思考，主要的學(xué)習(xí)資料是深藍(lán)學(xué)院的課程《機(jī)器人中的數(shù)值優(yōu)化》和高立編著的《數(shù)值最優(yōu)化方法》等，本系列文章篇數(shù)較多，不定期更新，上半部分介紹無(wú)約束優(yōu)化，下半部分介紹帶約束的優(yōu)化，中間會(huì)穿插一些路徑規(guī)劃方面的應(yīng)用實(shí)例

?? 七、信賴域方法

?? 1、信賴域方法簡(jiǎn)介

?? 信賴域方法（Trust Region Methods）是一種用于非線性優(yōu)化的數(shù)值優(yōu)化方法，旨在尋找目標(biāo)函數(shù)的最小值。信賴域算法是一種迭代算法，即從給定的初始解出發(fā)，通過(guò)逐步迭代，不斷改進(jìn)，直到獲得滿意的近似最優(yōu)解為止。其基本思想是把最優(yōu)化問(wèn)題轉(zhuǎn)化為一系列簡(jiǎn)單的局部尋優(yōu)問(wèn)題。

?? 它的核心思想是在當(dāng)前點(diǎn)的局部模型和真實(shí)模型之間建立一個(gè)可信區(qū)域（Trust Region），并在可信區(qū)域內(nèi)尋找更優(yōu)的解。

?? 該方法在解決非線性優(yōu)化問(wèn)題時(shí)，常使用局部二次模型來(lái)近似目標(biāo)函數(shù)，并在每個(gè)迭代步驟中解決這個(gè)二次模型的最小化問(wèn)題。信賴域方法是求解非線性最優(yōu)化問(wèn)題的有效方法之一，廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)、機(jī)器學(xué)習(xí)、優(yōu)化控制等領(lǐng)域。

?? 2、信賴域方法基本思想

?? 信賴域方法的基本思想是將問(wèn)題分解為多個(gè)步驟。首先，用一個(gè)二次模型來(lái)近似目標(biāo)函數(shù)，這個(gè)模型只在一個(gè)局部域內(nèi)是準(zhǔn)確的。其次，在這個(gè)局部域內(nèi)求解二次模型的最小值。最后，使用這個(gè)最小值來(lái)更新優(yōu)化變量，然后檢查更新后的函數(shù)值是否小于當(dāng)前的函數(shù)值。如果是，則擴(kuò)大局部域的半徑，否則縮小局部域的半徑，以此控制每個(gè)步驟的更新大小。

?? 那么為什么要構(gòu)建局部模型，而不使用真實(shí)模型呢？

?? 假設(shè)在點(diǎn)$x_k$處，我們欲求下降方向$d_x$，若直接求解極小值問(wèn)題$minf(x_k+d)$去得到$d_k$，那么這個(gè)問(wèn)題與原問(wèn)題復(fù)雜程度相同，而關(guān)于方向d的問(wèn)題應(yīng)該是相對(duì)簡(jiǎn)單、易求的。所以，解決這個(gè)問(wèn)題簡(jiǎn)單可行的方法是:利用Taylor展式,在點(diǎn)$x_k$的鄰域中,使用 $f(x_k+d)$的一階近似函數(shù)或二階近似函數(shù)作為局部模型代替$f(x_k+d)$去求$d_k$ 。（常使用二階近似函數(shù)）,我們記這個(gè)局部模型函數(shù)為$q_k(d)$．求取局部模型$q_k(d)$的極小點(diǎn)，并將其作為迭代方向$d_k$ ,即求

?? $$\underset{d}{\min }{q}_k(d)$$

?? $q_k(d)$近似$f(x_k+d)$的好壞,是受到$x_k$處鄰域大小的影響的.合適的鄰域和合適的近似函數(shù)的選取,可以保證$q_k(d)$是$f(x_k+d)$的一個(gè)好的近似函數(shù)，如取

?? $$q_k(d)=f_k+?f_k^{T}d+\frac{1}{2}{d}^T{?}^2{f}_{k}d$$

?? 當(dāng)||d||較小時(shí)，$q_k(d)$近似$f(x_k+d)$的誤差亦?。?如果$x_k$處的鄰域太大,就無(wú)法保證$q_k(d)$是$f(x_k+d)$的好的近似函數(shù)，此時(shí)可能會(huì)出現(xiàn)$q_k(d)$的極小點(diǎn)與目標(biāo)函數(shù)$f(x_k+d)$的極小點(diǎn)相差甚遠(yuǎn)的情況. 而鄰域的大小決定了步長(zhǎng)的長(zhǎng)短，太短的步長(zhǎng)會(huì)增加算法的迭代次數(shù)，影響算法的收斂速度，所以領(lǐng)域也不能取得過(guò)小。

?? 因此,每步迭代在$x_k$處選擇一個(gè)合適的鄰域，在這個(gè)鄰域中求解${\min }_d{q}_k(d)$，這就是信賴域方法的思想.這個(gè)鄰域,我們稱之為信賴域,即在此信賴域中,我們相信$q_k(d)$是$f(x_k+d)$的好的近似函數(shù).

?? 假定在第k步迭代已得$x_k$以及信賴域的半徑${\Delta }_k$，則信賴域的子問(wèn)題即為求解如下表達(dá)式，得到$d_k$

?? $$\begin{array}{l}\min q_k(d),\\ \text{s.t.}\Vert d\Vert ?{\Delta }_k,{\Delta }_k>0\end{array}$$

?? 在得到新的迭代點(diǎn)$x_{k+1}=x_k+d_k$之后,我們可以判斷${\Delta }_k$是否是下一步迭代的合適的信賴域半徑,若不合適,可以修正${\Delta }_k$得下一步迭代的${\Delta }_{k+1}$，上式中的范數(shù)可依方法而定。

?? 那么如何衡量${\Delta }_k$是否是下一步迭代的合適的信賴域半徑呢？

?? 應(yīng)該根據(jù)$x_k$處$q_k(d)$近似$f(x_k+d)$的好壞來(lái)確定，具體來(lái)說(shuō)，可以根據(jù)從$x_k$到$x_k+d_k$，$f(x)$的實(shí)際減少量$\Delta f_k$與近似函數(shù)$q_k(d)$的減少量$\Delta q_k$之比${\gamma }_k$來(lái)衡量，其中$q_k(0)=f(x_k)$

?? $$\begin{array}{l}\Delta f_k=f(x_k)?f(x_k+d_k)\\ \\ \Delta q_k=q_k(0)?q_k(d_k)\\ \\ {\gamma }_k=\frac{\Delta f_k}{\Delta q_k}\end{array}$$

?? ${\gamma }_k$接近1時(shí),表明$q_k(d)$近似$f(x_k+d)$的程度好，下一步迭代應(yīng)增大${\Delta }_k$;當(dāng) ${\gamma }_k$為接近于零的正數(shù)時(shí),表明$q_k(d)$近似$f(x_k+d)$的程度不好,下一步迭代應(yīng)減小${\Delta }_k$;當(dāng)${\gamma }_k$為零或負(fù)數(shù)時(shí)，說(shuō)明$f(x_k+d_k)\ge f(x_k)$ ，$x_k+d_k$不應(yīng)被接受為下一步的迭代點(diǎn)，這時(shí)只應(yīng)縮小信賴域的半徑 ${\gamma }_k$:,并重新求解。

?? 3、信賴域方法的具體步驟

?? （1）初始化：選擇一個(gè)初始點(diǎn)$x_0$，設(shè)定信賴域的初始大小${\Delta }_0$，初始化迭代次數(shù)k=0。

?? （2）開(kāi)始迭代：判斷是否滿足終止條件（例如目標(biāo)函數(shù)的值達(dá)到了一定的精度），若滿足則輸出$x_k$，迭代停止

?? （3）構(gòu)建局部模型：在當(dāng)前點(diǎn)$x_k$處，構(gòu)建一個(gè)局部二次模型，

?? $$q_k(d)=f_k+?f_k^{T}d+\frac{1}{2}{d}^T{?}^2{f}_{k}d$$

?? 其中，$f_k$是目標(biāo)函數(shù)在$x_k$處的函數(shù)值，$?f_k$是目標(biāo)函數(shù)在$x_k$處的梯度，${?}^2{f}_k$是目標(biāo)函數(shù)在$x_k$處的Hessian矩陣的近似值。

?? （4）尋找下降方向：求解$q_k(d)$的最小值$d_k$，滿足$|d_k|\le {\Delta }_k$，其中${\Delta }_k$是當(dāng)前信賴域的半徑。

?? （5）計(jì)算實(shí)際下降量和預(yù)測(cè)下降量：計(jì)算從$x_k$到$x_k+d_k$，$f(x)$的實(shí)際減少量$\Delta f_k$與近似函數(shù)$q_k(d)$的減少量$\Delta q_k$之比${\gamma }_k$

?? （6）更新信賴域大?。焊鶕?jù)比值${\gamma }_k$的大小更新信賴域大小

?? 如果${\gamma }_k$一定程度上接近于1（比如說(shuō)${\gamma }_k$>0.75）說(shuō)明局部模型對(duì)目標(biāo)函數(shù)有較好的擬合效果，可以增加信賴域的大小 ${\Delta }_{k+1}=\min ({\gamma }_2{\Delta }_k,{\Delta }_{\max })$，其中${\gamma }_2>1$是一個(gè)大于1的常數(shù)，${\Delta }_{\max }$是信賴域大小的上限。

?? 如果${\gamma }_k$一定程度上接近于0（比如說(shuō)${\gamma }_k$<0.25）說(shuō)明局部模型對(duì)目標(biāo)函數(shù)的擬合效果較差，應(yīng)該減少信賴域的大小${\Delta }_{k+1}={\gamma }_1{\Delta }_k$，其中$0<{\gamma }_1<1$是一個(gè)小于1的常數(shù)。

?? 如果${\gamma }_k$位于0~1之間，既不靠近0也不靠近1（比如說(shuō)0.25<${\gamma }_k$<0.75）說(shuō)明局部模型對(duì)目標(biāo)函數(shù)的擬合效果既不好也不壞，可以保持信賴域不變${\Delta }_{k+1}={\Delta }_k$。

?? （7）判斷是否接受新的點(diǎn)$x_{k+1}=x_k+d_k$。

?? 如果${\gamma }_k$<=0，說(shuō)明$f(x_k+d_k)\ge f(x_k)$ ，$x_k+d_k$不應(yīng)被接受為下一步的迭代點(diǎn)，取$x_{k+1}=x_k$，轉(zhuǎn)到第（2）步繼續(xù)迭代，重新求取第k次迭代的解。

?? 如果${\gamma }_k$>0，說(shuō)明$f(x_k+d_k)<f(x_k)$ ，$x_k+d_k$可以被接受為下一步的迭代點(diǎn)，取$x_{k+1}=x_k+d_k$，并將迭代數(shù)加1，即k=k+1，轉(zhuǎn)到第（2）步繼續(xù)迭代。

?? 4、總結(jié)

?? 與線搜索方法先在$x_k$點(diǎn)求得下降方向$d_k$,再沿 $d_k$方向確定步長(zhǎng)$a_k$不同，信賴域方法是先限定步長(zhǎng)的范圍,再同時(shí)確定下降方向$d_k$和步長(zhǎng)$a_k$。

?? 信賴域方法相對(duì)于其他優(yōu)化算法的優(yōu)點(diǎn)在于它可以保證每次迭代都可以得到一個(gè)可行解，并且可以保證在可信區(qū)域內(nèi)尋找更優(yōu)的解，從而增加算法的穩(wěn)定性和可靠性。此外，信賴域方法也可以靈活地處理約束條件和不等式約束問(wèn)題。

?? 然而，信賴域方法也存在一些缺點(diǎn)。例如，它可能會(huì)陷入局部最優(yōu)解，并且每次迭代需要計(jì)算Hessian矩陣或其近似，計(jì)算成本較高。同時(shí)，信賴域大小的選取也需要一定的經(jīng)驗(yàn)和調(diào)試。

?? 總的來(lái)說(shuō)，信賴域方法是一種有效的非線性優(yōu)化算法，可以用于解決一類較為復(fù)雜的優(yōu)化問(wèn)題。

?? 參考資料：

?? 1、機(jī)器人中的數(shù)值優(yōu)化

?? 2、信賴域算法

?? 3、數(shù)值最優(yōu)化方法（高立 編著）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-696532.html

到了這里，關(guān)于機(jī)器人中的數(shù)值優(yōu)化（五）——信賴域方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！