數值最佳化（4）——非線性共軛梯度法，信賴域法

上一節筆記：

————————————————————————————————————

大家好！抱歉讓大家久等啦！

在這一節我們會繼續介紹非線性共軛梯度法的內容，並且開始對於信賴域演算法展開介紹。信賴域演算法算是線搜尋方法的一個拓展，也是一種解最佳化問題的框架，之後的很多具體的最佳化演算法都會在信賴域的框架下去實現。

那麼我們開始吧。

線性共軛梯度法的具體實現

非線性共軛梯度法

預條件方法

信賴域方法

柯西點

柯西點的全域性收斂性

Source

J。 Nocedal， S。 J。 Wright，

Numerical Optimization

廈門大學課堂筆記，教授主頁：

https：//www。

math。fsu。edu/~whuang2/i

ndex。html

Y。 H。 Dai and Y。 Yuan。

A nonlinear conjugate gradient method with a strong global convergence property。

Arthur I。 Cohen。

Rate of convergence of several conjugate gradient algorithms。

線性共軛梯度法的具體實現

我們在上一節介紹了線性共軛梯度法可以帶來的幾個性質，我們放在這裡再給大家複習一下。

Theorem 1：

設線性共軛梯度法的第

步迭代的結果

不是解，那麼有以下結論成立

（1）

$\operatorname{span} (r_0, r_1, \cdots, r_k) = \operatorname{span}(r_0, Ar_0, \cdots, A^k r_0)$

（2）

$\operatorname{span}(p_0, p_1, \cdots, p_k) = \operatorname{span}(r_0, Ar_0, \cdots, A^k r_0)$

（3）

$r_k^T p_i = 0, \forall i < k$

（4）

$p_k^T Ap_i = 0, \forall i < k$

具體的來說，我們的演算法構造可以寫成這樣的一個形式

關於

$\alpha_k, x_{k + 1}, r_{k+1}, p_{k + 1}$

的選取和定義我們都在上一節有提過。只有

$\beta_{k + 1}$

怎麼取我們沒有說，但是事實上，根據我們的

$p_{k + 1} = - r_{k + 1} + \beta_{k + 1}p_k$

，左乘一個

$p_{k}^T A$

即可（因為我們的共軛性保證了

$p_{k}^T Ap_{k + 1} = 0$

）。

但是這個方法事實上還是差了點意思，這是因為在實現方式上，我們發現有些矩陣與向量的乘法，

可以透過向量與向量的內積做代替

，而有些可以重複利用的部分，我們也可以

只計算一次

。所以就會演變成下面這樣的方法

為什麼這樣的修改可以？我們把它單獨列成一個性質。

Proposition 1：

證明圖中的公式等價。

其實這些公式的證明關鍵都落在我們最開頭的幾個共軛性上，我們一個一個來看。

對於

$\alpha_k = \frac{-r_k^T p_k}{p_k A p_k}$

，注意到我們有

$p_k = -r_k + \beta_k p_{k - 1}$

，再利用上

$r_k^T p_{k - 1} = 0$

即可。對於

$r_{k + 1} = Ax_{k + 1} - b$

，其實只需要注意到

，所以歸根到底就是

$r_{k + 1} - r_k = A(x_{k + 1} - x_k) = A\alpha_k p _k$

所以這個性質也不難說明。至於

$\beta_{k + 1} = \frac{r_{k+1}^T A p_k}{p_k^T A p_k}$

，我們其實根據上面這個可以得到

$Ap_k = \frac{r_{k + 1} - r_{k}}{\alpha_k}$

代入就可以得到分子為

$r_{k+1}^T r_{k + 1}$

，因為

$r_{k+1}^T r_k = 0$

（想想為什麼？）。至於分母，注意到

$p_k^T r_{k + 1} = 0$

，

（想想為什麼？），就可以得到為

，所以最終的

$\beta_{k+1}$

的形式我們也算證明完成了。

在新的這個實現方式下，其實主要的計算開銷就落在了

，

和

上。相比較之前的而言，我們不需要計算

這樣的東西，這算是一個比較好的最佳化。

非線性共軛梯度法

事實上，非線性共軛梯度法相比較線性共軛梯度法而言，只是修改了幾個標記而已。但是它們的成功也是有理論保障的，我們會慢慢看到。

首先我們根據我們之前的線性共軛梯度法的框架來看一下非線性的情況究竟改了哪些。

初值上，我們一開始是

，這是因為我們是以

二次凸問題

作為線性共軛梯度法來舉例的。在這種情況下，事實上一開始的這個殘差就是梯度，所以在非線性的情況下，我們設定了

$r_0 = \nabla f(x_0)$

，也就是說，

初始搜尋方向設定為負梯度方向

。同理也可以解釋我們的第4步和第5步，線上性共軛梯度法中，它的目標是為了解

，使得

儘可能的小。但是本質上，其實就是為了使得

最佳化時梯度可以儘量的趨於0

，這也符合我們對最佳化演算法的要求。

看似到這裡問題就結束了，但是有一個隱含的問題在於演算法的第2步。一般情況下，由於數值誤差的存在，

最佳化的精確步長是難以求得的

。所以在非線性共軛梯度法下，實際的效果總是會差那麼一些。同樣的也正是因為這個，我們對於步長會放鬆限制，

不再採用精確步長

。有一種可以採納的思路就是使用Strong-Wolfe條件來選取步長（可以去看一下第1-2節）。下面的這個性質保證了這樣的選取的步長的方向

依然是下降方向

。

Proposition 2：

設

$\{x_k\}$

為使用Fletcher-Reeves格式（也即

$\beta_{k + 1} = \frac{\nabla f(x_{k + 1})^T \nabla f(x_{k+1})}{\nabla f(x_k)^T \nabla f(x_k)}$

）非線性共軛梯度法得到的迭代點序列。Strong-Wolfe條件的係數滿足

，那麼搜尋方向

滿足

$-\frac 1 {1 - c_2} \le \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2} \le \frac{2c_2 - 1}{1 - c_2}$

對於這種第一眼看毫無想法的式子，往往可以使用數學歸納法。

的情況對應著初值的情況，因為我們初始的搜尋方向為負梯度方向，所以這個時候步長與梯度的夾角為平角（也就是餘弦為1），代入不難得到結論成立。

現在考慮一下，如果對於

成立，對於

的情況會如何？注意到我們根據公式

$p_{k + 1} = -\nabla f(x_{k+1}) + \beta_{k+1}p_k$

，有

$\frac{\nabla f(x_{k+1})^Tp_{k + 1}}{\|\nabla f(x_{k+1})\|^2} = -1 + \beta_{k + 1}\frac{\nabla f(x_{k+1})^Tp_k}{\|\nabla f(x_{k+1})\|^2} = - 1 + \frac{\nabla f(x_{k+1})^T p_k}{\|\nabla f(x_k)\|^2}$

最後的一項是因為

$\beta_{k+1} = \frac{\|\nabla f(x_{k + 1})\|^2}{\|\nabla f(x_k)\|^2}$

。那麼根據Strong-Wolfe條件中的第二個不等式，我們有

而如果代入這個演算法，就可以得到

$|\nabla f(x_{k+1})^T p_k| \le -c_2 \nabla f(x_k)^T p_k$

這個式子就搭建了一個橋樑，把它代入之後就可以得到

$-1 + c_2 \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2} \le- 1 + \frac{\nabla f(x_{k+1})^T p_k}{\|\nabla f(x_k)\|^2} \le -1 -c_2 \frac{\nabla f(x_k)^T p_k}{\|\nabla f(x_k)\|^2}$

代入我們的歸設即可得到結論。

好的，看來我們解決了這個步長的問題。但是卻產生了一個新的問題：

迭代可以順利進行嗎

？具體來說，就是，

這個方法是不是可以自行修正的

？我們考慮一下假如說我們有

$\cos (\theta_k) \simeq 0$

，也就是說

$\frac{-\nabla f(x_k)^T p_k}{\|\nabla f(x_k) \| \| p_k \|} \simeq 0$

，也就是說

與負梯度方向幾乎正交。這個時候我們會發現，我們根據Proposition 2，有

$\frac{1 - 2 c_2}{1 - c_2} \frac{\|\nabla f(x_k)\|}{\|p_k\|} \le \cos \theta_k \le \frac{1}{1 - c_2} \frac{\|\nabla f(x_k)\|}{\|p_k\|}$

那麼可以得到的結論是

$\|\nabla f(x_k)\| << \|p_k\|$

，同時因為搜尋方向近乎垂直，就很難得到好的下降，所以我們也會有

$x_{k + 1} - x_k \simeq 0$

，那麼這個時候呢，你可以發現，

迭代幾乎沒有進行

，也就是說

梯度幾乎沒有變化

，

$\beta_{k + 1} \simeq 1$

，這個時候，根據

$p_{k + 1} = - \nabla f(x_{k+1}) + \beta_{k+1} p_k \simeq -\nabla f(x_k) + p_k \simeq p_k$

（根據梯度模長與

$\|p_k\|$

的比較關係），就可以得到我們這個時候，

搜尋方向也幾乎沒有變化

。結合這兩點來看，你會發現其實如果

在某一步搜尋方向取得不好，之後也別指望演算法能夠自己修好

。所以這樣的格式其實是不可取的。

下面這張圖解釋了為什麼我們認為

$x_{k+1} \simeq x_k$

說了這麼多，那麼有什麼解決方案嗎？我們看出來，只要破壞任何一條我們思考的依據，都應該算是可行的。因此我們可以考慮設定一些其它的

$\beta$

的格式。

Definition 1： Polak-Ribiere， Hestenes-Stiefel

定義P-R格式和H-S格式的

$\beta$

為

$\beta_{k + 1}^{PR} = \frac{\nabla f(x_{k + 1})^T (\nabla f(x_{k+1}) - \nabla f(x_k))}{\nabla f(x_k)^T \nabla f(x_k)}$

$\beta_{k + 1}^{HS} = \frac{\nabla f(x_{k+1})^T (\nabla f(x_{k + 1}) - \nabla f(x_k))}{(\nabla f(x_{k + 1}) - \nabla f(x_k))^T p_k}$

在精確步長的意義下，這兩個式子是等價的，並且化歸到二次凸問題也是可行的

。但是因為它們不是我們的重點，所以我們這裡就不證明了，感興趣的讀者可以自己嘗試。

解決問題了嗎？

很遺憾，依然沒有

。這兩個格式

都不存在全域性收斂性

。為了使得全域性收斂性滿足，基於這兩個格式的修正也有很多，這裡提一個格式為下面的這個格式。

Definition 2： Dai-Yuan

$\beta_{k + 1}^{DY} = \frac{\nabla f(x_{k + 1})^T \nabla f(x_{k+1})}{(\nabla f(x_{k+1}) - \nabla f(x_k))^T p_k}$

這個方法同時可以保證全域性收斂性，也就是對應的下面的這個定理。

Theorem 2：

設

$\mathcal{N}_{x_0} = \{x: f(x) \le f(x_0)\}, f\in C^1$

，

$\nabla f(x)$

在

$\mathcal{N}_{x_0}$

內是Lipschitz連續的，步長採取Wolfe條件，那麼有

$\liminf_{k \to \infty} \|\nabla f(x_k)\| =0$

要說明全域性收斂性，我們會使用到Zoutendijk條件（忘了的話可以看一下第2節~）。也就是說，一方面，我們希望觀察一下

$\sum_{k = 0}^\infty \cos^2 \theta_k |g_k|^2 = \sum_{k = 0}^\infty \frac{(g_k^Tp_k)^2}{|p_k|^2}$

。這裡

$g_k = \nabla f(x_k)$

。另一方面，我們希望看看

我們的方向是不是下降方向

。如果是最速下降法自然不需要說明後面這一件事，但是在共軛梯度法上其實這一點沒有那麼顯然。

注意到，因為我們對步長要求是Wolfe條件，所以可以推出這個級數是收斂的。那麼自然的，我們希望說明的就是，如果我們的結論不成立，那麼這個級數就無法收斂。

自然希望說明級數收斂，自然我們希望看到的就是對

$\frac{(g_k^Tp_k)^2}{\|p_k\|^2}$

的估計。而

也正好可以用來判斷方向是否是下降方向。注意到我們有

$p_{k + 1} = - g_{k + 1} + \beta_{k + 1} p_k = -g_{k + 1} + \frac{\|g_{k + 1}\|^2p_k}{(g_{k + 1} - g_k)^T p_k}$

所以化簡就可以得到

$g_{k + 1}^T p_{k + 1} = \beta_{k + 1}^{DY} g_k^T p_k$

（想想為什麼？）有了這個式子之後，可以看出，如果我們的第一步的方向是下降方向，那麼之後是否一直是下降方向，取決於

$\beta_{k + 1}^{DY}$

的情況。而注意到根據weak-wolfe條件的第二個不等式（也可以說是

Curvature條件

），我們可以得到

$(g_{k+1} - g_k)^T p_k \ge (c_2 - 1)g_k^T p_k$

所以如果第一步的方向是下降方向，那麼可以得到

$(g_{k+1} - g_k)^T p_k >0$

，對應的就是

$\beta_{k+1}^{DY}$

，結合我們第一步方向是負梯度方向，就可以得到我們每一步都是下降方向的結論。

好的，我們現在再來看看怎麼估計我們的

$\frac{(g_k^Tp_k)^2}{\|p_k\|^2}$

，而分子其實我們已經有了一個很好的估計，所以現在只需要再看看

$\|p_k\|^2$

可以怎麼估計就可以了。注意到我們有

$p_{k + 1} + g_{k + 1} = \beta_{k + 1}p_k$

，兩邊平方，有

$\|p_{k + 1}\|^2 = \beta_{k + 1}^2 \|p_k\|^2 - 2 g_{k + 1}^T p_{k + 1} - \|g_{k + 1}\|^2$

然後除以

$g_{k+1}^T p_{k +1}$

，代入我們之前證明的性質，就可以得到

$\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} = \frac{ \|p_k\|^2}{(g_k^T p_k)^2} - \frac{2}{ g_{k + 1}^T p_{k + 1}} - \frac{\|g_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2}$

根據配方法（具體怎麼配留給讀者思考），我們可以得到

$\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} \le \frac{ \|p_k\|^2}{(g_k^T p_k)^2} + \frac 1 {\|g_{k + 1}\|^2}$

你會發現，這樣的話就相當於找到了相鄰兩項差的上界。所以可以透過遞推的方式得到這個項的估計。事實上，代入初始的負梯度方向就可以得到

$\frac{\|p_{k + 1}\|^2}{(g_{k + 1}^T p_{k + 1})^2} \le \sum_{i = 0}^{k + 1}\frac 1{\|g_{i}\|^2}$

萬事俱備，只差反證。如果說存在

，使得

$\|g_k\| \ge c$

，那麼這個時候，你會發現第

項其實都

$\ge \frac {c^2}{k}$

，注意到調和級數是發散的，所以和式不收斂，這就矛盾了，也就說明了結論的成立。

到此，我們算是得到了一個能用的非線性共軛梯度法。當然了實際情況下，如果有了更多的資訊（比方說對於函式的性質瞭解很透徹），之前的方法也不是不能使用，但是如果毫無瞭解，使用一個沒有全域性收斂性的演算法，還是過於冒險了一點。

最後我們提一個實際演算法中會經常使用的trick。因為這個演算法非常依賴步長的性質（因為有一步要求是精確步長），加上它基本上沒有自我修復的能力，所以很多時候需要

加一些外界的干預

。有一個方法是判斷

$|\frac{\nabla f(x_{k + 1})^T \nabla f(x_k)}{\|\nabla f(x_{k +1})^2\|}| < \epsilon$

如果這個條件滿足，那麼說明

$\nabla f(x_{k+1})$

和

$\nabla f(x_k)$

是差別很大的，也就是說

$x_{k+1} \simeq x_k$

不太可能。這個時候我們認為演算法執行正常，就不做干預。反過來，如果不滿足，那麼說明可能演算法“卡住了”。這個時候可能會做一步重啟，也就是考慮

重新設定搜尋方向為當前的負梯度方向

。

預條件方法

預條件（Preconditioning）方法

算是一個最近比較火的方法。它的主要思路是對問題

做一個線性變換，使得新的問題的計算具有更低的複雜度

。比方說對於二次凸問題，在數值上，共軛梯度法

會受到線性系統矩陣的條件數的影響

。所以為了降低這個影響，有一種思路是考慮設定一個變換

$\hat x = Cx$

這個時候，我們會得到對應的二次凸問題為

$\frac12 x^T A x - b^T x = \frac12 \hat x ^T C^{-T} A C^{-1}\hat x - (C^{-T}b)^T \hat x$

這個時候，令

$\hat A = C^{-T}AC^{-1}$

，

$\hat b = C^{-T}b$

，就可以得到一個和之前的系統

形式完全一樣的最佳化目標

。

我們在之前提到過，在原始的方法中，

是一個大的計算開銷的部分，那麼在這個地方，其實對應的就是

$C^{-T}AC^{-1}$

這個東西，我們希望這個東西的條件數小一些，這個時候計算複雜度也就相對應的會小一些。所以事實上我們希望做的事情就是使得

$C^TC \simeq A$

有一個很好的例子就是

偏微分方程數值解

。在

中，我們有提過，對於三大經典方程，我們一般都會得到一個三對角的矩陣。這個矩陣的性質比較好，但是實際的運作中可能會出現非三對角的情況比較雜亂的情況，因此有一個方案就是

取 #FormatImgID_108# 為矩陣的三對角的部分

。這個時候就會發現，一方面我們避開了那些數值誤差導致的雜亂的矩陣元素（所以條件數會大大下降），另一方面也可以使得它與原始矩陣

的差距不會那麼大。

這樣的一個預條件做完之後自然還需要把原始的點再映射回來，所以綜合起來，我們可以把演算法寫成這樣的格式。

這樣的話，其實主要的開銷就會變成

$(C^TC)^{-1}r_k$

這樣的東西。而如果我們考慮之前的那種方法（也就是說這個東西為矩陣

的三對角部分），就會使得這個線性系統的計算也比較方便。

對於非線性共軛梯度法，其實它的主要的開銷依然沒有變，只不過這個時候主要的開銷會變成

$(C^TC)^{-1}\nabla f(x_k)$

這樣的東西，同時因為非線性共軛梯度法的情況下，

不是恆定的，但是我們注意到

它其實就是二次凸問題的海塞矩陣

。所以一般來說，我們會讓

逼近於海塞矩陣，同時擁有較低的條件數，這樣的話預條件才算達到了目標。

一個比較實用的帶預條件的非線性共軛梯度法如下

最後，我們放一個共軛梯度法的數值實驗結果。

這裡的

座標對應為梯度的模長。

就是wolfe條件中第二個不等式的係數。這個係數就

限制了對於步長是否精確的要求

。可以看出，

如果取得越小，對應的步長就要求越靠近精確步長（想想為什麼？），所以可以看出共軛梯度法的表現就越好。

到此，我們算是介紹完了共軛梯度法的相關內容。

信賴域方法

信賴域（Trust-Region）方法算是線搜尋方法的一個拓展。它的核心思想是

用一個好解的區域性模型去近似當前迭代點附近的函式情況

。線搜尋方法每一次都會找到下一步的迭代點，同時我們也有很完備的理論，但是

僅僅是探索一個點和一個方向總是感覺有點不放心

。事實上到後面我們會看到，有些方法會更適合使用信賴域的思想，也正是因為它在使用線搜尋框架的時候，會遇到一些麻煩。

簡單的概括一下信賴域演算法思想的重點，就是。

1。找到一個好解的區域性模型，設定這個區域性模型的探索範圍。

2。如果這個解符合真實情況，就採用，否則不採用

3。如果這個解符合真實情況，那麼擴大模型探索的範圍，否則縮小範圍。

下面是一個比較常見的信賴域演算法的框架。

我們可以看出，這裡牽涉到了幾個元素：半徑

$\Delta$

，下降程度

$\rho_k$

，模型

，事實上就對應了我們之前說的信賴域演算法的核心思想。這裡

$\mathbb{B}(\Delta)$

就是半徑為

$\Delta$

的球。

半徑

$\Delta$

表示了步長可以取的範圍，換句話說，

我的這個步長可以伸多遠

？而

$\rho_k$

就是衡量我的下降情況的。如果

$\rho_k$

很大，那麼這個時候相當於分子很大（因為分母是你設定的模型，因為要求在你規定的模型下取到最小，所以

一般是固定的，與

無關的），也就是說

下降的很多

。那自然就認為你的模型符合了函式的真實情況。符合了真實情況我們就會採用這個步長，也就是更新為

$x_{k + 1} = x_k + p_k$

，否則就不會改變。同樣的，如果說我們的模型表現的好，下降的很多，一般來說會考慮擴大半徑，反過來就會縮小半徑。當然瞭如果表現的一般，不好不壞，那麼這個時候就會考慮維持當前的半徑。

在上面的這個模型中，我們的假設是

$m_k(p) = f(x_k) + \nabla f(x_k)p + \frac12 p^T B_k p$

這是二次模型，事實上也可以取三次模型等，具體的形式因為我們用不上，所以這裡就不給出了。事實上模型的次數越高，逼近效果也就越好，但是對應的計算的複雜度也就會上升。另外，這裡的

取的是

對稱陣

。這麼取的原因主要在於

一些比較經典的演算法都會依賴到對稱陣的結構

。具體的我們到後面的章節會看到。

柯西點

如果我們加一些限制條件，在方向的匯出上

只考慮一次模型

，得到的這樣的解的點就是柯西（Cauchy）點。雖然信賴域演算法中基本上沒有模型使用一次函式的逼近，但是我們有性質說明，

即使這樣的演算法也可以保證全域性收斂性

。

首先我們要看一下如何匯出柯西點。

第一步找方向

。首先我們注意到，一次模型就是去掉了關於

的二次項，也就是說

$p_k^s = \arg\min_{\|p\| \le \Delta_k}f(x_k) + \nabla f(x_k)^T p$

那麼注意到

是一個常數，所以這個時候只需要

$\nabla f(x_k)$

與

方向相反就好，這個時候結合

$\|p\| \le \Delta_k$

，可以得到

$p_k^s = \frac{-\nabla f(x_k)}{\|\nabla f(x_k)\|} \Delta_k$

第二步找收縮因子

，我們考慮一下計算收縮因子

$\tau_k$

，滿足

$\tau_k = \arg \min_{\tau \ge 0, \|\tau p_k^s\| \le \Delta_k}m_k(\tau p_k^s)$

這個時候也不難求得

$\tau_k = \begin{cases}1 & \nabla f(x_k)^T B_k \nabla f(x_k) \le 0 \\ \min(\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))}, 1) & \operatorname{otherwise}\end{cases}$

這個式子看似比較複雜，但是其實就是一個二次函式極值的討論，屬於高一數學的難度。這裡我們就不展示具體計算細節了，留給讀者思考。

最終，我們可以得到

$p_k^c = -\tau_k \frac{\nabla f(x_k)}{\|\nabla f(x_k)\|} \Delta_k$

這也就是最終的柯西點。

柯西點的全域性收斂性

接下來我們要說明的就是

柯西點的全域性收斂性

。為此我們先給出一個不等式。

Proposition 3：

存在

$c_1 \in (0, 1)$

，使得

$m_k(0) - m_k(p_k^c) \ge c_1 \|\nabla f(x_k)\| \min (\Delta_k, \frac{\|\nabla f(x_k)\|}{\|B_k\|})$

我們證明一下這個結論。既然我們的

$\tau_k$

有多種情況，那麼自然需要分情況討論。

如果

$\nabla f(x_k)^T B_k \nabla f(x_k) \le 0$

，那麼這個時候，

$\tau_k = 1$

，所以可以直接把

代入，可以得到

$m(p_k^c) - m(0) = -\frac{ \Delta_k \nabla f(x_k)^T \nabla f(x_k)}{\|\nabla f(x_k)\|} + \frac 12 \frac{\Delta_k^2}{\|\nabla f(x_k)\|^2}\nabla f(x_k)^T B_k \nabla f(x_k) \\$

第二項根據條件就可以得到它是小於0的，所以我們可以考慮去掉它。所以化簡第一項，可以得到

$m(p_k^c) - m(0) \le-\|\nabla f(x_k)\|\Delta_k \le - \|\nabla f(x_k)\| \min (\Delta_k, \frac{\nabla f(x_k)}{\|B_k\|})$

再兩邊同乘-1，即可得到結論。

如果是另一個情況，也就是說

$\nabla f(x_k)^T B_k \nabla f(x_k) > 0$

，那麼這個時候，

$\tau_k$

又會對應兩種情況。如果說

$\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))} \le 1$

，那麼這個時候對應的式子自然會寫的很長，我們直接給出化簡後的結果，也即

$m(p_k^c) - m(0) = -\frac12 \frac{\|\nabla f(x_k)\|^4}{\nabla f(x_k)^T B_k \nabla f(x_k)} \le -\frac12 \frac{\|\nabla f(x_k)\|^2}{\|B_k\|} \le -\frac12 \|\nabla f(x_k)\| \min (\Delta_k, \frac{\|\nabla f(x_k)\|}{\|B_k\|}) \\$

如果說有

$\frac{\|\nabla f(x_k)\|^3}{(\Delta_k \nabla f(x_k)^T B_k \nabla f(x_k))} \ge 1$

，這個情況下

$\tau_k = 1$

，結論也很好證明，因為這個時候式子和之前的形式一樣，並且我們有

$\frac{\|\nabla f(x_k)\|^3}{\Delta_k} \ge \nabla f(x_k)^T B_k \nabla f(x_k)$

。所以不難得到

$m(p_k^c) - m(0) \le -\frac12 \Delta_k \|f(x_k)\|$

後面的話相信也都知道怎麼寫了，這裡就略過了。

這個性質就是用來證明下面的全域性收斂性的。

Theorem 3：

設在信賴域演算法中

$\eta = 0$

，設存在

$\beta$

，使得

$\|B_k\| \le \beta$

，並且存在

$\delta$

，使得

在

$\mathcal{N}_{x_0}$

上存在下界，且在

$\mathcal{N}_{x_0}^\delta = \{x: \|x - y\| \le \delta, \exist y \in \mathcal{N}_{x_0}\}$

上Lipschitz連續，並且子問題的解均滿足Proposition 3，那麼有

$\liminf_{k \to \infty} \|\nabla f(x_k)\| =0$

我們證明一下這個結論，還是一樣，考慮反證。設對任意的

$k \ge K$

，我們都有

$\|\nabla f(x_k)\| \ge \epsilon$

，那麼我們的想法是，觀察一下我們的下降情況

$\rho_k$

，看它是否會有一些異常。注意這裡我們的方法

不再是線搜尋方法了

，所以不能再使用Zoutendijk了。

注意到我們可以考慮構造式子

$|\rho_k - 1| = |\frac{m_k(p_k) - f(x_k + p_k)}{m_k(0) - m_k (p_k)}|$

分母非常好辦，因為我們上面的那個式子

$m_k(0) - m_k(p_k) \ge c_1 \epsilon \min(\Delta_k, \frac{\epsilon}{\beta})$

（中間是有跳步的，讀者可以自己補上），分子稍微麻煩些，把式子寫開可以得到

$|m_k(p_k) - f(x_k + p_k)| = |\nabla f(x_k)^T p_k + \frac12 p_k^T B_k p_k + f(x_k) - f(x_k+p_k)| \\$

根據Taylor展開，我們有

$f(x_k + p_k) = f(x_k) + \nabla f(x_k)^T p_k + [\nabla f(x_k + tp_k) - \nabla f(x_k)]^T p_k$

其中

$t \in (0, 1)$

。在這種情況下，可以發現前兩項代回之後會被消掉，所以其實只會剩下

$|m_k(p_k) - f(x_k + p_k)| \le |\frac12 p_k^T B_k p_k + [\nabla f(x_k + tp_k) - \nabla f(x_k)]^T p_k| \\ \le \frac \beta 2 \|p_k\|^2+L \|p_k\|^2$

這裡用到的主要是柯西不等式和各種題目給的條件。綜合起來，加上

$\|p_k\| \le \Delta_k$

，就會有

$|\rho_k -1| \le \frac{\Delta_k^2 (\frac12 \beta + L)}{c_1 \epsilon \min (\Delta_k, \frac\epsilon \beta)}$

為什麼要給定這個呢？這是因為我們希望，在這個條件下，我們能夠找到一個

半徑與下降情況的制衡

，進而得到矛盾。事實上，我們希望說明的是

Lemma 1：

若

$\Delta_k \le \bar \Delta = \min (\frac12 \frac{c_1 \epsilon}{\frac \beta 2 + L}, \delta)$

，那麼會有

$|\rho_k - 1| \le \frac12$

。

這個性質的說明不是很困難，因為我們有

$\bar \Delta \le \frac \epsilon \beta$

，所以分母其實那個值是固定的。也就是說可以得到

$|\rho_k - 1| \le \frac{\Delta_k (\frac \beta 2 + L)}{c_1 \epsilon} \le \frac12$

我們依然有所跳步，留給讀者補充。

這個性質證明完之後，其實我們就可以發現，如果我們的半徑取得足夠的小，那麼對應的

$\rho_k$

就會足夠的好，這種情況下半徑就無法得到收縮。反過來，如果我們的

$\rho_k$

比較一般，那麼這個時候半徑就會收縮，收縮到最後又會使得步長足夠的好。這個思考邏輯指引我們考慮

$\rho_k$

的取值情況。

如果說我們存在一個無限子列

，滿足

$\rho_k \ge \frac14,\forall k \in S$

，那麼這個時候，我們可以考慮，對於任意的

$k \ge K, k \in S$

（

足夠大），我們可以得到

$f(x_k) - f(x_{k + 1}) \ge \frac14 [m_k(0) - m_k(p_k)] \ge \frac14 c_1 \epsilon \min(\Delta_k, \frac \epsilon \beta)$

可以看到右邊並不是一個趨於0的項，所以事實上可以考慮對子列中的所有項求和，那麼因為左邊實質上是函式的差，求和有限，右邊卻會得到一個無限的值，因此這會產生矛盾。

反過來，如果說這樣的子列不存在，那麼也就是說，只有有限個

$\rho_k \ge \frac 14$

，相當於說

$\Delta_{k + 1} = \frac14 \Delta_k$

會發生無數次，那麼這個時候可以推出來

$\Delta_k \to 0$

。這是不可能的，因為我們知道

$\Delta_k$

足夠小的時候，

$\rho_k$

取得會足夠的好，導致半徑無法收縮。所以這也是個矛盾。

到此我們就證明了這個全域性收斂性，而事實上，我們的柯西點就是滿足Proposition 3這個不等式的，因此即使是隨便取的柯西點，我們也能保證演算法是有效的。

好的，這一節就到這裡，關於信賴域法還剩下一點內容，我們到之後再說。

小結

本節主要介紹了非線性共軛梯度法和信賴域法。非線性共軛梯度法的形式和線性共軛梯度法相同，但是我們為了保證它的有效性，也介紹了很多有趣的技巧。對於信賴域方法，它是一種不同於線搜尋方法的最佳化框架，我們這一節的後半部分也介紹了一些簡單的情形，但是即使是簡單的情形，也可以推出很好的性質。所以也不難怪為什麼很多方法會更傾向於使用信賴域方法了。

事實上，如果需要解完全的二次模型，也有很多成型的方法，我們下一節的開始會介紹這些。

——————————————————————————————————————

本專欄為我的個人專欄，也是我學習筆記的主要生產地。

任何筆記都具有著作權，不可隨意轉載和剽竊

。

個人微信公眾號：

cha-diary

，你可以透過它來獲得最新文章更新的通知。

《一個大學生的日常筆記》專欄目錄：筆記專欄|目錄

《GetDataWet》專欄目錄：GetDataWet|目錄

想要更多方面的知識分享嗎？可以關注專欄：一個大學生的日常筆記。你既可以在那裡找到通俗易懂的數學，也可以找到一些雜談和閒聊。也可以關注專欄：GetDataWet，看看在大資料的世界中，一個人的心路歷程。我鼓勵和我相似的同志們投稿於此，增加專欄的多元性，讓更多相似的求知者受益~

小蜜蜂問答

小蜜蜂問答

數值最佳化（4）——非線性共軛梯度法，信賴域法

推薦文章

小蜜蜂問答

小蜜蜂問答

數值最佳化（4）——非線性共軛梯度法，信賴域法

相關文章

貓吃完貓糧可以吃零食嗎？

男朋友喜歡穿衝鋒衣，新年送衝鋒衣的話買什麼牌子的好？

當下的海道教育，發展怎麼樣？

多智慧體強化學習入門（七）——AC for CDec-POMDP 大規模規劃學習演算法

推薦文章