求解不定信赖域子问题的改进休恩三阶方法

郭栋栋

(山西应用科技学院 基础教学部，山西 太原 030000)

一般的R-K法的形式为

(1)

R-K法的本质是利用Taylor级数方法，且减少了对原复杂函数进行解析求导的过程.R-K类算法求解无约束最优化问题[1-2]的本质就是利用了R-K法构造一条能够代替最优曲线[3]的折线从而解信赖域子问题.

首次R-K类[4]算法求解信赖域子问题是于海波[5]提出的一种变步长的休恩算法CHML.随后又提出了改进的显示欧拉、隐式欧拉和平均欧拉[6-7]算法.2017年李琳俊[8]提出不定的ICHML算法.本文在张春霞和王希云提出的改进休恩三阶方法[9]的基础上，提出了一种不定的改进休恩三阶[10]算法.本文提出的新算法提高了在Hessian阵不定的情况下改进休恩三阶算法的适用性，从而使得改进休恩三阶算法变得系统完整.

1 对称正定矩阵Gk的构造

任取一对称矩阵Bk，一定有排列矩阵P能够得到PΤBkP=LDkLΤ，设P=I，即Bk=LDkLΤ,设λi是Dk的特征值，vi是Dk的特征向量，令vk=(v1,v2,…,vn)Τ，下面分两种情形来构造Gk.

(i)当λi>0，i=1,2,…,n时，

(ii)当∃i，s.t.λi≤0时，

2 步长

改进算法修正条件为

(2)

改进后步长简化形式为

(3)

(4)

其中，n=0,1,2,…，N-1 ,δ0=-Gg，ε称为限制步长.

3 算法描述

步1 给定梯度g,G,半径Δ.取n∶=0.

具体形式见公式(3),转步3.

步4 令

停止计算，否则令n∶=1转步4.

步5 令

的具体形式见公式(3).转步5.

步6 令

停止计算，否则令n∶=n+1转步4.

4 不定的改进休恩三阶折线路径的性质分析

证明(i)当n=1时，

因为

(ii)假设1

若n=k+1，有

又由

得到

于是

故

即

证毕.

定理设矩阵G是对称正定的，且有下式成立，

其中，

记休恩三阶折线T=[P0,P1,…，PN]为δ(τ)，具体形式如下

则δ(τ)满足如下两个要求，

(ii)q[δ(τ)]为单调非减函数.

证明(i) 当τ∈[β0，β1]，即τ∈[0，h0]时

则

由公式(3)

对∀τ∈[βi，βi-1]，即(τ-βi)∈(0,hi],n=0,1,2,…，N-1时

则

由公式(4)式可知

(ii)当τ∈[β0,β1]，即τ∈(0,h0]时

所以,q[δ(τ)]在区间[β0，β1]上为单调非减函数.

对∀τ∈[βi，βi-1]，即(τ-βi)∈(0,hi]，n=0,1,2,…，N-1时，

故q[δ(τ)]在区间[βi，βi+1]，n=0,1,2,…，N-1上都为单调非减函数.证毕.

5 数值结果

用不定的改进休恩三阶算法与原不定算法做对比，q表示测试函数的最优解值.

文中用到的测试函数如下.

Function 1

Function 2

表1 测试函数1的数值结果