求解不定信賴域子問題的改進休恩三階方法

郭棟棟

(山西應用科技學院 基礎教學部，山西 太原 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時

則

由公……