下载:
-
解极小化问题min{f(x)| x ∈
$\mathbb{R} $ n}的迭代法有多种，其中共轭梯度法由于无须用到▽2f(x)等n阶矩阵数据，存储需求少而特别适合大规模优化问题[1-18]. 传统共轭梯度法的迭代格式为：其中：dk为搜索方向，αk为步长因子，βk为参数，gk=▽f(xk)，sk= xk+1- xk. 不同的βk参数公式对应不同的共轭梯度法. 著名的PRP，HS，LS，FR，DY，CD方法的参数公式如下：
其中：yk-1= gk- gk-1，‖·‖为欧氏范数. 基于βk≥0在某些类型共轭梯度法收敛性分析中的重要性，文献[5-14]均对βk采取相应的非负修正策略，如文献[5]对βkPRP截值得到βkPRP+=max{βkPRP，0}≥0；文献[7-8]则从βkPRP与βkFR，βkHS与βkDY，βkLS与βkCD凸组合的方式，得到βkPRP，βkHS，βkLS的非负修正公式如下：
其中
相应的WYL，MHS，MLS方法都具有较好的收敛性.
类似地，βkPRP，βkHS，βkLS也可修正为：
其中：
这一修改方式能确保βk≥0，但却无法满足充分下降条件：∃c∈(0，1)，使
然而某些类型共轭梯度法的收敛性依赖于充分下降条件，因此文献[11]定理1只得将“满足充分下降条件”作为预设前提. 事实上VPRP，VHS，VLS方法不满足充分下降性，其全局收敛性仍无法保证.
受文献[9-10, 16-17]充分下降性策略的启发，我们修改(3)式的分母，得到
其中常数μ＞2. 我们将讨论(1)，(2)式迭代法的收敛性，其中参数βk取自(5)，(6)或(7)式，步长因子αk考虑采用经典的weak Wolfe-Powell(WWP)线搜索[2]及文献[18]针对BFGS和PRP方法设计的modified weak Wolfe-Powell(MWWP)线搜索.
记参数为δ，σ的WWP线搜索条件为WWP(δ，σ)条件：
其中：δ∈(0，
$\frac{1}{2}$ )，σ∈(δ，1).记参数为δ1，δ，σ的MWWP线搜索条件为MWWP(δ1，δ，σ)条件：
其中：δ∈(0，
$\frac{1}{2}$ )，δ1∈(0，δ)，σ∈(δ，1).将βkV1，βkV2，βkV3统称为βkV，对应的算法V1，V2和V3也统称为算法V.
全文HTML
-
算法 V-WWP
步骤 1 设定初值x1∈
$\mathbb{R} $ n，μ＞2，0＜δ1＜δ＜σ＜1，ε＞0，d1=- g1，k=1. 若‖ gk‖≤ε，则停止.步骤 2 计算αk满足WWP(δ，σ)条件(8)和(9)式.
步骤 3 由(1)式计算xk+1. 若‖ gk+1‖≤ε，则停止.
步骤 4 由(5)，(6)或(7)式计算βk+1，由(2)式计算dk+1.
步骤 5 置k=k+1，转步骤2.
在算法V-WWP框架中，将步骤2改为计算αk满足MWWP(δ1，δ，σ)条件(10)和(11)式，则得到V-MWWP算法.
定理 1 算法V-WWP生成的序列βk，gk，dk满足0≤βk和充分下降条件(4).
证 ∀k≥2，由-‖ gk‖‖ gk-1‖≤ gkT gk-1≤‖ gk‖‖ gk-1‖，可得
又有
从而，可得0≤βkV1，0≤βkV2，0≤βkV3. 根据算法V-WWP步骤(4)βk的取法，可得0≤βk.
取c=1-
$\frac{2}{\mu }$ ，则c∈(0，1). 当k=1时，显然对k≥2情形，若gkT dk-1=0，将gkT与(2)式两端作内积，可得
若gkTdk-1≠0，则由(12)-(15)式，可得
从而可得
进一步可得
定理1得证.
-
证明算法的收敛性需要用到以下假设和引理.
假设：
(i) f(x)在水平集Ω={ x ∈
$\mathbb{R}$ n|f(x)≤f(x1)}下方有界，Ω有界.(ii) ▽f(x)在Ω的某邻域N上Lipschitz连续，即存在常数L＞0，使得
引理 1[3, 6] 考虑满足如下条件的任一共轭梯度法(1)-(2)：
(a) βk≥0.
(b) 搜索方向满足充分下降条件(4).
(c) 以下Zoutendijk条件成立：
(d) βk满足性质(*)：设0＜r≤‖ gk‖≤ r，存在常数b＞1和λ＞0，对∀k≥2有
若假设(i)和(ii)成立，则该迭代全局收敛.
以下算法收敛性分析中均假设‖ gk‖≠0，否则算法已得到f(x)的稳定点而终止.
-
定理 2 若假设(i)和(ii)成立，则算法V-WWP生成的序列gk，dk满足Zoutendijk条件(17).
证 由(8)式和定理1，知fk+1≤fk+δαkgkTdk＜fk，递推可得fk+1＜fk＜…＜f1. 再由假设(i)可知，序列{fk}单调有界从而收敛，即
$\mathop {\lim }\limits_{k \to \infty } {f_{k + 1}}$ 为常数.由(9)式和假设(ii)，可得
从而可得
由(8)，(18)式可得
(19) 式两端对k=1，2，…求和，可得
从而可知(17)式成立，定理2得证.
定理 3 若假设(i)和(ii)成立，βk，gk，dk为算法V-WWP生成的序列，则βk满足性质(*).
证 由(9)式和定理1，可得
从而可得
根据算法V-WWP步骤(4)βk的取法，可知
假设∀k≥1，0＜r≤‖ gk‖≤ r，其中r和r为常数. 取
则由σ∈(0，1)，c=1-
$\frac{2}{\mu }$ ∈(0，1)，知b＞1，λ＞0.由(12)和(20)式，可得
设‖ sk-1‖≤λ，则由(16)，(20)式及
可得
定理3得证.
由定理1-3以及引理1，可得如下定理4.
定理 4 若假设(i)和(ii)成立，gk为算法V-WWP生成的序列，则
$\mathop {\lim \;\inf }\limits_{k \to \infty } \left\| {{\mathit{\boldsymbol{g}}_k}} \right\| = 0$ .定理 5 若αk满足MWWP(δ1，δ，σ)条件，则αk也满足WWP(δ-δ1，σ)条件.
证 设αk由MWWP(δ1，δ，σ)线搜索产生，其中δ∈(0，
$\frac{1}{2}$ )，δ1∈(0，δ)，σ∈(δ，1)，则由(10)和(11)式，可得显然δ-δ1∈ (0，
$\frac{1}{2}$ )，由(21)和(22)式，可知αk也满足参数为δ-δ1，σ的WWP线搜索条件. 定理5得证.由定理5，类似定理4的证明过程，可得算法V-MWWP全局收敛，即如下定理6成立.
定理 6 若假设(i)和(ii)成立，gk为算法V-MWWP生成的序列，则
$\mathop {\lim \;\inf }\limits_{k \to \infty } \left\| {{\mathit{\boldsymbol{g}}_k}} \right\| = 0$ .
-
利用文献[19]的部分测试问题，维数分别取1 000，5 000，10 000，对算法PRP(采用MWWP搜索)和算法V-MWWP进行数值试验. 试验环境为：ThinkPad E580，Intel(R) Core(TM) i5-8250U CPU@1.60GHz，RAM 8.00GB，Windows 10，Matlab R2016a. 算法参数δ1=0.05，δ=0.1，σ=0.9，μ=5.1，ε=10-6. 终止条件为‖ gk‖≤10-6或迭代次数N ≥1 000. 计算结果见表 1，其中t表示算法所耗CPU时间，NaN表示算法终止时未满足‖ gk‖≤ε.
应用文献[20]的技术得到算法PRP与算法V关于迭代次数和CPU时间比较的效能图(图 1和图 2). 可见算法V对这些测试问题的数值表现比算法PRP更好些.