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

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

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

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

1 問題的提出

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

minf（x），x∈Rn（1）

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

2 精細(xì)修正牛頓法的計(jì)算方法分析

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

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

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

上述兩種都是已知的搜索方向確定。那么如果Gk的矩陣性質(zhì)為不定或者半正定時(shí)，我們就需要構(gòu)建新的方式來對當(dāng)前的矩陣性質(zhì)就行修正，從而獲得可以繼續(xù)進(jìn)行研究的正定矩陣。根據(jù)迭代點(diǎn)矩陣Gk的自身性質(zhì)，其為實(shí)對稱陣，必然存在可逆矩陣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）就可以成為可處理的正定矩陣。那么此時(shí)的搜索方向確定為dk=-G--1kgk

那么根據(jù)上述迭代點(diǎn)xk的搜索方向可以看出，dk始終為迭代點(diǎn)的下降方向，并且滿足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ǔ)上述條件，我們可以得出精細(xì)修正牛頓法的在處理無約束優(yōu)化問題時(shí)的基本步驟。

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

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

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

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

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

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

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

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

假設(shè)2 假設(shè)水平集F的領(lǐng)域?yàn)棣?，那么函?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是任意實(shí)對稱矩陣，那么矩陣B的特征值可以表示為λ（B）那么λ作為全體對稱矩陣機(jī)上的函數(shù)，該概述的任意算子范數(shù)則關(guān)于矩陣B連續(xù)。由此可以得出推論：

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

推論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）當(dāng)p1=<|akij|，p2=maxi≥1，j≤n[DD）]|a-kij|，那么根據(jù)矩陣序列的特征值λki，q-kij可以獲得不等式|λki|≤np1，|q-kij|≤np2.（8）

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

具體分析如下：

那么當(dāng)矩陣為負(fù)定或半負(fù)定方向時(shí)，采用最速下降法，則有cos〈dk，-gk〉=1，當(dāng)矩陣為正定方向時(shí)，則依據(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

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

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ù)精細(xì)修正牛頓算法產(chǎn)生的步長序列{ak}，那么當(dāng)假設(shè)2成立時(shí)，結(jié)合矩陣特征，則有不等式ak≥1-2[]L‖dk‖‖gk‖cos〈dk，-gk〉

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

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

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

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

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

當(dāng)水平集F的領(lǐng)域?yàn)棣茫敲春瘮?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ìn)而根據(jù)極限函數(shù)可知limk→+∞ inf‖gk‖=0

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

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

對式（10）進(jìn)行整理可以獲得不等式（11）

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

那么就σ1ak‖gk‖‖dk‖cos〈dk，-gk〉進(jìn)行如下求和運(yùn)算：

∑∞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則應(yīng)存在ε，ε對任意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中提出的十三個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行述職驗(yàn)證可知，其在解決無約束優(yōu)化問題函數(shù)上的效果明顯，能夠解決最速下降法全局收斂速度慢的問題。

4 結(jié)論及展望

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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