信賴域演演算法

在每次迭代中給出一個信賴域，這個信賴域一般是當前迭代點 的一個小鄰域。然後，在這個鄰域內求解一個子問題，得到試探步長（trial step） ，接著用某一評價函數來決定是否接受該試探步以及確定下一次迭代的信賴域。

如果試探步長被接受，則： ，否則， 。

新的信賴域的大小取決於試探步的好壞，粗略地說，如果試探步較好，在下一步信賴域擴大或者保持不變，否則減小信賴域。

設當前點 的鄰域定義為： ，其中，稱為信賴域半徑。

目標函數在極值點附近近似一個二次函數，因此對於無約束優化問題，利用二次逼近，構造如下信賴域子問題：

其中， ，是目標函數 在當前迭代點 處的梯度，對稱，是 在 處Hesse陣 或者其近似。

設 是信賴域子問題的解。目標函數 在第 步的實際下降量（真實下降量）：

二次模型函數 的下降量（預測下降量）：

定義比值：

它衡量了二次模型與目標函數的逼近程度，越接近於1，表明接近程度越好。因此，我們也用這個量來確定下次迭代的信賴域半徑。

（1）越接近與1，表明接近程度越好。這時可以增大以擴大信賴域；

（2）但是不接近於1，保持 不變；

（3）如果 接近於0，減小，縮小信賴域。

Step1：給出初始點，初始信賴域半徑，開始迭代。

Step2：到第k步時，計算梯度 與Hesse陣。

Step3：求解信賴域模型，得到試探步長，計算比值。

Step4：若，說明步子邁得太大了，應縮小信賴域半徑，令。

Step5：若 且，說明這一步已經邁到了信賴域半徑的邊緣，並且步子有點小，可以嘗試擴大信賴域半徑，令。

Step6：若，說明這一步邁出去之後，處於“可信賴”和“不可信賴”之間，可以維持當前的信賴域半徑，令。

Step7：若，說明函數值是向著上升而非下降的趨勢變化了（與最優化的目標相反），說明這一步邁得錯得“離譜”了，這時不應該走到下一點，而應“原地踏步”，即，並且和上面 的情況一樣縮小信賴域。反之，在 的情況下，都可以走到下一點，即。

信賴域演演算法具有整體收斂性。