文摘
广义牛顿法为一种互补问题的解决方案。该方法是基于非光滑方程再形成的问题F-B函数和广义牛顿法。是一个可微的函数使用的价值功能。当地的全局收敛性和超线性收敛的结果给出合适的假设下。最后,给出了一些数值结果和讨论。
1。介绍
本文考虑一种互补的问题: 在哪里是两个可微函数。方程(1GCP()也用F, G)(1]。当,(1)减少非线性互补问题,它是一个通用的框架非线性优化问题的最优性条件以及一些出现的问题在不同的领域。在过去的几年里,一些已建立互补理论和计算结果,如(1- - - - - -12]。该方法基于半光滑方程组再形成(1)。我们都知道,牛顿型方法是最快的一个方程和非光滑方程的解的方法。但通常只有局部收敛的方法。近年来,一些研究工作一直致力于全球化的本地方法的技术。所以,在这篇文章中,我们感兴趣的解决(1基于牛顿法)。基于线搜索方法和半光滑方程组改编了(1)。
本文组织如下。在下一节中,(1)转换为半光滑方程。然后,介绍了广义牛顿法求解再形成。全局收敛性和局部超线性收敛的方法。一节中3列出,数值实验结果和一些讨论。
2。预赛和方法
首先,我们介绍一些论文中使用的符号和主张(见例如[1- - - - - -5])。鉴于,我们使用表示其雅可比矩阵。如果是当地Lipschitzian和表示可微的集合点,B次微分和克拉克的雅可比矩阵在被定义为
让是一个局部李普希茨函数。如果下面的限制, 存在任何,据说是半光滑。
命题1。如果是半光滑,下面的方程是等价的。(一)当, (b)在哪里,
定义2。 被称为矩阵如果未成年人其主要都是积极的和矩阵如果未成年人其主要都是负的。
定义3。 被称为如果函数是连续可微的,其梯度是半光滑。
定义4。 BD-regular在如果非奇异的。
在下面,我们给的再形成(1)和广义牛顿法。基于F-B函数 我们考虑以下再形成(1): 解决(1) 解决(7)。表示 我们知道是局部李普希茨和可微的。当,我们有 在哪里。我们也知道,
当不在,因为,我们有 在哪里。
然后,对于,我们有
定义一个价值功能 然后解决(1)等价于求解无约束极小化问题如下: 在哪里是连续可微的。我们知道,在那里。现在,我们给出以下广义牛顿法求解(1)。
方法1(广义牛顿法)。鉴于和,。
步骤1。如果,停止。
步骤2。选择和计算方程的
如果条件 是不满意,准备好了吗。
步骤3。找到最小的整数这样
集,让步骤1,去。
方向得到解决(15)是一个函数的下降方向。这是一个标准的光滑方程的牛顿方法解决方案。但它不再适用于非光滑方程。在上述方法中,通过解决方向(15)是一个下降方向的事实。另一方面,正如我们所知,不是独一无二的15)如果不是满秩。所以,我们会给下面的命题,以确保是满秩。
命题5。假设由(1)满足,对于任何和;然后是满秩。
证明。让,让解决。通过上述的分析为常量,我们有
所以我们有
乘的方程在上面的方程,我们得到
如果,(12),我们有。所以,
然后
我们有
然后。另一方面,如果,我们有
通过,我们得到
然后的非奇异性遵循。这就完成了证明。
可能有一个全球最低与当(1)没有解决方案。另一点值得关注的是,平稳点的条件的解决方案(1)。类似于(1),我们给的条件,保证每个驻点是一个解决方案(1)。
命题7。如果是一个静止的点吗这样是满秩和是一个矩阵,然后是一个解决方案(1)。
现在,我们给方法的全局收敛性定理1。
定理8。假设序列生成的方法1。然后每一序列的聚点是一个静止的点吗。
证明。下面的证明是由两个部分。
我一部分。如果一个无限的一组指标,我们有,然后,通过命题1.16 (7),我们知道,任何的极限点是一个静止的点吗。
第二部分。我们假设的方向总是计算(15)。假设和。由(15),我们有
从(26),我们得到
为和,我们知道
如果为在。为这是有界的,(27),我们得到,这是矛盾的假设。另一方面,考虑到这一点是有界的,(16),不能无限。因为(17),这一事实是一个连续可微的函数,我们有什么
在下面,我们将证明是有界的远离。假设相反,
由(28),我们可以假设。两边的限制条件(30.),我们有
从(16),我们知道与(31日)。所以,我们知道是有界的远离。另一方面,(16)和(29日)暗示这与(28)。这就完成了证明。
在接下来的一部分,本节中,我们将讨论的局部超线性收敛的方法1。
备注9。假设序列生成的方法1。如果一个序列的极限点是,这是一个解决方案(1),是一个BD-regular解决方案,然后,我们可以在本地证明方向总是解决方案(15)和最后一个满足的步长(17)。所以最终减少了当地的方法。
定理10。让BD-regular条件维持在一个聚点序列的生成的方法1。然后收敛于Q-superlinearly。Q-quadratic如果收敛速度和是功能。
证明。自是一个聚点的存在子序列这样。我们知道对所有足够大。因此,这个定理的结果保证了定理3.1 (8]。
备注11。在方法1,(17)可以被以下线搜索: 在哪里和,是一个整数。
3所示。数值结果和讨论
在本节中,我们提出一些数值结果,也给一些讨论的广义雅可比矩阵计算方法。为解决系统(7),我们可以作为一种工具而不是克拉克和广义雅可比矩阵B微分。我们提供以下为在(7): 在哪里,如果,或如果,,如果。
示例13。我们认为广义互补问题(1),功能
这两个和是连续可微的函数。
我们使用方法1计算例子13。结果为例13与初始点和展示在表1。
在方法1如果我们更换(17)(32),我们也可以使用这种方法来计算例子13。结果为例13与初始点和展示在表2。
讨论1。数值结果的方法1在表中1和2,我们可以看到,(17)工作以及(32)。所以我们可以使用(17)或(32在实践中)。
在方法1,我们也可以更换(15)(35)或(36)。然后方法1成为Levenberg-Marquardt方法和修改Levenberg-Marquardt方法,这是在(4,10]。计算了
或
我们使用方法1(计算(15)),Levenberg-Marquardt方法(计算(35)),修改Levenberg-Marquardt方法(计算(36))计算的例子13。结果为例13与初始点和展示在表3。
讨论2。从数值结果的方法1(计算(15)),Levenberg-Marquardt方法(计算(35)),修改Levenberg-Marquardt方法(计算(36)表3,我们可以看到,我们的方法在本文中工作得十分比方法(4,10]。
从讨论1,我们可以看到,(17)工作以及(32)。当我们使用线搜索(32)取代(17),我们给下面的数值结果的方法1(计算(15)),Levenberg-Marquardt方法(计算(35)),修改Levenberg-Marquardt方法(计算(36))计算的例子13。数值结果给出了表4。
利益冲突
作者宣称没有利益冲突有关的出版。
承认
这项工作是由美国国家科学基金会支持的中国(11101231)。