一类新的锥模型信赖域自适应算法

赵 绚,朱 帅

(1.运城师范高等专科学校 数学与计算机系,山西 运城 044000;2.山西大同大学 数学与统计学院,山西 大同 037009)

考虑无约束优化问题

(1)

其中，f:Rn→R二次连续可微.

求解此问题的大部分新算法是采用二次模型逼近f(x),但是对于一些非二次形态较强、曲率变化剧烈的函数,效果不是很理想.为此,Dnvidon[1]于1980年提出了锥模型,锥模型是二次模型的推广.Di和Sun[2]给出了锥模型信赖域子问题的最优性条件.文献[3]和[4]提出了基于锥模型的拟牛顿信赖域算法.

为了克服原目标函数在1-bTd>0的附近可能无界的情况,Ni[5]取消了对水平向量b的限制,对锥模型信赖域的子问题考虑了更为一般的情况,提出了一种新锥模型信赖域子问题

(2)

文献[6]中定义了关于ρk的R-函数以变化的速率来调节信赖域半径的大小,充分利用了ρk的信息,使信赖域半径的调节取决于问题本身,更具客观性.本文将R-函数以变化的速率来调节信赖域半径的大小的自适应和非单调技术[7-8]相结合,提出了一种基于锥模型的非单调自适应信赖域算法.

1 算法

定义1[6]Rμ(t)定义在(-∞,+∞)上,参数μ∈(0,1),Rμ(t)是一个R-函数,当且仅当它满足

(i)Rμ(t)在(-∞,+∞)上非减;

(iii)Rμ(t)≤1-γ1,(∀t<μ,γ1∈(0,1-ω)是一个常数);

(iv)Rμ(μ)=1+γ2,(γ2∈(0,+∞)是一个常数);

对于自动调节信赖域半径的R-函数,本文定义为[6]

算法1

step0 给定x0∈Rn,对称阵

step2 用折线法[9]求解子问题(2)得近似解dk.

step4 若ρk≥μ,令xk+1=xk+dk;否则取λk为

(3)

令xk+1=xk+λkdk.

step6 令k∶=k+1,更新bk[3]和Bk[3]

若ρk≥μ,令Mk+1=M;若μ<ρk<1,Mk+1=M+1.转step1.

2 算法的收敛性

2.1 本文假设

H1 水平集L(x0)={x|f(x)≤f(x0),x∈Rn}有界,且{xk}∈L(x0);

H2 数列{fk}有下界；

H3 ∇f(x)在Rn上一致连续；

2.2 全局收敛性

引理1[8]若假设H2成立，则数列{fl(k)}非增且收敛.

(4)

(5)

取ε=τδ(1-μ)/2,其中0<μ<1,τ>0,则

(6)

令

m=min{Δ1,Z1,ε0δ,ωδ,ωδZ1,τδω(1-μ)/2},

下面分两种情况证明(4)式.

(7)

(8)

(9)

f(xk+dk)-fl(k)>-μpredk.

(10)

由(6)式知

(11)

(12)

从而有……