置信域優(yōu)化（TR, Trust Region Optimization）

應(yīng)用背景

信賴域算法TR可以用來求解非線性規(guī)劃問題（NLP, NonLinear Programing），比如含二次項(xiàng)問題的優(yōu)化求解。

方法原理

函數(shù)f在x_k處的泰勒展開式為:

f(x_k + p)=f(x_k) + \nabla f(x_k)^ Tp + \frac {1}{2} p^T \nabla^2 f(x_k)p + o(p^2)

其中，向量p為迭代向量。在TR算法中，將函數(shù)f隨著p在置信域R中的行為使用二次型表示：

m_k(p) \approx f(x_k)+G(x_k)^Tp+\frac{1}{2}p^TB(x_k)p

式中G為Jacobian矩陣，B為Hessian矩陣?？梢允褂糜邢薏罘只驍M牛頓法來對(duì)Hessian矩陣進(jìn)行近似。這樣，我們的優(yōu)化目標(biāo)為在置信域R中尋找迭代向量p使得m_k取得極小值：

\begin{align*}& {\rm min} \space m_k(p) = f(x_k) + G(x_k)^Tp+\frac{1}{2}p^TB(x_k)p \\& s.t. \|p\| \leq h_k\end{align*}

式中h_k是第k次迭代的信賴域上界（或稱為信賴域半徑）。

接下來我們需要確定置信域邊界，我們可以分別計(jì)算出此步迭代下的實(shí)際優(yōu)化量和使用m_k近似計(jì)算出的優(yōu)化量：

\begin{align}& \Delta f(x_k) = f(x_k) - f(x_k + p) \\& \Delta m_k = f(x_k) - m(p)\end{align}

定義實(shí)際優(yōu)化量和預(yù)測(cè)優(yōu)化量的比值：

r_k = \frac{\Delta f(x_k)}{\Delta m_k}

r_k可以用于衡量二次模型與目標(biāo)函數(shù)的近似程度，顯然r_k值越接近1越好；

* 當(dāng)r_k \leq 0.25?，說明步子邁得太大了，應(yīng)縮小信賴域半徑，h_{k+1} = \frac{\|p_k\|}{4}；

* 當(dāng)r_k > 0.75且\|p_k\| = h_k，說明這一步已經(jīng)邁到了信賴域半徑的邊緣，并且步子有點(diǎn)小，可以嘗試擴(kuò)大信賴域半徑，h_{k + 1} = 2h_k；

* 當(dāng)0.25 < r_k < 0.75，說明這一步邁出去之后，處于“可信賴”和“不可信賴”之間，可以維持當(dāng)前的信賴域半徑，h_{k+1} = h_k；

* 當(dāng)r_k < 0，說明函數(shù)值是向著上升而非下降的趨勢(shì)變化了（與最優(yōu)化的目標(biāo)相反），這說明這一步邁得錯(cuò)得“離譜”了，這時(shí)不應(yīng)該走到下一點(diǎn)，而應(yīng)“原地踏步”，即x_{k+1} = x_k，并且和上述0.25 < r_k < 0.75的情況一樣，縮小信賴域。反之，在r_k > 0的情況下，都可以走到下一點(diǎn)，即x_{k+1} = x_k + p；

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容