信賴域子問題與 Fidelity

信賴域法的思想很好理解：就是利用一個好解的

區域性模型

m_x(p)

來近似當前迭代點附近 （附近就是一個區域

||p||\le \Delta

） 的函式情況

f(x+p)

。

信賴域子問題的定義：假設

x\in \mathbb{R}^n

且

f:\mathbb{R}^n \rightarrow \mathbb{R}

為目標函式，在區域

||p||\le \Delta

內目標函式的近似函式為

m_x(p)

，則置信域子問題的目的是尋找

\arg\min \{m_x(p):||p|||\le \Delta \}

也就是說信賴域子問題求的是近似函式在信賴域內取最小時對應的自變數取值

p

。通常近似函式可以用二次函式來表示（注意這是關於

p

的函式）

m_x(p)=f(x)+\nabla f_x^T p + \frac{1}{2}p^TBp

其中

B

為模型 Hessian，這裡並沒有要求它是正定的。

近似函式

m_x

在點

p+x

的 Fidelity 定義為：（可以理解為兩個函式斜率的比值，用來衡量近似函式的可信程度）

\rho (m_x,f,p,\Delta)=\frac{f(x+p)-f(x)}{m_x(p)-m_x(0)}

我們需要根據近似函式

m_x

對目標函式

f

的近似程度的好壞來調整信賴域的大小：令

0<c_1<c_2<1

如果

\rho \ge c_2

且

p

是用於函式下降，函式

m_x

能夠很好地近似

f

，此時我們能夠增大置信域；（可以理解為

f

和近似函式的斜率（導數）相近，所以

m_x

能夠較好近似

f

）

如果

\rho \le c_1

且

p

是用於函式下降，函式

m_x

不能有效近似

f

，此時應該收縮置信域；（可以理解為函式的導數偏差大，近似效果肯定不好了）

其他情況下不需要對信賴域做出調整。

假設

p

是函式

m_x

的下降方向，令

\eta \in (0,1/4]

如果

\rho < \eta

則方向

p

並不能使得函式

f

具有一定的下降量，

x_{k+1}=x_k

如果

\rho \ge \eta

則方向

p

能夠使得函式

f

有較大的下降，

x_{k+1}=x_k+p

Fidelity 演算法

信賴域調整演算法

輸入：閾值

0<c_1<c_2<1

（通常取

c_1 = 1/4,c_2 = 3/4

），信賴域

\Delta,\Delta_{max},\rho_x

判斷：

如果

\rho_x >c_2

（可以理解為擴大信賴域，但又不能超過最大信賴域的約束）

如果

\rho < c_1

則

\Delta \leftarrow \Delta /2

（可以理解為縮小信賴域）

輸出：

\Delta

解的接受演算法

輸入：閾值

\eta \in (0,1/4], \rho,x,p

判斷：

如果

\rho_x(p)\ge \eta

則

x_{k+1}=x_k+p

否則

x_{k+1}=x_k

輸出：

x_{k+1}

子問題的近似解

柯西點

定義：令

m_x

為函式

f

在

||p||\le \Delta

的近似函式，

p^S

為

m_x(0)

處的單位最陡下降方向（

||p^S||=1

），求解關於

\tau

的最佳化命題

\arg\min \{m_x(\tau p^S):\tau \le \Delta\}

則

p^C=\tau p^S

為函式

m_x

的柯西點。可以理解為柯西點是函式

m_x

在區域

||p||\le \Delta

內沿著最陡下降方向進行線搜得到的最小點。

柯西點的計算：令

m_x

是函式

f

在區間

||p||\le \Delta

的一個二次近似模型

m_x(p)=f(x)+g^Tp+\frac{1}{2}p^TBp

則柯西點為（其實就是高中的二次函式求最值問題，需要考慮邊界條件）

p^C=\begin{cases} \frac{-g}{||g||}\min \left( \Delta ,\frac{||g||^3}{g^TBg} \right)& \,\,g^TBg>0\ \frac{-g}{||g||}\Delta& \,\,g^TBg\le 0\ \end{cases}

注：使用柯西點的收斂速率並不高。

Dogleg 法

狗腿路徑的定義：令

m_x

為函式

f

的二次近似函式且

B>0

，令

p^C

為柯西點，

p^{min}=-B^{-1}g

為近似函式的無約束情況下的最小點，狗腿路徑

p^{DL}(t)

為

p^{DL}\left( t \right) =\begin{cases} p^Ct& \,\,t\in \left[ 0,1 \right]\\ p^C+\left( t-1 \right) \left( p^{min}-p^C \right)& \,\,t\in \left[ 1,2 \right]\\ \end{cases}

狗腿路徑可以理解為一種

兩階段

的方法，先朝最陡方向走，再往近似函式的無約束最小點走（如果碰到信賴域的邊界就不走了）。

狗腿法的定義：選擇

x

的迭代點

x_{k+1}=x_k + p^{DL}(\tau)

且

||p^{DL}(\tau)||=\Delta

。

狗腿路徑的性質：假設

p^{DL}(t)

為二次函式

m_x

的狗腿路徑且半徑

\Delta = \infty

，模型的 Hessian

B>0

m_x(p^{DL}(t))

是下降的

||p^{DL}(t)||

是上升的

柯西點法的全域性收斂性

引理1：柯西點

p_k^c

滿足

m_k(p_k^C)-m_k(0)\le \frac{1}{2}||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})

引理2：狗腿步長

p_k^{DL}

滿足

m_k(p_k^{DL})-m_k(0)\le \frac{1}{2}||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})

引理3：假設一個方法採用的步長

p_k

滿足

m_k(p_k)-m_k(0)\le c(m_k(p_k^C)-m_k(0))

且

c\in (0,1)

，則

p_k

滿足

m_k(p_k)-m_k(0)\le \frac{1}{2}c||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})

可以證明在一定條件下，柯西點法能夠使得：

\lim_{k \rightarrow \infty} ||g_k|| = 0

。

子問題的迭代解

子問題的精確解

最小化二次函式的條件：假設

m

為二次函式

m(p)=g^Tp + \frac{1}{2}p^TBp

其中

B

是對稱矩陣

m

取得最小值當且僅當

B\ge 0

且

g \in Im(B)

，如果

B\ge 0

則所有滿足

Bp=-g

的

p

均是

m

的全域性最小點

m

具有唯一最小點當且僅當

B>0

精確解滿足定理：向量

p^*

是信賴域問題的解

\min_{p\in \mathbb{R}^n} f(x)+g^Tp +\frac{1}{2}p^TBp:||p||\le \Delta

當且僅當

p^*

是可行的且存在

\lambda >0

(B+\lambda I)p^* = g

\lambda (||p^*||-\Delta)=0

B+\lambda I \ge 0

子問題的迭代解

精確解定理保證瞭解的存在性，因此我們需要找到滿足條件的

\lambda

，可以利用牛頓法求根的思想進行迭代求解。

算例及matlab程式碼

這裡採用信賴域法來求解一個無約束問題，信賴域子問題的求解採用柯西點法。最佳化問題為

\min f(x_1,x_2)=(x_2-0.129x_1^2+1.6x_1-6)^2+6.07cos(x_1)+10

這一函式也叫做 Branin 函式，經常被用作測試函式，它有三個全域性最優。

演算法流程

為：

初始化

重複以下步驟直到滿足收斂條件

求解區域性二次函式的最小值得到

p_k

計算

\rho_k

解的接受演算法

信賴域調整演算法

求解過程：

假設初始點為

x_1=6.00

，

x_2=14.00

，迭代的終止條件為

g_k\le 0.01

，信賴域半徑為

\Delta_0 =2.0

，

\Delta_{max}=5.0

，

目標函式的梯度

g

為

g=\left[ \begin{array}{c} 2\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right) \left( -0.258x_1+1.6 \right) -6.07\sin \left( x_1 \right)\\ 2\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right)\\ \end{array} \right]

目標函式的嚴格 Hessian 為

B=\left[ \begin{matrix} 2\left( -0.258x_1+1.6 \right) ^2-0.516\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right) -6.07\cos \left( x_1 \right)& \left( -0.516x_1+3.2 \right)\\ -0.516x_1+3.2& 2\\ \end{matrix} \right]

解的接受演算法中的閾值

\eta =0.2

，信賴域調整演算法中的

c1=0.25,c2=0.75

%% 定義函式、梯度和Hessian

f

=

@（

x1

，

x2

）

（

x2

-

0。129

*

x1

^

2

+

1。6

*

x1

-

6

）

^

2

+

6。07

*

cos

（

x1

）

+

10

；

g

=

@（

x1

，

x2

）

［

2

*

（

x2

-

0。129

*

x1

^

2

+

1。6

*

x1

-

6

）

*

（

-

0。258

*

x1

+

1。6

）

-

6。07

*

sin

（

x1

）；

。。。

2

*

（

x2

-

0。129

*

x1

^

2

+

1。6

*

x1

-

6

）］；

B

=

@（

x1

，

x2

）

［

2

*

（

-

0。258

*

x1

+

1。6

）

^

2

-

0。516

*

（

x2

-

0。128

*

x1

^

2

+

1。6

*

x1

-

6

）

-

6。07

*

cos

（

x1

），

。。。

-

0。516

*

x1

+

3。2

；

-

0。516

*

x1

+

3。2

，

2

］；

%% 初始引數設定

epsilon

=

0。01

；

Delta_0

=

2

；

Delta_max

=

5

；

x0

=

［

6

；

14

］；

c1

=

0。25

；

c2

=

0。75

；

eta

=

0。2

；

%% 迭代求解

while

1

if

norm

（

g

（

x0

（

1

），

x0

（

2

）），

2

）

<

=

0。01

break

end

g_k

=

g

（

x0

（

1

），

x0

（

2

））；

B_k

=

B

（

x0

（

1

），

x0

（

2

））；

if

g_k

‘*

B_k

*

g_k

>

0

p

=

-

g_k

/

norm

（

g_k

，

2

）

*

min

（

Delta_0

，（

norm

（

g_k

，

2

）

^

3

）

/

（

g_k

’*

B_k

*

g_k

））；

else

p

=

-

g_k

/

norm

（

g_k

，

2

）

*

Delta_0

；

end

x_temp

=

x0

+

p

；

rho

=

（

f

（

x_temp

（

1

），

x_temp

（

2

））

-

f

（

x0

（

1

），

x0

（

2

）））

/

（

g_k

‘*

p

+

0。5

*

p

’*

B_k

*

p

）；

if

rho

>

c2

Delta_0

=

min

（

2

*

Delta_0

，

Delta_max

）；

else

Delta_0

=

0。5

*

Delta_0

；

end

if

rho

>

=

eta

x0

=

x0

+

p

；

end

end

求解的結果：左圖為自變數

x

的最佳化軌跡，右圖為函式值隨迭代次數的變化。

數值最佳化（Numerical Optimization）(2)-信賴域法

下圖在等高線圖中展示最佳化路徑

數值最佳化（Numerical Optimization）(2)-信賴域法