04无约束优化-二阶方法

Lingfeng2024-10-10

04无约束优化-二阶方法

1. Newton方法

1.1 基本Newton方法

Definition (基本Newton方法)

对在处进行泰勒展开

此时用二次函数近似求解

得到

Theorem (Newton方法局部收敛性)

设二次可微，的Hessian矩阵在的邻域内满足Lipschitz条件

则当充分接近的局部极小点，且正定，则Newton方法具有二次收敛速度。同时梯度序列二次收敛到0。

证明
首先由于，此时

同时注意到

因此

同时，当时，有

有界。因此二次收敛到。

同时

1.2 阻尼Newton方法

Definition (阻尼Newton方法)

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

1.3 混合方法

Definition (混合方法)

将Newton方法与负梯度方法混合。当Hesse矩阵奇异或者与几乎正交时，采用负梯度方向；在负定，但存在时，取。

1.4 LM方法

Definition (LM方法)

对于奇异或者不正定的情况，我们求解

当充分大时，可以保证正定。当较小时，偏向Newton方法；较大时则偏向负梯度方向。

2. 拟Newton方法

Definition (拟Newton条件)

解
注意到靠近时，有

因此即得条件。

2.1 SR1方法

Definition (对称秩方法, SR1)

解
设

代入拟Newton方程有

此时必有与共线。因此设，此时

因此

故

2.2 BFGS公式

Definition (BFGS公式)

证明
考虑构造

此时有

取特解

即得。

2.3 DFP公式

Definition (DFP公式)

证明
类似于BFGS方法，只是从方向进行构造。

Theorem (性质)

是下面问题的解

其中。即满足对称与拟Newton条件中，在Frobenius范数意义下与距离最近的矩阵。

Theorem (与对称正定性)

若对称正定，则如果，则DFP构造出的也是对称正定。此时使用精确线搜索或者非精确线搜索Wolfe准则的DFP方法和BFGS方法有。

证明

而使用精确线搜索

而wolfe准则

2.4 Broyden族方法

Definition (Broyden族方法)

Theorem (的对称正定性)

若为对称正定阵，则当时，Broyden族公式得到也是对称正定阵。

2.5 BB方法

Definition (BB方法)

3. 共轭梯度方法

3.1 共轭梯度法

Definition (共轭方向)

设是对称正定矩阵，若非零向量组满足

则称非零向量组是矩阵的共轭方向。

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

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

证明
定义内积

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

此时

此时有且仅有。故证毕。

Theorem (共轭迭代定理)

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

证明
易知由精确线搜索有

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

两边与做内积有

注意到

因此

故证毕。

Theorem (子空间扩展定理)

设，为正定矩阵，为共轭方向，此时

且是在上的最小点。

证明
类似的，注意到

故证毕。

Corollary (凸优化最优化条件)

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

由凸函数，有

故证毕。

3.2 线性共轭梯度法

Definition (线性共轭梯度法)

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

其中取，且

此时为一组共轭梯度，且有

证明
我们使用数学归纳法，当时，由于，显然有。而注意到

因此

满足。

此时假设都是-共轭，且，。首先注意到

由归纳假设知，。而对于，有

显然，而由精确线搜索，因此，进而

此时

成立。故证毕。

3.3 非线性共轭梯度法

Definition (FR公式)

Theorem (下降方向保证)

若FR方法步长由强Wolfe准则得到，且，则迭代方向满足

从而是下降方向。

证明
考虑数学归纳法，当时，，此时

成立。考虑均成立，此时

一方面

另方面

故证毕。

Definition (PRP方法)

Definition (共轭下降方法)

Definition (DY方法)

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

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

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

当时，，同时

此时对于均成立，此时

注意到

同时

04无约束优化-二阶方法

ON THIS PAGE