DY共轭梯度法
时间：2022-12-29 03:00:00
DY共轭梯度法
1、简介
2、DY共轭梯度法的框架和假设
3、DY共轭梯度法的收敛性证明
4、对 DY 进一步讨论共轭梯度法
5.总结参考文献
1、简介
?? 1952 年，Hestense 和 Stiefel 求解线性方程组 AX=b 共轭梯度法，我们称之为线性共轭梯度法。1964 年，Fletcher 和 Reeves 将共轭梯度法应用于解决二次函数的局部极小问题，通常被认为是解决无约束优化问题的非线性共轭梯度法的开始。共轭梯度法具有存储容量小的特点，适用于解决大型无约束、无约束优化问题。
?? 无约束优化问题
min x ∈ R n f ( x ) (1) \min_{x\in\mathbb{R}^n}~f(x)\tag{1} x∈Rnminf(x)(1)
其中 f ( x ) : R n → R ~f(x):\mathbb{R}^n\rightarrow\mathbb{R}~ f(x):Rn→R梯度函数记为连续可微函数 g ( x ) : R → R n ~g(x):\mathbb{R}\rightarrow\mathbb{R}^n~ g(x):R→Rn .。其一般的迭代格式为:
x k + 1 = x k + α k d k (2) x_{k+1}=x_k+\alpha_k d_k\tag{2} xk+1=xk+αkdk(2),
d k = { − g k , k = 1 , − g k + β k d k , k ≥ 2 , (3) d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{3} dk={
−gk,−gk+βkdk,k=1,k≥2,(3)
其中 g k ~g_k~ gk 是迭代点 x k ~x_k~ xk 处的梯度， α k ~\alpha_k~ αk 是搜素步长， d k ~d_k~ dk 是搜素方向， β k ~\beta_k~ βk 为共轭参数。
不同的参数 β k ~\beta_k~ βk 决定不同的共轭梯度法，本文想说明的是 D Y ~DY~ DY 算法，其他算法便不在此处列出。
β k D Y = ∥ g k ∥ 2 d k − 1 ( g k − g k − 1 ) (4) \beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}(g_k-g_{k-1})}\tag{4} βkDY=dk−1(gk−gk−1)∥gk∥2(4)
决定步长 α k ~\alpha_k~ αk 的线搜索此处仅给出两种
标准 Wolfe 线搜索
f ( x k + α k d k ) ≤ f ( x k ) + ρ α k d k (5) f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{5} f(xk+αkdk)≤f(xk)+ραkdk(5)
g ( x k + α k d k ) T d k ≥ σ g k d k (6) g(x_k+\alpha_k d_k)^Td_k\ge\sigma g_k d_k\tag{6} g(xk+αkdk)Tdk≥σgkdk(6)
强 Wolfe 线搜索
f ( x k + α k d k ) ≤ f ( x k ) + ρ α k d k (7) f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{7} f(xk+αkdk)≤f(xk)+ραkdk(7)
∣ g ( x k + α k d k ) T d k ∣ ≤ − σ g k d k (8) \vert g(x_k+\alpha_k d_k)^Td_k\vert\le-\sigma g_k d_k\tag{8} ∣g(xk+αkdk)Tdk∣≤−σgkdk(8)
其中 0 < ρ < σ < 1 ~0<\rho<\sigma<1~ 0<ρ<σ<1 .
2、DY 共轭梯度法的框架和假定
基于公式(2),(3),(4)和标准 Wolfe 线搜索 (5) 和 (6)，给出 DY 共轭梯度法的算法框架.
DY 共轭梯度法
步1：给定初始点 x 1 ∈ R n ~x_1\in\mathbb{R}^n~ x1∈Rn ， ∀ ϵ > 0 \forall~\epsilon>0 ∀ ϵ>0， 0 < ρ < σ < 1 ~0<\rho<\sigma<1~ 0<ρ<σ<1 ，令 d 1 = − g 1 ~d_1=-g_1 d1=−g1， k : = 1 ~k:=1~ k:=1 ，若 g 1 < ϵ ~g_1<\epsilon~ g1<ϵ ，终止.
步2：由标准 Wolfe 线搜索 (5) 和 (6) 计算步长因子 α k ~\alpha_k~ αk .
步3：迭代计算 x k + 1 = x k + α k d k ~x_{k+1}=x_k+\alpha_k d_k~ xk+1=xk+αkdk ，
