無約束優(yōu)化問題的精細修正牛頓算法分析

摘要：無約束優(yōu)化問題是人們在探討優(yōu)化問題的典型和基礎(chǔ)。為了解決這一問題，這一問題被提出時，牛頓通過研究確定了一種快速收斂的方式，解決了最速下降法存在的收斂性局限問題。但與此同時，牛頓算法不能解決一般非凸函數(shù)求解中迭代點矩陣正定不定的問題。最速下降法和牛頓算法可以分別解決迭代點矩陣負定或半負定、正定的問題。在前人研究的修正牛頓算法的基礎(chǔ)上，筆者提出對最速下降法、牛頓算法及修正牛頓算法的優(yōu)勢進行結(jié)合，從而獲得一種精細修正牛頓算法，用以解決迭代點矩陣正定不定的問題，收效良好，可以進行全局的收斂分析。

關(guān)鍵詞：無約束優(yōu)化問題；牛頓算法；最速下降法；修正牛頓算法

微分方程是微積分學科重要的研究內(nèi)容，微積分奠基人Newton和Leibniz分別在其著作中就有關(guān)微分方程的問題進行過論證，且廣泛應用于多個學科的研究當中。而無約束優(yōu)化問題正式微積分這一學科發(fā)展的結(jié)果，并且廣泛適用于計算機應用的科學之中。在進行無約束有過時，往往為了獲得最優(yōu)解及實現(xiàn)快速收斂，采取多種算法。但是根據(jù)應用算法的不同，其全局性和收斂速度有所區(qū)別。作為微積分的奠基人Newton所提出的牛頓算法已經(jīng)被當今科研人員結(jié)合實際問題進行修正和拓展。本文正是在前人研究的基礎(chǔ)之上進行結(jié)合和優(yōu)化，從而尋求一種全局收斂效果良好的無約束優(yōu)化問題的求解方法。

1 問題的提出

無約束優(yōu)化被認為是最優(yōu)化問題的基礎(chǔ)。在進行無約束優(yōu)化問題的求解過程中，通過使用牛頓法、擬牛頓法、共軛梯度法、最速下降法等算法。對于共軛梯度法而言，它對問題初始值的依賴性比較大，很難獲得全局收斂的最小值。對最速下降法而言，它是一種結(jié)構(gòu)簡單實現(xiàn)容易的算法，能夠較好的實現(xiàn)全局收斂。而根據(jù)理論驗證，這種方法的收斂速度比較慢，通常職能達到局部收斂速度。牛頓法相比較而言，收斂速度更快，所使用的范圍也更廣。雖然牛頓法擁有二階收斂速度，但是迭代點的問題即Hessian矩陣正定不確定始終對其應用有所影響。因此相關(guān)學者也紛紛提出了牛頓法的優(yōu)化，如修正牛頓法。那么本文試圖在已有的修正牛頓法的基礎(chǔ)上，結(jié)合最速下降法和牛頓法的基本原理，提出對型如函數(shù)

minf（x），x∈Rn（1）

其中f：Rn→R下的二次連續(xù)可微函數(shù)的無約束優(yōu)化問題進行求解。其核心就是要將迭代點目標函數(shù)的一階、二階信息充分利用，選取合理的搜索方向，從而建立全局收斂性。

2 精細修正牛頓法的計算方法分析

本文所提出的精細修正牛頓算法是綜合了最速下降法、牛頓法以及修正牛頓法的優(yōu)點獲得的。主要就是為了解決迭代點hessian矩陣正定不確定的問題。那么首先要求根據(jù)迭代點處的目標函數(shù)的一階、二階信息來確定合理的搜索方向。

現(xiàn)在可以假設(shè)函數(shù)（1）的迭代點為xk，那么此時可以獲得該迭代點處目標函數(shù)的梯度函數(shù)為gk=f（xk）。那么結(jié)合hessian矩陣的函數(shù)關(guān)系Gk=2f（xk）.如果gk=f（xk）≠0。那么可以對Gk的矩陣性質(zhì)進行研究。如果Gk為正定矩陣，那么目標函數(shù)f：Rn→R下的二次連續(xù)可微性可知，迭代點xk附近為嚴格的凸函數(shù)。那么此時可以確定搜索方向為dk=-G-1kgk。搜索方向確定為牛頓法方向。

如果Gk為負定或者半負定矩陣時，則根據(jù)目標函數(shù)的連續(xù)可微性質(zhì)得知，迭代點處為凹函數(shù)，那么此時的搜索方向可以確定dk=-gk。也就是最速下降法的搜索方向。

上述兩種都是已知的搜索方向確定。那么如果Gk的矩陣性質(zhì)為不定或者半正定時，我們就需要構(gòu)建新的方式來對當前的矩陣性質(zhì)就行修正，從而獲得可以繼續(xù)進行研究的正定矩陣。根據(jù)迭代點矩陣Gk的自身性質(zhì)，其為實對稱陣，必然存在可逆矩陣Pk使得P-1kGkPk為對角陣。那么根據(jù)矩陣函數(shù)的特征，確定λki為2f（xk）的非零特征值，同樣該值為對角陣上的非零元素，其中i=1，2，…，n，s≤n。

那么該對角陣如下所示：

Q=（qij）=P-1k▽2f（xk）Pk=

[JB（（]λk10…0 0 … 0

0 λk2…0 0 … 0

[KG*2][KG*3]……[KG-1]…[KG*2][KG*3]…[KG-*2]…[KG*2]…

0 0…λk2 0 … 0

0 0…0 0 … 0

[KG*2][KG*3]……[KG-1]…[KG*2][KG*3]…[KG-*2]…[KG*2]…

0 0…0 0…0[JB））]

（2）

（2）如果q-kij=[JB（{]max[JB（{]1-eλki，δ[JB）}]，λki≤0[]λki，λki>0[JB）]

則可以獲得Q-=（q-ijk）那么通過該方法獲得的修正矩陣G-k=P-1kO-Pk（3）就可以成為可處理的正定矩陣。那么此時的搜索方向確定為dk=-G--1kgk

那么根據(jù)上述迭代點xk的搜索方向可以看出，dk始終為迭代點的下降方向，并且滿足WolfePowell線搜索規(guī)則。那么尋找ak滿足下列條件：

[JB（{]f（xk+akdk）≤f（xk）+σ1akgTkdk

gTk+1dk≥σ2gTkdk[JB）]

其中0<σ1<1/2，且1>σ2>σ1，σ1，σ2均為常數(shù)。

基礎(chǔ)上述條件，我們可以得出精細修正牛頓法的在處理無約束優(yōu)化問題時的基本步驟。

①設(shè)定初始點x0Rn，精度ε>0，參數(shù)δ>0，并給定常數(shù)0≤σ1<1/2且1>σ2>σ1，此時k值為0。當‖gk‖≤ε時，即終止運算，求得無約束優(yōu)化問題（1）的解為xk。

②在未達到步驟①的要求時，根據(jù)迭代點處矩陣函數(shù)的正定性質(zhì)，確定搜索方向。若矩陣為正定，則可以確定為牛頓法方向搜索即dk=-G-1kgk，其中Gk=2f（xk）。若確定為負定或者半負定矩陣時，那么此時的搜索方向可以確定為最速下降法dk=-gk。如果矩陣為不定或者半正定時就需要對矩陣進行修正，利用其實對稱陣的性質(zhì)，構(gòu)造正定矩陣G-k=P-1kQ-Pk

③根據(jù)WolfePowell的線性搜索規(guī)則，確定步長ak，并且令xk+1=xk+akdk，k：=k+1，可以獲得‖gk‖≤ε，終止運算并取得最最優(yōu)解。

3 無約束優(yōu)化問題的精細修正牛頓算法的全局收斂性研究

那么在獲得精細修正牛頓算法的一般步驟后，我們就需要對其解決無約束優(yōu)化問題的全局收斂性進行研究。從牛頓算法來看，其具有局部收斂速度快的特征，那么在進行精細修正后，其能夠獲得較好的全局收斂性。筆者將通過以下假設(shè)、引理進行推論和驗證。本文所研究的無約束優(yōu)化問題函數(shù)型為：minf（x），x∈Rn

（1），且目標函數(shù)f：Rn→R

下的二次連續(xù)可微函數(shù)。那么由此可以進行相關(guān)的假設(shè)：首先給出基本假設(shè)1、2。

假設(shè)1 ：目標函數(shù)f：Rn→R是二次連續(xù)可微函數(shù)，那么給定x0∈Rn，水平集F=[JB（{]x0∈Rn|f（x）≤f（x0）[JB）}]

假設(shè)2 假設(shè)水平集F的領(lǐng)域為γ，那么函數(shù)f（x）的梯度函數(shù)g（x）=▽f（x）在領(lǐng)域γ內(nèi)存在常數(shù)m>0使得不等式（4）成立：

對于任意y，z屬于領(lǐng)域γ有‖▽f（y）-▽f（z）‖|≤m‖y-z‖（4）

那么根據(jù)引理1 假設(shè)B∈Rn×n是任意實對稱矩陣，那么矩陣B的特征值可以表示為λ（B）那么λ作為全體對稱矩陣機上的函數(shù)，該概述的任意算子范數(shù)則關(guān)于矩陣B連續(xù)。由此可以得出推論：

當假設(shè)1成立時，可以獲得兩個推論：

推論1矩陣值函數(shù)g：Rn→Rn×n，aij：Rn→R，

g（x）=2fx=（2f[]xixj）n×n△（aij）n×n存在常數(shù)h1使得所有x∈F（F為有界閉集）使得不等式（5）成立：

|aij（x）|

那么矩陣值函數(shù)g的特征值在水平集F上有界。

推論2 矩陣值函數(shù)g-：Rn→Rn×n，a-ij：Rn→R，g-=P-1kQ-Pk，存在常數(shù)h2使得所有x∈F（F為有界閉集）使得不等式（6）成立：

|a-ij（x）|

那么矩陣值函數(shù)g的特征值在水平集F上有界。

根據(jù)矩陣的非零特征值的形態(tài)結(jié)合假設(shè)1、2和引理1可以獲得下列推論

推論3 矩陣特征值序列{λkimin}，{q-kijmin}，存在常數(shù)h1，h2且h1，h2∈（0，+∞）使得任意k值都有不等式（7）成立。

λkimin>h1，q-kijmin>h2其中1≤i≤n（7）

引理2 矩陣gk=（akij），g-k=（a-kij）當p1=<|akij|，p2=maxi≥1，j≤n[DD）]|a-kij|，那么根據(jù)矩陣序列的特征值λki，q-kij可以獲得不等式|λki|≤np1，|q-kij|≤np2.（8）

引理3 根據(jù)精細修正牛頓算法產(chǎn)生的搜索方向序列{dk}，那么則應該存在cos〈dk，-gk〉>η，其中η=min[JB（{]1，（m1[]nh1）n，（m2[]mh2）n[JB）}]>0（9）

具體分析如下：

那么當矩陣為負定或半負定方向時，采用最速下降法，則有cos〈dk，-gk〉=1，當矩陣為正定方向時，則依據(jù)牛頓算法，存在不等式：1[]nh1<1[]λki<1[]m1。那么則有極值gTk（2f（xk）-1）Tgk=gTk（PkQ-1P-1k）Tgk≥min1[]λkingTk（PkEP-1k）Tgk=min1[]λk1n‖gk‖2>（[SX（]m1[]nh1[SX）]）n‖gk‖2

且‖2f（xk）-1‖=‖PkQ-1P-1k‖≤max[JB（{]1[]λki[JB）}]n‖PkEP-1k‖=max[JB（{]1

[]λki[JB）}]n<（m1[]nh1）n

其中設(shè)定E為n×n階的單位矩陣，那么根據(jù)矩陣性質(zhì)cos〈dk，-gk〉=-dTkgk[]‖gk‖‖dk‖，代入dk=2f（xk）則可以獲得cos〈dk，-gk〉=-dTkgk[]‖gk‖‖dx‖≥min[JB（{]1[]λki[JB）}]n‖gk‖2[]‖2f（xk）-1gk‖‖gk‖≥min1[]λkin‖gk‖2[]‖2f（xk）-1‖‖gk‖2>m1[]nh1n[]1[]m1n

同理當矩陣為不定或半正定時，根據(jù)修正結(jié)果獲得的搜索方向dk=-G--1kgk按照上述方法進行論證可知，

cos〈dk，-gk〉=-dTkgk[]‖gk‖‖dk‖>min[JB（{]1[]λki[JB）}]n‖gk‖2[]‖2f（xk）-1gk‖‖gk‖>（m2[]nh2）n。綜合可知，

η=min[JB（{]1，m1[]nh1n，m2[]nh2n[JB）}]>0

引理4根據(jù)精細修正牛頓算法產(chǎn)生的步長序列{ak}，那么當假設(shè)2成立時，結(jié)合矩陣特征，則有不等式ak≥1-2[]L‖dk‖‖gk‖cos〈dk，-gk〉

引理5根據(jù)精細修正牛頓算法產(chǎn)生的迭代點的序列{xk}，且有xk∈水平集F，其中對于任意k均屬于N集合。

引理6 當假設(shè)f為水平集F上的二次連續(xù)可微函數(shù)，那么搜索方向序列{dk}可得到以下兩個結(jié)論，第一，序列{‖gk‖}是水平集F上的有界序列；第二，序列{‖dk‖}是水平集F上的有界序列。

根據(jù)上述推論、引理可獲得定理：

根據(jù)精細修正牛頓算法可獲得迭代點xk序列{xk}，根據(jù)梯度函數(shù)可以獲得對應的梯度函數(shù)序列{gk}，那么目標函數(shù)f：Rn→R是二次連續(xù)可微函數(shù)，那么給

定x0∈Rn，水平集F=[JB（{]x0∈Rn|f（x）≤f（x0）[JB）}]

當水平集F的領(lǐng)域為γ，那么函數(shù)f（x）的梯度函數(shù)g（x）=f（x）在領(lǐng)域γ內(nèi)存在常數(shù)m>0使得不等式成立：

對于任意y，z屬于領(lǐng)域γ有‖▽f（y）-▽f（z）‖≤m‖y-z‖進而根據(jù)極限函數(shù)可知limk→+∞ inf‖gk‖=0

對這一定理進行驗證，現(xiàn)在已知‖dk‖有界，根據(jù)wolfePowell的序列條件，可以獲得下列式子：

f（xk+akdk）≤f（xk）+σ1akgTkdk=f（xk）-σ1ak‖gk‖‖dk‖cos〈dk，-gk〉（10）

對式（10）進行整理可以獲得不等式（11）

σ1ak‖gk‖‖dk‖cos〈dk，-gk〉≤f（xk）-f（xk+akdk）（11）

那么就σ1ak‖gk‖‖dk‖cos〈dk，-gk〉進行如下求和運算：

∑∞k=0σ1ak‖gk‖‖dk‖cos〈dk，-gk〉=limp→∞∑pk=0σ1ak‖gk‖‖dk‖cos〈dk，-gk〉=limp→∞ f（x0）-f（xp+1）<∞，

代入引理3，可獲得limk→+∞ inf‖gk‖=0

如果limk→+∞ inf‖gk‖>0則應存在ε，ε對任意k>0，有‖gk‖≥ε使得limk→+∞ ak‖dk‖=0，而結(jié)合引理5、6，在該假設(shè)條件下limk→+∞ inf‖gk‖=0，與假設(shè)結(jié)果相反。因此可以證明在假設(shè)1、2成立的條件下，存在limk→+∞ inf‖gk‖=0

根據(jù)本文所獲得的定理，通過反設(shè)和推論，結(jié)合相關(guān)的引理，證明本文所得定理具有良好的收斂性。因此根據(jù)cute中提出的十三個標準測試函數(shù)進行述職驗證可知，其在解決無約束優(yōu)化問題函數(shù)上的效果明顯，能夠解決最速下降法全局收斂速度慢的問題。

4 結(jié)論及展望

綜上所述，本文所提出的針對無約束優(yōu)化問題函數(shù)minf（x），x∈Rn（1）其中f：Rn→R下的二次連續(xù)可微函數(shù)的無約束優(yōu)化問題進行求解。其核心就是要將迭代點目標函數(shù)的一階、二階信息充分利用，選取合理的搜索方向，從而建立全局收斂性。在假設(shè)目標函數(shù)f：Rn→R是二次連續(xù)可微函數(shù)，那么給定xo∈Rn，水平集F=[JB（{]x0∈Rn|f（x）≤f（x0）[JB）]且當水平集F的領(lǐng)域為γ，那么函數(shù)f（x）的梯度函數(shù)g（x）=f（x）在領(lǐng)域γ內(nèi)存在常數(shù)m>0使得不等式成立：對于任意y，z屬于領(lǐng)域γ有‖f（y）-f（z）‖≤m‖y-z‖進而根據(jù)極限函數(shù)可知limk→+∞ inf‖gk‖=0。根據(jù)cute中提出的十三個標準測試函數(shù)進行述職驗證可知，其在解決無約束優(yōu)化問題函數(shù)上的效果明顯，能夠解決最速下降法全局收斂速度慢的問題。根據(jù)無約束優(yōu)化問題的具體推廣，該種方法適用于生活、生產(chǎn)的多個領(lǐng)域。當然如果將這一算法進行推廣和深度優(yōu)化，還需要進行更多的研究、試驗加以論證。

參考文獻：

[1]郭小蘭.牛頓法求解無約束優(yōu)化問題[J].數(shù)字化用戶，2017，23（30）：2629.

[2楊海麗.非線性最優(yōu)化算法比較研究[J].科學導報，2016（4）：223.

[3]丁小星，劉偉，韓加坤.淺談對修正牛頓法的一點改進[J].價值工程， 2016，35（34）：1314.

[4]林海嬋.無約束優(yōu)化問題的非單調(diào)PerryShanno方法[J].海南大學學報（自然科學版）自然科學版， 2015，33（4）：318326.

[5]汪丹戎.非線性共軛梯度法及全局收斂性分析[D].長江大學，2016：1112.

[6]胡夢英.一種改進的自適應信賴域算法[J].中國科技信息， 2016（17）：8082.

[7]劉金魁.無約束最優(yōu)化問題與非線性方程組的若干解法研究[D].重慶大學， 2016：69.

[8]段瓊，戴璟，喬慧.一種改進的牛頓法及其在歐式距離選址模型中的應用[J].物流技術(shù)，2017，36（8）：139142.

[9]王玨鈺.基于子空間技術(shù)的（無）約束優(yōu)化問題的不精確（高斯）牛頓法的理論與應用[D].上海師范大學，2016：1214.

[10]趙禮翔，劉國慶.基于Givens矩陣和聯(lián)合非線性不相關(guān)的盲源分離新算法[J].計算機科學，2015，42（5）：149152.

[11]鄭新宇，劉停戰(zhàn).無約束最優(yōu)化中行列修正擬牛頓法的計算效能和最佳換元周期[J].中國傳媒大學學報（自然科學版）自然科學版，2015（6）：3539.

[12]于慧慧，王永麗，陳勇勇，等.求解無約束一致性優(yōu)化問題的分布式擬牛頓算法[J].山東科技大學學報（自然科學版），2016，35（3）：112118.

[13]張新華.等式約束非凸優(yōu)化問題的修正牛頓算法[J].數(shù)學雜志， 2015（1）：111.

作者簡介：李明偉（1978），男，漢族，云南昆明人，云南大學數(shù)學系師范專業(yè)（已畢業(yè)），重慶師范大學計算機應用技術(shù)專業(yè)工程碩士（在讀），云南開放大學，講師，研究方向：數(shù)學教學，計算機應用技術(shù)。