无约束优化问题的精细修正牛顿算法分析

摘要：无约束优化问题是人们在探讨优化问题的典型和基础。为了解决这一问题，这一问题被提出时，牛顿通过研究确定了一种快速收敛的方式，解决了最速下降法存在的收敛性局限问题。但与此同时，牛顿算法不能解决一般非凸函数求解中迭代点矩阵正定不定的问题。最速下降法和牛顿算法可以分别解决迭代点矩阵负定或半负定、正定的问题。在前人研究的修正牛顿算法的基础上，笔者提出对最速下降法、牛顿算法及修正牛顿算法的优势进行结合，从而获得一种精细修正牛顿算法，用以解决迭代点矩阵正定不定的问题，收效良好，可以进行全局的收敛分析。

关键词：无约束优化问题；牛顿算法；最速下降法；修正牛顿算法

微分方程是微积分学科重要的研究内容，微积分奠基人Newton和Leibniz分别在其著作中就有关微分方程的问题进行过论证，且广泛应用于多个学科的研究当中。而无约束优化问题正式微积分这一学科发展的结果，并且广泛适用于计算机应用的科学之中。在进行无约束有过时，往往为了获得最优解及实现快速收敛，采取多种算法。但是根据应用算法的不同，其全局性和收敛速度有所区别。作为微积分的奠基人Newton所提出的牛顿算法已经被当今科研人员结合实际问题进行修正和拓展。本文正是在前人研究的基础之上进行结合和优化，从而寻求一种全局收敛效果良好的无约束优化问题的求解方法。

1 问题的提出

无约束优化被认为是最优化问题的基础。在进行无约束优化问题的求解过程中，通过使用牛顿法、拟牛顿法、共轭梯度法、最速下降法等算法。对于共轭梯度法而言，它对问题初始值的依赖性比较大，很难获得全局收敛的最小值。对最速下降法而言，它是一种结构简单实现容易的算法，能够较好的实现全局收敛。而根据理论验证，这种方法的收敛速度比较慢，通常职能达到局部收敛速度。牛顿法相比较而言，收敛速度更快，所使用的范围也更广。虽然牛顿法拥有二阶收敛速度，但是迭代点的问题即Hessian矩阵正定不确定始终对其应用有所影响。因此相关学者也纷纷提出了牛顿法的优化，如修正牛顿法。那么本文试图在已有的修正牛顿法的基础上，结合最速下降法和牛顿法的基本原理，提出对型如函数

minf（x），x∈Rn（1）

其中f：Rn→R下的二次连续可微函数的无约束优化问题进行求解。其核心就是要将迭代点目标函数的一阶、二阶信息充分利用，选取合理的搜索方向，从而建立全局收敛性。

2 精细修正牛顿法的计算方法分析

本文所提出的精细修正牛顿算法是综合了最速下降法、牛顿法以及修正牛顿法的优点获得的。主要就是为了解决迭代点hessian矩阵正定不确定的问题。那么首先要求根据迭代点处的目标函数的一阶、二阶信息来确定合理的搜索方向。

现在可以假设函数（1）的迭代点为xk，那么此时可以获得该迭代点处目标函数的梯度函数为gk=f（xk）。那么结合hessian矩阵的函数关系Gk=2f（xk）.如果gk=f（xk）≠0。那么可以对Gk的矩阵性质进行研究。如果Gk为正定矩阵，那么目标函数f：Rn→R下的二次连续可微性可知，迭代点xk附近为严格的凸函数。那么此时可以确定搜索方向为dk=-G-1kgk。搜索方向确定为牛顿法方向。

如果Gk为负定或者半负定矩阵时，则根据目标函数的连续可微性质得知，迭代点处为凹函数，那么此时的搜索方向可以确定dk=-gk。也就是最速下降法的搜索方向。

上述两种都是已知的搜索方向确定。那么如果Gk的矩阵性质为不定或者半正定时，我们就需要构建新的方式来对当前的矩阵性质就行修正，从而获得可以继续进行研究的正定矩阵。根据迭代点矩阵Gk的自身性质，其为实对称阵，必然存在可逆矩阵Pk使得P-1kGkPk为对角阵。那么根据矩阵函数的特征，确定λ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

那么根据上述迭代点xk的搜索方向可以看出，dk始终为迭代点的下降方向，并且满足WolfePowell线搜索规则。那么寻找ak满足下列条件：

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

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

其中0<σ1<1/2，且1>σ2>σ1，σ1，σ2均为常数。

基础上述条件，我们可以得出精细修正牛顿法的在处理无约束优化问题时的基本步骤。

①设定初始点x0Rn，精度ε>0，参数δ>0，并给定常数0≤σ1<1/2且1>σ2>σ1，此时k值为0。当‖gk‖≤ε时，即终止运算，求得无约束优化问题（1）的解为xk。

②在未达到步骤①的要求时，根据迭代点处矩阵函数的正定性质，确定搜索方向。若矩阵为正定，则可以确定为牛顿法方向搜索即dk=-G-1kgk，其中Gk=2f（xk）。若确定为负定或者半负定矩阵时，那么此时的搜索方向可以确定为最速下降法dk=-gk。如果矩阵为不定或者半正定时就需要对矩阵进行修正，利用其实对称阵的性质，构造正定矩阵G-k=P-1kQ-Pk

③根据WolfePowell的线性搜索规则，确定步长ak，并且令xk+1=xk+akdk，k：=k+1，可以获得‖gk‖≤ε，终止运算并取得最最优解。

3 无约束优化问题的精细修正牛顿算法的全局收敛性研究

那么在获得精细修正牛顿算法的一般步骤后，我们就需要对其解决无约束优化问题的全局收敛性进行研究。从牛顿算法来看，其具有局部收敛速度快的特征，那么在进行精细修正后，其能够获得较好的全局收敛性。笔者将通过以下假设、引理进行推论和验证。本文所研究的无约束优化问题函数型为：minf（x），x∈Rn

（1），且目标函数f：Rn→R

下的二次连续可微函数。那么由此可以进行相关的假设：首先给出基本假设1、2。

假设1 ：目标函数f：Rn→R是二次连续可微函数，那么给定x0∈Rn，水平集F=[JB（{]x0∈Rn|f（x）≤f（x0）[JB）}]

假设2 假设水平集F的领域为γ，那么函数f（x）的梯度函数g（x）=▽f（x）在领域γ内存在常数m>0使得不等式（4）成立：

对于任意y，z属于领域γ有‖▽f（y）-▽f（z）‖|≤m‖y-z‖（4）

那么根据引理1 假设B∈Rn×n是任意实对称矩阵，那么矩阵B的特征值可以表示为λ（B）那么λ作为全体对称矩阵机上的函数，该概述的任意算子范数则关于矩阵B连续。由此可以得出推论：

当假设1成立时，可以获得两个推论：

推论1矩阵值函数g：Rn→Rn×n，aij：Rn→R，

g（x）=2fx=（2f[]xixj）n×n△（aij）n×n存在常数h1使得所有x∈F（F为有界闭集）使得不等式（5）成立：

|aij（x）|

那么矩阵值函数g的特征值在水平集F上有界。

推论2 矩阵值函数g-：Rn→Rn×n，a-ij：Rn→R，g-=P-1kQ-Pk，存在常数h2使得所有x∈F（F为有界闭集）使得不等式（6）成立：

|a-ij（x）|

那么矩阵值函数g的特征值在水平集F上有界。

根据矩阵的非零特征值的形态结合假设1、2和引理1可以获得下列推论

推论3 矩阵特征值序列{λkimin}，{q-kijmin}，存在常数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|，那么根据矩阵序列的特征值λki，q-kij可以获得不等式|λki|≤np1，|q-kij|≤np2.（8）

引理3 根据精细修正牛顿算法产生的搜索方向序列{dk}，那么则应该存在cos〈dk，-gk〉>η，其中η=min[JB（{]1，（m1[]nh1）n，（m2[]mh2）n[JB）}]>0（9）

具体分析如下：

那么当矩阵为负定或半负定方向时，采用最速下降法，则有cos〈dk，-gk〉=1，当矩阵为正定方向时，则依据牛顿算法，存在不等式：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

其中设定E为n×n阶的单位矩阵，那么根据矩阵性质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

同理当矩阵为不定或半正定时，根据修正结果获得的搜索方向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根据精细修正牛顿算法产生的步长序列{ak}，那么当假设2成立时，结合矩阵特征，则有不等式ak≥1-2[]L‖dk‖‖gk‖cos〈dk，-gk〉

引理5根据精细修正牛顿算法产生的迭代点的序列{xk}，且有xk∈水平集F，其中对于任意k均属于N集合。

引理6 当假设f为水平集F上的二次连续可微函数，那么搜索方向序列{dk}可得到以下两个结论，第一，序列{‖gk‖}是水平集F上的有界序列；第二，序列{‖dk‖}是水平集F上的有界序列。

根据上述推论、引理可获得定理：

根据精细修正牛顿算法可获得迭代点xk序列{xk}，根据梯度函数可以获得对应的梯度函数序列{gk}，那么目标函数f：Rn→R是二次连续可微函数，那么给

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

当水平集F的领域为γ，那么函数f（x）的梯度函数g（x）=f（x）在领域γ内存在常数m>0使得不等式成立：

对于任意y，z属于领域γ有‖▽f（y）-▽f（z）‖≤m‖y-z‖进而根据极限函数可知limk→+∞ inf‖gk‖=0

对这一定理进行验证，现在已知‖dk‖有界，根据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，而结合引理5、6，在该假设条件下limk→+∞ inf‖gk‖=0，与假设结果相反。因此可以证明在假设1、2成立的条件下，存在limk→+∞ inf‖gk‖=0

根据本文所获得的定理，通过反设和推论，结合相关的引理，证明本文所得定理具有良好的收敛性。因此根据cute中提出的十三个标准测试函数进行述职验证可知，其在解决无约束优化问题函数上的效果明显，能够解决最速下降法全局收敛速度慢的问题。

4 结论及展望

综上所述，本文所提出的针对无约束优化问题函数minf（x），x∈Rn（1）其中f：Rn→R下的二次连续可微函数的无约束优化问题进行求解。其核心就是要将迭代点目标函数的一阶、二阶信息充分利用，选取合理的搜索方向，从而建立全局收敛性。在假设目标函数f：Rn→R是二次连续可微函数，那么给定xo∈Rn，水平集F=[JB（{]x0∈Rn|f（x）≤f（x0）[JB）]且当水平集F的领域为γ，那么函数f（x）的梯度函数g（x）=f（x）在领域γ内存在常数m>0使得不等式成立：对于任意y，z属于领域γ有‖f（y）-f（z）‖≤m‖y-z‖进而根据极限函数可知limk→+∞ inf‖gk‖=0。根据cute中提出的十三个标准测试函数进行述职验证可知，其在解决无约束优化问题函数上的效果明显，能够解决最速下降法全局收敛速度慢的问题。根据无约束优化问题的具体推广，该种方法适用于生活、生产的多个领域。当然如果将这一算法进行推广和深度优化，还需要进行更多的研究、试验加以论证。

参考文献：

[1]郭小兰.牛顿法求解无约束优化问题[J].数字化用户，2017，23（30）：2629.

[2杨海丽.非线性最优化算法比较研究[J].科学导报，2016（4）：223.

[3]丁小星，刘伟，韩加坤.浅谈对修正牛顿法的一点改进[J].价值工程， 2016，35（34）：1314.

[4]林海嬋.无约束优化问题的非单调PerryShanno方法[J].海南大学学报（自然科学版）自然科学版， 2015，33（4）：318326.

[5]汪丹戎.非线性共轭梯度法及全局收敛性分析[D].长江大学，2016：1112.

[6]胡梦英.一种改进的自适应信赖域算法[J].中国科技信息， 2016（17）：8082.

[7]刘金魁.无约束最优化问题与非线性方程组的若干解法研究[D].重庆大学， 2016：69.

[8]段琼，戴璟，乔慧.一种改进的牛顿法及其在欧式距离选址模型中的应用[J].物流技术，2017，36（8）：139142.

[9]王珏钰.基于子空间技术的（无）约束优化问题的不精确（高斯）牛顿法的理论与应用[D].上海师范大学，2016：1214.

[10]赵礼翔，刘国庆.基于Givens矩阵和联合非线性不相关的盲源分离新算法[J].计算机科学，2015，42（5）：149152.

[11]郑新宇，刘停战.无约束最优化中行列修正拟牛顿法的计算效能和最佳换元周期[J].中国传媒大学学报（自然科学版）自然科学版，2015（6）：3539.

[12]于慧慧，王永丽，陈勇勇，等.求解无约束一致性优化问题的分布式拟牛顿算法[J].山东科技大学学报（自然科学版），2016，35（3）：112118.

[13]张新华.等式约束非凸优化问题的修正牛顿算法[J].数学杂志， 2015（1）：111.

作者简介：李明伟（1978），男，汉族，云南昆明人，云南大学数学系师范专业（已毕业），重庆师范大学计算机应用技术专业工程硕士（在读），云南开放大学，讲师，研究方向：数学教学，计算机应用技术。