一个非单调BFGS信赖域算法

A Nonmonotone BFGS-Trust-Region Algorithm

关键词:  非单调  BFGS校正  全局收敛性  信赖域算法

Key words:  nonmonotone  BFGS update  global convergence  trustregion algorithm

摘要:

将新的BFGS校正公式B_k+1=B_k+(y_k^*y_k^*T)/(s_k^Ty_k^*)-(B_ks_ks_k^TB_k)/(s_kTB_ks_k),与文献[16]中的算法相结合给出一个非单调BFGS校正的信赖域算法.该算法在假设条件:(i)存在常数c₁,c₂,c₃,使得对所有的Δ_k>0,g_k∈Rⁿ,对称正定阵B_k∈R^n×n,有pred_k ≥ c₁||g_k||min{Δ_k,c₂||g_k||,c₃||g_k||/||B_k||};(ii)若||B_k^-1|| ≤ Δ_k,则d_k=-B_k^-1g_k;(iii)f(x)是二次连续可微函数,▽²f(x_k)是Lipschitz连续,水平集ϕ(x₀)有界下,具有全局收敛性和Q-二次收敛性.

Abstract:

A new nonmonotone BFGS-trust-region algorithm is proposed by combining the BFGS update B_k+1=B_k+ (y_k^*y_k^*T)/ (s_k^Ty_k^*)- (B_ks_ks_k^TB_k)/ (s_k^TB_ks_k), with the algorithm given in references[16].The global and Q-quadratic convergences of the proposed algorithm are also proved under the following conditions: (i)there are constants c₁, c₂, c₃ such that pred_k ≥ c₁‖g_k‖ min{Δ_k, c₂‖g_k‖, c₃‖g_k‖/‖B_k‖}for Δ_k>0, g_k∈Rⁿ and some symmetry positive definite matrix B_k∈R^n×n; (ii)d_k=-B_k^-1g_k if ‖B_k^-1g_k‖ ≤ Δ_k and (iii) f (x) is a second-order continuously differentiable function, ▽²f (x) is Lipschitz continuous and the level set ϕ (x₀) is bounded.