04无约束优化-二阶方法

Lingfeng2024-10-10

04无约束优化-二阶方法

1. Newton方法

1.1 基本Newton方法

Definition (基本Newton方法)

\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-G_{k}^{-1}g_{k}

对 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}_{k}$ 处进行泰勒展开

f(\boldsymbol{x}_{k}+\boldsymbol{d})=f(\boldsymbol{x}_{k})+g_{k}^{T}\boldsymbol{d}+\frac{1}{2}\boldsymbol{d}^{T}G_{k}\boldsymbol{d}+o(\left\lVert \boldsymbol{d} \right\rVert ^{2})

此时用二次函数近似求解

\min_{\boldsymbol{d}} q_{k}(\boldsymbol{d})=\min_{\boldsymbol{d}}\left( f(\boldsymbol{x}_{k})+g_{k}^{T}\boldsymbol{d}+\frac{1}{2}\boldsymbol{d}^{T}G_{k}\boldsymbol{d} \right)

得到

\boldsymbol{d}_{k}=-G_{k}^{-1}g_{k}

Theorem (Newton方法局部收敛性)

设 $f(\boldsymbol{x})$ 二次可微， $f(\boldsymbol{x})$ 的Hessian矩阵 $G(\boldsymbol{x})$ 在 $\boldsymbol{x}^{*}$ 的邻域 $\delta$ 内满足Lipschitz条件

\left\lVert G(\boldsymbol{x})-G(\boldsymbol{y}) \right\rVert \leq L\left\lVert \boldsymbol{x}-\boldsymbol{y} \right\rVert

则当

\boldsymbol{x}_{0}

充分接近

f(\boldsymbol{x})

的局部极小点

\boldsymbol{x}^{*}

，且

G(\boldsymbol{x}^{*})

正定，则Newton方法具有二次收敛速度。同时梯度序列

g_{k}

二次收敛到0。

证明
首先由于 $g^{*}=0$ ，此时

\begin{align*} \boldsymbol{x}_{k+1}-\boldsymbol{x}^{*} & =\boldsymbol{x}_{k}-\boldsymbol{x}^{* }-G_{k}^{-1}g_{k} \\ & = G_{k}^{-1}(G_{k}(\boldsymbol{x}_{k}-\boldsymbol{x}^{*})-(g_{k}-g^{*})) \end{align*}

同时注意到

g_{k}-g^{*}=\int _{0}^{1}G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k}))(\boldsymbol{x}_{k}-\boldsymbol{x}^{*}) \, dt

因此

\begin{align*} \left\lVert G_{k}(\boldsymbol{x}_{k}-\boldsymbol{x}^{*})-(g_{k}-g^{*})\right\rVert & =\left\lVert \int _{0}^{1}(G_{k}-G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k})))(\boldsymbol{x}_{k}-\boldsymbol{x}^{*}) \, dt \right\rVert \\ & \leq \int _{0}^{1}\left\lVert G_{k}- G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k})) \right\rVert \left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert \, dt \\ & \leq L\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert ^{2}\int _{0}^{1} t \, dt= \frac{1}{2}L\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert ^{2} \end{align*}

同时

\exists r>0

，当

\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert\leq r

时，有

\left\lVert G(x)^{-1} \right\rVert \leq 2\left\lVert G(\boldsymbol{x}^{*})^{-1} \right\rVert

有界。因此

\{ \boldsymbol{x}_{k} \}

二次收敛到

\boldsymbol{x}^{*}

。

同时

\begin{align*} \left\lVert g_{k+1} \right\rVert & = \left\lVert g_{k+1}-g_{k}-G_{k}\boldsymbol{d}_{k} \right\rVert \\ & = \left\lVert \int _{0}^{1}G(\boldsymbol{x}_{k}+t\boldsymbol{d}_{k})\boldsymbol{d}_{k} \, dt-G_{k}\boldsymbol{d}_{k} \right\rVert \\ & = \int _{0}^{1}\left\lVert G(\boldsymbol{x}_{k}+t\boldsymbol{d}_{k})-G(\boldsymbol{x}_{k}) \right\rVert \left\lVert \boldsymbol{d}_{k} \right\rVert \, dt \\ & = \frac{1}{2}L\left\lVert \boldsymbol{d}_{k} \right\rVert^{2} \leq \frac{1}{2}L\left\lVert G_{k}^{-1} \right\rVert ^{2 }\left\lVert g_{k} \right\rVert ^{2} \end{align*}

1.2 阻尼Newton方法

Definition (阻尼Newton方法)

在Newton方法的基础上，使用一维搜索计算步长

\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k}

1.3 混合方法

Definition (混合方法)

将Newton方法与负梯度方法混合。当Hesse矩阵 $G_{k}$ 奇异或者 $g_{k}$ 与 $\boldsymbol{d}_{k}$ 几乎正交时，采用负梯度方向；在 $G_{k}$ 负定，但 $G_{k}^{-1}$ 存在时，取 $\boldsymbol{d}_{k}=G_{k}^{-1}g_{k}$ 。

1.4 LM方法

Definition (LM方法)

对于 $G_{k}$ 奇异或者不正定的情况，我们求解

(G_{k}+\boldsymbol{v}_{k}I)\boldsymbol{d}_{k}=-g_{k}

当

\boldsymbol{v}_{k}

充分大时，可以保证

G_{k}+\boldsymbol{v}_{k}I

正定。当

\boldsymbol{v}_{k}

较小时，

\boldsymbol{d}_{k}

偏向Newton方法；较大时则偏向负梯度方向。

2. 拟Newton方法

Definition (拟Newton条件)

B_{k+1}\boldsymbol{s}_{k}=\boldsymbol{y}_{k}

解
注意到 $\boldsymbol{x}_{k}$ 靠近 $\boldsymbol{x}_{k+1}$ 时，有

g_{k}-g_{k+1}\approx G_{k+1}(\boldsymbol{x}_{k}-\boldsymbol{x}_{k+1})

因此即得条件。

2.1 SR1方法

Definition (对称秩方法, SR1)

B_{k+1}=B_{k}+ \frac{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}}

解
设

B_{k+1}=B_{k}+ \boldsymbol{v}\boldsymbol{v}^{T}

代入拟Newton方程有

\begin{align*} \boldsymbol{y}_{k} & =B_{k}\boldsymbol{s}_{k}+\boldsymbol{v}\boldsymbol{v}^{T}\boldsymbol{s}_{k} \\ & = B_{k}\boldsymbol{s}_{k}+ ( \boldsymbol{v}^{T}\boldsymbol{s}_{k})\boldsymbol{v} \end{align*}

此时必有

\boldsymbol{v}

与

\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k}

共线。因此设

\boldsymbol{v}=\delta(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})

，此时

\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k}=\delta^{2}((\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})

因此

\delta^{2}= \frac{1}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}}

故

\begin{align*} \boldsymbol{v}\boldsymbol{v}^{T} & =\delta^{2}(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T} \\ & = \frac{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}} \end{align*}

2.2 BFGS公式

Definition (BFGS公式)

\begin{align*} B_{k+1}&=B_{k}+ \frac{y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}- \frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}} \\ H_{k+1}&= H_{k}+\left( 1+\frac{y_{k}^{T}H_{k}y_{k}}{y_{k}^{T}s_{k}} \right) \frac{s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}-\left( \frac{s_{k}y_{k}^{T}H_{k}+H_{k}y_{k}s_{k}^{T}}{y_{k}^{T}s_{k}} \right)\end{align*}

证明
考虑构造

B_{k+1}=B_{k}+ u u^{T}+ v v ^{T}

此时有

y_{k}=B_{k}s_{k}+ uu^{T}s_{k}+ v v^{T}s_{k}

取特解

\begin{align*} u=y_{k},\quad u^{T}s_{k}=1 \\ v=B_{k}s_{k},\quad v^{T}s_{k}=-1 \end{align*}

即得。

2.3 DFP公式

Definition (DFP公式)

\begin{align*} H_{k+1}&=H_{k}+ \frac{s_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}- \frac{H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}} \\ B_{k+1}&= B_{k}+\left( 1+\frac{s_{k}^{T}B_{k}s_{k}}{s_{k}^{T}y_{k}} \right) \frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}-\left( \frac{y_{k}s_{k}^{T}B_{k}+B_{k}s_{k}y_{k}^{T}}{s_{k}^{T}y_{k}} \right)\end{align*}

证明
类似于BFGS方法，只是从 $H_{k+1}$ 方向进行构造。

Theorem ( $B_{k+1}^{DFP}$ 性质)

$B_{k+1}^{DFP}$ 是下面问题的解

\begin{align*} \min\left\lVert W^{-T}(B-B_{k})W^{-1} \right\rVert_{F} \\ s.t. B=B^{T},\quad Bs_{k}=y_{k} \end{align*}

其中

W^{T}W=B

。即满足对称与拟Newton条件中，在Frobenius范数意义下与

B_{k}

距离最近的矩阵。

Theorem ( $B_{k+1}$ 与 $H_{k+1}$ 对称正定性)

若 $H_{k}$ 对称正定，则如果 $s_{k}^{T}y_{k}>0$ ，则DFP构造出的 $H_{k+1}^{DFP}$ 也是对称正定。此时使用精确线搜索或者非精确线搜索Wolfe准则的DFP方法和BFGS方法有 $s_{k}^{T}y_{k}>0$ 。

证明

\begin{align*} x^{T}H_{k+1}^{DFP}x & = x^{T}H_{k}x+ \frac{(x^{T}s_{k})^{2}}{s_{k}^{T}y_{k}}-\frac{(x^{T}H_{k}y_{k})^{2}}{y_{k}^{T}H_{k}y_{k}} \\ & = \frac{(x^{T}H_{k}x)(y_{k}^{T}H_{k}y_{k})-(x^{T}H_{k}y_{k})^{2}}{y_{k}^{T}H_{k}y_{k}}+ \frac{(x^{T}s_{k})^{2}}{s_{k}^{T}y_{k}} \end{align*}

而使用精确线搜索

s_{k}^{T}y_{k}=\alpha_{k}d_{k}^{T}(g_{k+1}-g_{k})=-\alpha_{k}d_{k}^{T}g_{k}=\alpha_{k}g_{k}^{T}H_{k}g_{k}>0

而wolfe准则

s_{k}^{T}y_{k}=\alpha_{k}d_{k}^{T}(g_{k+1}-g_{k})\geq-\alpha_{k}(1-\sigma)d_{k}^{T}g_{k}>0

2.4 Broyden族方法

Definition (Broyden族方法)

\begin{align*}B_{k+1}&=(1-\phi)B_{k+1}^{BFGS}+\phi B_{k+1}^{DFP} \\ &= B_{k+1}^{BFGS}+\phi v_{k}v_{k}^{T}\end{align*}

Theorem ( $B_{k+1}$ 的对称正定性)

若 $B_{k+1}^{BFGS}$ 为对称正定阵，则当 $\phi>0$ 时，Broyden族公式得到 $B_{k+1}$ 也是对称正定阵。

2.5 BB方法

Definition (BB方法)

x_{k+1}=x_{k}-\alpha_{k}g_{k}

3. 共轭梯度方法

3.1 共轭梯度法

Definition (共轭方向)

设 $G$ 是对称正定矩阵，若非零向量组 $\{ d_{0},d_{1},\dots,d_{n} \}$ 满足

d_{i}^{T}Gd_{j}=0,\quad i\neq j

则称非零向量组是矩阵

G

的共轭方向。

Theorem (共轭方向线性无关性)

共轭向量组中的向量必然线性无关。

证明
定义内积

\langle u,v \rangle_{A}=u^{T}Av

若共轭向量组向量线性相关，则设

v=\sum_{i = 1}^{n} c_{i}d_{i}=0

此时

\begin{align*} \langle v,v \rangle _{A} & =\left\langle \sum_{i = 1}^{n} c_{i}d_{i},\sum_{i = 1}^{n} c_{i}d_{i} \right\rangle_{A} \\ & = \sum_{i = 1}^{n} c_{i}^{2}\langle d_{i},d_{i} \rangle _{A}=0 \end{align*}

此时有且仅有

c_{i}=0, i=1,\dots,n

。故证毕。

Theorem (共轭迭代定理)

对于正定二次函数，从任意初始点出发，依次沿共轭方向做精确线搜索，最多迭代n步就可以得到极小点。

证明
易知由精确线搜索 $g_{k+1}^{T}d_{k}=0$ 有

\alpha_{k}=- \frac{d_{k}^{T}g_{k}}{d_{k}^{T}Gd_{k}}=-\frac{\langle d_{k},g_{k} \rangle }{\langle d_{k},d_{k} \rangle _{G}}

由于共轭方向线性无关，因此构成一组基底。此时

x^{*}-x_{0}=\beta_{0}d_{0}+\dots+\beta_{n-1}d_{n-1}

两边与

d_{k}

做内积有

\beta_{k}= \frac{\langle d_{k}, x^{*}-x_{0}\rangle_{G} }{\langle d_{k},d_{k} \rangle _{G}}

注意到

\langle d_{k},x_{k}-x_{0} \rangle _{G}=0

因此

\begin{align*} -\langle d_{k},g_{k} \rangle & =\langle d_{k},(g(x^{*})-g_{k}) \rangle \\ & =\langle d_{k},G(x^{*}-x_{k})\rangle \\ & = \langle d_{k},x^{*}-x_{k} \rangle _{G} \\ & = \langle d_{k},x^{*}-x_{0} \rangle _{G} \end{align*}

故证毕。

Theorem (子空间扩展定理)

设 $f(x)=\frac{1}{2}x^{T}Gx-b^{T}x$ ， $G$ 为正定矩阵， $d_{0},\dots,d_{n-1}$ 为共轭方向，此时

g_{k}^{T}d_{j}=0,\quad j=0,1,\dots,k-1

且

x_{k}

是

f(x)

在

\{ x\mid x=x_{0}+span\{ d_{0},d_{1},\dots,d_{k-1} \} \}

上的最小点。

证明
类似的，注意到

\begin{align*} -\langle d_{j},g_{k} \rangle & =\langle d_{j},G(x^{*}-x_{k}) \rangle \\ & =\langle d_{j},x^{*}-x_{k} \rangle _{G } \\ & = \left\langle d_{j},\sum_{i = k+1}^{n} \alpha_{i}d_{i} \right\rangle _{G} \end{align*}

故证毕。

Corollary (凸优化最优化条件)

对于凸函数，若一点的梯度与所有可行方向正交，则该点为可行集的最小点。

由凸函数，有

f(x)-f(x^{*})\geq g(x^{*})(x-x^{*})

故证毕。

3.2 线性共轭梯度法

Definition (线性共轭梯度法)

对于正定二次函数，取迭代方向为

d_{k}=-g_{k}+\beta_{k-1}d_{k-1}

其中取

d_{0}=-g_{0}

，且

\beta_{k-1}= \frac{g_{k}^{T}g_{k}}{g_{k-1}^{T}g_{k-1}}

此时

\{ d_{i} \}

为一组共轭梯度，且有

g_{k}^{T}g_{i}=0,\quad i=1,\dots,k-1

证明
我们使用数学归纳法，当 $k=1$ 时，由于 $g_{1}^{T}d_{0}=0$ ，显然有 $g_{1}^{T}g_{0}=0$ 。而注意到

\alpha_{0}Gd_{0}=G(x_{1}-x_{0})=g_{1}-g_{0}

因此

\begin{align*} \alpha_{0} d_{1}^{T}Gd_{0} & =(-g_{1}+\beta_{0}d_{0})^{T}(g_{1}-g_{0}) \\ & = -g_{1}^{T}g_{1}-\beta_{0}d_{0}^{T}g_{0} \\ & = -g_{1}^{T}g_{1}+\beta_{0}g_{0}^{T}g_{0}=0 \end{align*}

满足。

此时假设 $d_{0},d_{1},\dots,d_{k-1}$ 都是 $G$ -共轭，且 $g_{i}^{T}g_{j}=0$ ， $0\leq i,j<k,i\neq j$ 。首先注意到

g_{k}=g_{k-1}+\alpha_{k-1}Gd_{k-1}

由归纳假设知

g_{k}^{T}g_{i}=0

，

i=0,\dots,k-2

。而对于

g_{k-1}

，有

g_{k-1}=-d_{k-1}+\beta _{k-2}d_{k-2}

显然

g_{k}^{T}d_{k-2}=0

，而由精确线搜索

g_{k}^{T}d_{k-1}=0

，因此

g_{k}^{T}g_{k-1}=0

，进而

g_{k}^{T}g_{i}=0,\quad i=0,\dots,k-1

此时

\begin{align*} \alpha_{k-1}d_{k}^{T}Gd_{k-1} & = (-g_{k}+\beta_{k-1}d_{k-1})^{T}(g_{k}-g_{k-1}) \\ & = -g_{k}^{T}g_{k}-\beta_{k-1}(-g_{k-1}+\beta_{k-2}d_{k-2})^{T}g_{k-1} \\ & = -g_{k}^{T}g_{k}+\beta_{k-1}g_{k-1}^{T}g_{k-1}=0 \end{align*}

成立。故证毕。

3.3 非线性共轭梯度法

Definition (FR公式)

\beta_{k-1}^{FR}=\frac{g_{k}^{T}g_{k}}{g_{k-1}^{T}g_{k-1}}

Theorem (下降方向保证)

若FR方法步长由强Wolfe准则得到，且 $\sigma \in\left( 0, \frac{1}{2} \right)$ ，则迭代方向 $d_{k}$ 满足

-\frac{1}{1-\sigma}\leq \frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert ^{2}}\leq \frac{2\sigma-1}{1-\sigma}

从而

d_{k}

是下降方向。

证明
考虑数学归纳法，当 $k=0$ 时， $d_{0}=-g_{0}$ ，此时

\frac{g_{0}^{T}d_{0}}{\left\lVert g_{0} \right\rVert ^{2}}=-1

成立。考虑

k-1

均成立，此时

\begin{align*} \frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert ^{2}} & =-1+ \beta_{k-1} \frac{g_{k}^{T}d_{k-1}}{\left\lVert g_{k} \right\rVert ^{2}} \\ & = -1 + \frac{g_{k}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert^{2} } \end{align*}

一方面

\frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert^{2} }\geq-1+ \frac{\sigma g_{k-1}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert ^{2}}\geq-1-\frac{\sigma}{1-\sigma}=-\frac{1}{1-\sigma}

另方面

\frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert^{2} }\leq-1- \frac{\sigma g_{k-1}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert ^{2}}\leq-1+\frac{\sigma}{1-\sigma}=\frac{2\sigma-1}{1-\sigma}

故证毕。

Definition (PRP方法)

\beta^{PRP}_{k}=\frac{g_{k+1}^{T}(g_{k+1}-g_{k})}{g_{k}^{T}g_{k}}

Definition (共轭下降方法)

\beta_{k}=-\frac{g_{k+1}^{T}g_{k+1}}{d_{k}^{T}g_{k}}

Definition (DY方法)

\beta_{k}=-\frac{g_{k}^{T}g_{k}}{d_{k}^{T}(g_{k+1}-g_{k})}

Theorem (正定二次函数Broyden族性质)

对于正定二次函数，采用精确线搜索的Broyden族方法，有

\begin{align*} H_{k}y_{i} &= s_{i}\\ d_{k}^{T}Gd_{i}&=0\end{align*}

证明
仍然考虑数学归纳法。由Broyden族方法定义，迭代方向为

d_{k}=-H_{k}g_{k}

当

k=1

时，

H_{0}y_{0}=s_{0}

，同时

\begin{align*} d_{1}^{T}Gd_{0} & = -\frac{1}{\alpha_{0}} (H_{1}g_{1})^{T}(Gs_{0}) \\ & =-\frac{1}{\alpha_{0}}(H_{1}g_{1})^{T}y_{0} \\ & =-g_{1}^{T}d_{0}=0 \end{align*}

此时对于

k-1

均成立，此时

H_{k}y_{i}=H_{k-1}y_{i}+ \frac{s_{k-1}s_{k-1}^{T}}{s_{k-1}^{T}y_{k-1}}y_{i}- \frac{H_{k-1}y_{k-1}y_{k-1}^{T}H_{k-1}}{y_{k-1}^{T}Hy_{k-1}}y_{i}+\varphi v_{k-1}v_{k-1}^{T}y_{i}

注意到

\begin{align*} & s_{k-1}^{T}y_{i}=s_{k-1}^{T}Gs_{i} =0 \\ & y_{k-1}^{T}H_{k-1}y_{i}=y_{k-1}^{T}s_{i}=s_{k-1}^{T}Gs_{i}=0 \\ & v_{k-1}^{T}y_{i}=(y_{k-1}^{T}H_{k-1}y_{k-1})^{1/2}\left( \frac{s_{k-1}}{s_{k-1}^{T}y_{k-1}}-\frac{H_{k-1}y_{k-1}}{y_{k-1}^{T}H_{k-1}y_{k-1}} \right)^{T}y_{i}=0 \end{align*}

同时

\begin{align*} d_{k}^{T}Gd_{i} & = -\frac{1}{\alpha_{i}}(H_{k}g_{k})^{T}y_{i} \\ & =-\frac{1}{\alpha_{i}}g_{k}^{T}s_{i} \\ & =-g_{k}^{T}d_{i} \\ & =-(g_{i+1}+y_{i+1}+\dots+y_{k-1})^{T}d_{i} \\ & =0 \end{align*}

04无约束优化-二阶方法

ON THIS PAGE