一种基于新NCP函数的非线性互补问题的光滑牛顿法

朱琳，芮绍平

（淮北师范大学数学科学学院，安徽淮北235000）

一种基于新NCP函数的非线性互补问题的光滑牛顿法

朱琳，芮绍平

（淮北师范大学数学科学学院，安徽淮北235000）

文章首先提出一类新的光滑互补函数，在此基础上将非线性互补问题转化为与之等价的光滑方程组；其次提出了一种求解非线性互补问题的光滑牛顿法，并证明算法具有全局收敛性；最后给出了数值实验.

非线性互补问题；牛顿法；全局收敛性

0 引言

互补问题由美国数学家Cottle首次提出，经过多年发展，互补问题包括：线性互补问题、非线性互补问题、二阶锥互补问题、半定互补问题、对称锥互补问题以及随机互补问题［1］，其中以非线性互补问题最为典型，其在经济、交通、金融、力学、控制等诸多领域应用广泛［2-3］.

非线性互补问题：求向量x=（x1，x2，…，xn）∈Rn，使得

其中F：Rn→Rn为连续可微函数.

本文主要提出一类求解非线性互补问题（1）的新光滑算法.算法基本思想是：首先给出一个新NCP函数（互补函数），通过该光滑函数利用光滑化技术将问题（1）转化为与之等价的光滑方程组，然后利用非精确牛顿法求解该方程组，从而得到原问题的解.文中非线性互补问题的解集都设为非空.

1 光滑函数及算法

定义1函数φ：R2→R称为互补函数，如果对∀（a，b）∈R2，φ（）a，b=0当且仅当a≥0，b≥0， ab=0.

迄今为止，许多类型的互补函数被提出［4］，其中最常用是Fischer-Burmeister函数（简称为FB互补函数）：

考虑到FB互补函数在（0，0）点不可微，许多优化研究者通过引入光滑参数对其光滑化，得到许多性质不同的光滑互补函数.本文通过光滑化FB互补函数（2），得到一个具有良好性质的新光滑函数该函数定义如下：

为了利用新光滑函数（3）求解非线性互补问题，首先证明该函数的性质.

引理1设（μ，a，b）∈R3，φ（μ，a，b）由式（3）定义，那么

（a）φ（0，a，b）=0⇔a≥0，b≥0，ab=0；

（b）对任意（μ，a，b）∈R++×R×R，φ（μ，a，b）连续可微.

证明由φ（0，a，b）=φFB（a，b）可知：φ（0，a，b）=0⇔a≥0，b≥0，ab=0.易知φ（μ，a，b）在任意点（μ，a，b）∈R++×R×R处连续可微，且

下面将利用光滑互补函数（3）将互补问题（1）转化为与之等价的光滑方程组.令z：=（μ，x）∈R+×Rn，并定义函数H（z）：R+×Rn→R+×Rn：

其中

由引理1可知H（z）在任意点z=（μ，x）∈R++×Rn处连续可微，通过简单计算其雅克比矩阵为：

其中

通过函数H（z），可定义一个价值函数Ψ（z）：R+×Rn→R如下：

因此，求解互补问题（1）等价于求解方程Ψ（x）=0.

下面借助于新光滑函数（3），在文献［5］的基础上，给出求解互补问题（1）的一类光滑化牛顿方法.

算法1取任意点z0=（μ0，x0）∈R++×Rn为初始点，再取常数δ，σ和γ满足δ∈（0，1），σ∈（0，1），γμ0＜0.5.取序列｛ηk｝使得ηk∈［0，η］，这里η∈［0，1-γμ0］为一常数，k：=0.

第1步若Ψ（zk）=0，停止.

第3步令θk为1，δ，δ2，…中最大值，使得

注：在实际数值实验中，与文献［5］中算法不同，如果H′（zk）奇异，插入一梯度步.

2 算法的收敛性分析

有唯一解，这里r∈Rn满足表示此唯一解.对∀α∈［0，1］定义

即

定理1假设对任意的z=（μ，x）∈R++×Rn，雅克比矩阵H′（z）非奇异且水平集L（z0）=｛z∈Rn+1|Ψ（z）≤Ψ（z0）｝有界，算法1产生的无穷序列｛zk｝的聚点z∗是H（z）=0的解.

证明由于对∀z=（μ，x）∈R++×Rn，H′（z）非奇异，故算法1第2步有定义，再根据引理2，第3步也能够在第k次迭代中有定义.因此，算法1能生成无穷序列zk=（μk，xk）.下面证明对于∀k＞0有

显然，z0∈Ω.假设zk∈Ω，也就是，可以得到

在算法1中，对充分大的k满足θk≥δl，θk≥δl.于是

再对上式两边关于k→+∞求极限，则

3 数值实验

为了测试算法1性能，进行数值实验.算法中的参数取值如下：

实验终止准则设为Ψ（zk）≤10-10.所测试问题为：F（x）=Mx+q，其中

表1 数值实验结果

从表1结果可以看出，本文所设计的算法稳定可靠，所需的迭代次数和CPU时间很少，说明文中所设计的新方法适合于互补问题的求解.

4 总结

首先给出了FB函数的一个新的光滑函数，介绍了该函数性质，利用这个函数将非线性互补问题转化为一个光滑方程组，然后设计了一种求解互补问题的光滑化牛顿算法，并证明了算法具有全局收敛性.这类算法的后续研究工作还很多，比如设计求解随机互补问题的光滑类算法等，值得进一步进行探究.

［1］韩继业，修乃华，戚厚铎.非线性互补理论与算法［M］.上海：上海科技出版社，2006.

［2］FERRIS M C，PANG J S.Engineering and economic applications of complementarity problems［J］.SIAM Review，1997，39（4）：669-713.

［3］HARKER P T，PANG J S.Finite-dimensional variational inequality and nonlinear complementarity problems：A survey of theory，algorithms and applications［J］.Mathematical Programming，1990，48（2）：161-220.

［4］CHEN J S，PAN S.A family of NCP functions and a descent method for the nonlinear complementarity problem［J］.Com⁃putational Optimization and Applications，2008，40（3）：389-404.

［5］RUI Shaoping，XU Chengxian.A smoothing inexact Newton method for nonlinear complementarity problems［J］.Journal of Computational and Applied Mathematics，2010，233（9）：2332-2338.

A Smoothing Newton Method for Nonlinear Complementarity Problem Based on a New NCP Function

ZHU Lin，RUI Shaoping
（School of Mathematical Science，Huaibei Normal University，235000，Huaibei，Anhui，China）

In this paper，we give a new NCP function.Based on the smoothing function，nonlinear complemen⁃tary problem is reformulated as a series of parameterized smooth equations.We proposed a smoothing Newton method for solving nonlinear complementary problem，and the global convergence is obtained.Preliminary nu⁃merical results are given.

nonlinear complementary problem；Newton method；global convergence

O 221.2

A

2095-0691（2016）03-0033-05

2016-04-15

安徽省自然科学基金项目（1508085SMA204）；高校优秀青年人才支持计划重点项目（gxyqZD2016109）

朱琳（1990-），女，安徽淮北人，硕士生，从事数值最优化研究；通讯作者：芮绍平（1978-），男，安徽安庆人，博士，副教授，研究方向：优化理论与计算、金融优化.