英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

---

求解无约束凸优化问题的两步改进牛顿法

T. Dehghan Niri1 · S. A. Shahzadeh Fazeli1 . M. Heydari1

摘要

本文提出了一种求解无约束凸优化问题的两步牛顿法。该方法基于Traub迭代格式（方程求解的迭代方法，Prentice Hall，Englewood Cliffs，1964），并扩展到n变量。本文提出的两步算法是对牛顿法求解无约束优化问题的一种改进。在适当的条件下，对该迭代算法进行了收敛性分析。数值算例表明了该方法的有效性和性能。

关键词 牛顿法·无约束优化问题·收敛性分析

1介绍

优化问题的一般形式可以写为：

，

，

，

， (1)

其中E和I分别是等式和不等式约束的指标集，）是约束函数。当目标函数和约束函数都是线性函数时，这个问题称为线性规划。否则，该问题称为非线性规划。另外，不包含任何等式或不等式约束的问题称为无约束优化问题。现在，我们考虑一个无约束优化问题

(2)

其中 是光滑连续可微函数。要找到 的全局极小值并不容易，因为我们对目标函数的了解通常只是局部的。因此，大多数算法只能找到一个局部极小值，即在其邻域中达到 最小值的点[2]。换言之，如果有一个邻域N（包含的开集），使得对于所有，则点是局部极小值。大多数求解无约束优化问题的数值方法可分为两类：线搜索算法和信赖域算法。求解问题（2）有许多有用的算法，如共轭梯度法、信赖域法、拟牛顿法、经典牛顿法、含噪函数问题的Nelder–Meade单纯形法、Levenberg–Marquardt法等[2–4]。在上述方法中，经典牛顿法以其收敛速度快而著称。对于无约束极小化的牛顿法有一些改进，以实现全局和局部收敛，见[2，4]和其中的参考文献。在New-ton方法中，目标函数Hessian矩阵的正定性是获得局部极小值和快速局部收敛的必要条件。Zhou等人[5]提出了一种求解单调方程的新算法，并在弱于标准非奇异条件的局部误差界假设下证明了其超线性收敛性。文[6]提出了一种新的求解信赖域半径收敛为零的非线性方程的信赖域方法，并给出了该方法在某些弱条件下的收敛性。Li等人[7]得到了Hessian-at解可能奇异的凸极小化问题的两个正则化New-ton方法，并证明了如果目标函数在LC2中，则该方法在局部误差界条件下具有局部二次收敛性，而不需要孤立的非奇异解。Zhou和Chen在[8]中提出了一种求解Hessian矩阵可能奇异的凸极小化问题的改进正则化Newton方法。Nesterov和Polyak[9]提出了牛顿法的立方正则化。在每次迭代中，它需要求解一个无约束的极小化问题。Nesterov和Nemirovsky[10]提出了一类自洽函数，即三次可微凸函数，其二阶和三阶导数在每一点满足一个特定条件。Polyak[11]介绍了无约束凸优化的正则化牛顿法。对于任何凸函数，在有界最优集的情况下，RNM生成一个从任意起点收敛到最优集的序列。Dehghan等人[12]提出了一种新的牛顿法模型来解决无约束优化问题。而且，他们在求解无约束极小化问题的信赖域算法中使用了一种新的改进牛顿法，并分析了其局部和全局收敛性。最近，Dehghan等人提出了一种新的基于Q.I.F方法的正则化Newton方法来求解优化问题。上述算法的应用之一就是求解非线性方程组。例如，文献中出现的非线性方程组可以用这些方法求解。

本文提出了一种求解无约束凸优化问题的新算法。论文的组织结构如下：第一节。2.提出了一种求解无约束极小化问题的新算法。其相关的收敛性分析在第节中给出。三。文中给出了一些数值结果，并与其它算法进行了比较。第四节为结论。

2方法说明

在本节中，简要回顾了文献[2]中提到的求解无约束优化问题的牛顿法。考虑最小化问题，

(3)

式中， 是光滑函数，并且是两次连续可微的。梯度和海森矩阵 分别用和表示。在线性搜索方法中，每次迭代计算一个搜索方向，然后决定沿着该方向移动多远。迭代如下：

(4)

其中正标量称为步长。线性搜索方法的成功取决于步长和方向的选择。大多数直线搜索方法都要求是下降方向，因为这个属性保证函数可以沿着这个方向缩减。搜索方向可以定义为：

(5)

其中是对称非奇异矩阵。

牛顿法是求解非线性方程组的一种强有力的方法。它是泰勒多项式在函数求根中的应用。牛顿法是求解非线性方程的简单根的迭代法，即 ， 通过使用

(6)

在 [1，20–22]的某个邻域内二次收敛。牛顿法也可以用来求函数的最小值或最大值。导数在最小值或最大值处为零，应用牛顿法求导数的极小值和极大值。迭代变成：

(7)

通过用梯度 代替导数，用Hessian矩阵的逆 代替二阶导数的倒数，上述方法可以推广到多维。我们有下面的迭代公式

(8)

在线搜索牛顿法中，是Hessian矩阵. 。如果Hessian矩阵是非正定的，或接近奇异的，则可以在求解之前或求解过程中对其进行修正。下面是此方法的一般说明。

算法1.（带修改的线搜索牛顿）[2]：

对于给定的初始点和参数;

当

分解矩阵，其中，如果是充分肯定；否则，选择以确保为足够肯定。

解 ；

设；

当满足Wolfe、Goldstein或Armijo回溯条件。

结束

Hessian修正方法的选择对方法的有效性至关重要。多重根的修正牛顿法 和 ， 是二次收敛的，写为：

(9)

如果多重数m未知，则标准牛顿法具有线性收敛性，收敛速度为[23]. 特劳布[1]使用了一个变换 替代 计算 的多根。然后是找到一个倍数的问题将求根问题归结为求变换后的方程的一个单根的问题，从而任何迭代方法都可以保持其原来的收敛阶。将标准牛顿法（6）应用于 ，我们可以得到

(10)

(11)

现在，我们使用方法（8）和（11）提出了一种求解无约束优化问题的两步算法。

算法2.（建议方法）

第一步.给定一个初始点，和。

第二步.如果 停止，否则转到步骤3。

第三步.如果是一个正定矩阵

解；

或

解；

第五步.如果是足够正定的，则设；

否则，选择是为了确保是足够正定的，

解；

第六步.。

设并转至步骤2。

(

k

T

k

(

(

k

很明显，引入的矩阵 是对称矩阵。此外，该算法不需要每次迭代计算步长和 。

k

3收敛性分析

在本节中，我们研究了所提出方法的收敛性。以下假设贯穿全文。

假设3.1

（A1）：设 定义在有界闭集上，设是两次连续可微的，表示水平集的闭，

(12)

(A2) : 和都是Lipschitz连续的，即存在常数和，以便

(13)

和

(14)

(A3):

(A4):

(A5):

定理3.2 假设 是非奇异的矩阵，是，是，那么是非奇异的当且仅当是非奇异的矩阵。如果是这样，那么

(15)

这是谢尔曼-莫里森-伍德伯里公式[3，24，25]。更多概述见[3]。

命题3.3[3]设为非奇异矩阵，设. 那么 是可逆的当且仅当。在这种情况下，

(16)

引理3.4假设假设假设3.1（A1）和（A3）成立。那么

(I)

(II)

根据假设3.1（A3），我们有

(17)

因此

(18)

根据定理（3.2）和命题（3.3），我们设置了。从（17）我们得到

(19)

因此，矩阵是可逆的，我们可以得到

(20)

定理3.5假设假设假设3.1（A1）–（A5）成立。假设

(21)

和

(22)

然后迭代由算法2生成收敛到，其中是起点。

求证：在这个证据里，， 和 表示， 和 。利用引理3.4-I

(23)

在不丧失普遍性的前提下，我们假设正定矩阵根据（22）和（23）我们有

， (24)

因此

. (25)

从

， (26)

然后

=

. (27)

现在从引理3.4-I，假设3.1（A2）和（27），我们得到

. (28)

自是非奇异的，这意味着适用于所有足够大的k。因此从

假设3.1（A4）

. (29)

现在假设存在一个整数k，使得（i） 或（ii）。然后我们考虑以下情况：

案例（一）：本例意味着

， (29)

在（30）的帮助下，我们得到了

(31)

如果起点足够接近，则通过使用假设3.1（A5）序列收敛到。

案例（二）：这个案例意味着

， (32)

因此

， (33)

与前一种情况类似，使用假设3.1（A5）的序列收敛到。

备注1 当，该方法简化为标准牛顿法。

4 数值结果

在这一节中，我们报告了关于所提出算法的以下数值实验的一些结果。并与经典牛顿法和修正正则化牛顿法（MRN）进行了比较。我们假设，停止条件为。此外，在MRN法中的我们假设 和。表示目标的数目函数求值和表示梯度求值的数量。代码用matlab12.0编写，在2.3vGHZ、8GB内存的PC机上运行。以下标准起点为[26，27]和[28]的测试函数用于比较。得到的数值结果总结在表1中和2。如这些表格所示，所提出的方法（PM）优于经典的牛顿法（NM）和MRN法。这里，我们使用Dolan和More[29]提出的性能概要来比较和评估测试函数的每个实现。图1、2、3、4、5和6给出了 和的拟议方法、MRN方法和经典牛顿法相对于目标函数评估数和梯度评估数的性能曲线。另外，“Dim”表示问题的维度。图1、2和3显示了所

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[405150]，资料为PDF文档或Word文档，PDF文档可免费转换为Word