信賴域算法是一種求解非線性最佳化問題的數值方法。信賴域算法是一種疊代算法，即從給定的初始解出發，通過逐步疊代，不斷改進，直到獲得滿意的近似最優解為止。其基本思想是把最最佳化問題轉化為一系列簡單的局部尋優問題。
基本介紹
- 中文名：信賴域算法
- 外文名：Trust region algorithm
- 領域：計算機編程
- 專業：程式設計
- 套用：最最佳化問題
- 作用：數值最佳化
信賴域算法的基本思想,信賴域方法思想,信賴域半徑的選擇,信賴域算法的步驟,信賴域算法的收斂性,
信賴域算法的基本思想
在每次疊代中給出一個信賴域，這個信賴域一般是當前疊代點
的一個小鄰域。然後，在這個鄰域內求解一個子問題，得到試探步長（trial step）
，接著用某一評價函式來決定是否接受該試探步以及確定下一次疊代的信賴域。
如果試探步長被接受，則：
，否則，
。
新的信賴域的大小取決於試探步的好壞，粗略地說，如果試探步較好，在下一步信賴域擴大或者保持不變，否則減小信賴域。
信賴域方法思想
設當前點
的鄰域定義為：
，其中，
稱為信賴域半徑。
目標函式在極值點附近近似一個二次函式，因此對於無約束最佳化問題，利用二次逼近，構造如下信賴域子問題：
其中，
，
是目標函式
在當前疊代點
處的梯度，
對稱，是
在
處Hesse陣
或者其近似。
設
是信賴域子問題的解。目標函式
在第
步的實際下降量（真實下降量）：
二次模型函式
的下降量（預測下降量）：
定義比值：
它衡量了二次模型與目標函式的逼近程度，
越接近於1，表明接近程度越好。因此，我們也用這個量來確定下次疊代的信賴域半徑。
信賴域半徑的選擇
（1）
越接近與1，表明接近程度越好。這時可以增大
以擴大信賴域；
（2）
但是不接近於1，保持
不變；
（3）如果
接近於0，減小
，縮小信賴域。
信賴域算法的步驟
Step1：給出初始點
，初始信賴域半徑
，開始疊代。
Step2：到第k步時，計算梯度
與Hesse陣
。
Step3：求解信賴域模型，得到試探步長
，計算比值
。
Step4：若
，說明步子邁得太大了，應縮小信賴域半徑，令
。
Step5：若
且
，說明這一步已經邁到了信賴域半徑的邊緣，並且步子有點小，可以嘗試擴大信賴域半徑，令
。
Step6：若
，說明這一步邁出去之後，處於“可信賴”和“不可信賴”之間，可以維持當前的信賴域半徑，令
。
Step7：若
，說明函式值是向著上升而非下降的趨勢變化了（與最最佳化的目標相反），說明這一步邁得錯得“離譜”了，這時不應該走到下一點，而應“原地踏步”，即
，並且和上面
的情況一樣縮小信賴域。反之，在
的情況下，都可以走到下一點，即
。
信賴域算法的收斂性
信賴域算法具有整體收斂性。
