当前位置：文档之家 › 非线性互补问题的光滑算法

非线性互补问题的光滑算法

  • 格式：docx
  • 大小：39.40 KB
  • 文档页数：5

非线性互补问题的光滑算法

朱红焰;岳靖;巩成艳

【摘 要】Based on the equivalent deformation of nonlinear

complementarity problems (NCP(F)) and the use of smooth approximating

functions of Fischer-Burmeister function,the problem is transformed into

optimization problem. A smoothing approximation algorithm is proposed

for solving the nonlinear complementarity problem.By introducing a new

smoothing NCP-function,the problem is approximated by a family of

parameterized smooth equations. The proposed al-gorithm has been

proved to be globally convergent under certain conditions. Numerical

experiment results demonstrate the effectiveness of the algorithm.%基于非线性互补问题(NCP(F))的等价变形,利用Fischer-Burmeister函数的光滑逼近函数将非线性互补问题转化为优化问题.提出了一种求解非线性互补问题的光滑逼近算法,通过构造非线性互补问题的一个新的光滑逼近函数,将非线性互补问题等价地转化为求解光滑方程组问题.在一定条件下证明了该算法的全局收敛性.数值实验结果说明了算法的有效性.

【期刊名称】《长春理工大学学报（自然科学版）》

【年(卷),期】2016(039)005

【总页数】4页(P127-130)

【关键词】非线性互补问题;光滑逼近算法;全局收敛性

【作 者】朱红焰;岳靖;巩成艳 【作者单位】安徽理工大学 理学院,淮南 232001;安徽理工大学 理学院,淮南

232001;安徽理工大学 理学院,淮南 232001

【正文语种】中 文

【中图分类】O224

考虑以下非线性互补问题NCP(F):求向量x∈Rn使得

其中F∶Rn→Rn连续可微的P0-函数。

由于其在理论和实际应用上的重要性，近年来，非线性互补问题已经受到了许多研究者的关注。

首先，给出Fischer-Burmeister函数:

求非线性互补问题（1）等价转化为求解以下非线性方程组:

且Φ∶Rn→Rn，它的第i个分量由下面的表达式给出:

Fischer-burmeister函数有很多好的性质，在求解NCP（1）时，一般都以Fischer-Burmeister函数作为 NCP函数，但是Fischer-burmeister函数在(a,b)=(0,0)点是不可微的，给算法的收敛性分析带来困难，于是光滑算法应运而生。

本文构造一个新的光滑NCP函数如下:

其中，μ＞0为光滑参数，记 Φ(x,μ)=(φ1(x,μ),φ2(x,μ),…,φn(x,μ))T作为 Φ(x)的光滑逼近函数，

对于任意的μ1＞μ≥0，有:

特别地，对于μ＞0，有即当μ→0时，φi(x,μ)一致收敛于φi(x).

引理1:若Φ(x,μ)，Φ(x)是如上所定义的，则Φμ是Φ的一致光滑逼近函数。通过简单计算得

显然，对于任意的μ＞0，都是连续的。

利用光滑逼近函数，问题可以转化为下面带约束的非线性方程组 显然，当μ＞0时，Φμ(x)是光滑的，且其Jacobi矩阵∇Φμ(x)T为:

其中，Jacobi矩阵的第i个分量为

算法1:

Step 1 选取参数 ρ1,ρ2∈(0,1)，σ1,σ2＞0，选择正数序列{ηk}，满足

其中，η＞0，选取初始点 x0∈Rn和正常数置k∶=0，

Step 2 如果算法终止；否则求解如下方程的解

若式（13）成立，置λk∶=1，转step5；

Step4 若m是满足下属不等式的最小非负整数

置λk∶=ρ1m；

Step5 置xk+1∶=xk+λkdk；

Step6 若（12）成立或者选取μk+1满足式（15）

否则，置μk+1∶=μk；

Step7 置k∶=k+1，转Step2

注1:由于 ηk＞0，总可以选取充分小的λ=ρ1i＞0，使得不等式（14）成立，从而算法是可行的。

注2:若是{xk}是由于算法产生的无穷数列，则对于任意的k满足Φ(xk,μk)≠0，且正数序列{μ k}是非增的，并且满足式（16）:

则由于式（6）和式（16）可以得到证明如下:

从而可以得到式（19）:

假设

（a）水平集有界，且正数η由（11）给出；

（b）对于任意的μ＞0，Φ'(x,μ)非奇异，且x∈Ω。

引理2:设序列{xk}是由算法产生的，那么对于任意的k，有{xk}⊂Ω,

证明:对于算法1中步3中的式（13），结论显然成立，对于步4中的式（14），有:

引理3:设序列{xk}由算法产生，定义指标集其中:

若指标集K为无限集，那么:

且序列{xk}的任意聚点是问题（1）的解。

证:由题中K为无限集，又因K={0}⋃K1⋃K2，故只需要考虑以下两种情况:

情形1:K2是无限集.此即意味着（21）式无限次成立，而ρ2∈(0,1)，故由引理即可得（22）成立。

情形2:K2是有限集，但K1是无限集，不失一般性，设对任意的非负整数k，记即ki是 K中不大于k的最大指标，则显然有μk=μki。

由（17），对i≥0，有:

由算法的step 6可知

以及

综上表明序列{xk}的每个聚点都是Φ(x)的一个零点，即问题（1）的一个解。

定理1:设假设成立，序列{xk}由算法产生，那么指标集K必是无限集，且

证明:用反证法，假设K是有限集，K采用情形2的假设方式，则μk=μki=μ，且步长λk由（14）确定，即

由假设（b），存在常数 M1＞0，使得

因此，对于充分大的K，有

不失一般性，假设并设x是相应序列的一个聚点，令则 λ≥0，且λd=0

（a）当 λ＞0时，有 d=0则由（12）式即得Φ(x)=0，矛盾。

（b）当λ=0时，由（14）式即得当k∈K充分大时，不满足（23）式，即有

对上式两端同时除以λk'，且令k(∈K)→∞，得

由于-∇Φ(xk,μ)dk=Φ(xk)，令k(∈K)→∞，得

又由（26）式得 因此式（25）与式（27）矛盾，从而K为无限集.

该问题有一个退化解和一个非退化解(1,0,3,0)T，选取的参数为γ=0.1，σ1=0.5，σ2=0.5，ρ1=0.6，ρ2=0.5算法的终止准则为Φ(xk+1)＜10-6。选取不同的初始点，数值结果见表1

论文将NCP问题转化为光滑方程组来求解，构造了相应的光滑逼近算法，证明了在一定条件下该算法的全局收敛性，同时给出数值试验来验证算法的时效性，下一步工作的重点是证明算法的局部二次收敛和超线性收敛，以及算法产生的迭代序列至少存在一个聚点。

【相关文献】

［1］ 许小芳，马昌风.基于一个新的NCP函数的光滑牛顿法求解非线性互补问题［J］.数学杂志，2011，31（4）: 750-755.

［2］ 范斌，马昌凤.求解非线性互补问题的一个雅可比光滑化方法［J］.福建师范大学学报，2012，28（3）:27-31.

［3］ 张修梅，蒋利华.非线性互补问题的光滑逼近法［J］.安徽大学学报，2012，36（2）:24-28.

［4］ 陈争，马昌凤.求解非线性互补问题的一个新的Jacobin光滑化方法［J］.计算数学，2010，32（4）:362-372.

［5］ 柴婧，马昌凤.求解广义非线性互补问题的光滑拟牛顿算法［J］.高校应用数学学报，2011，26（4）:453-466.

［6］ 于一超，田志远，刘相静，等.非线性互补问题的一个数值解法［J］.青岛大学学报，2014，27（3）:14-18.

［7］ 韩继业，修乃华，戚厚锋.非线性互补理论与算法［M］.上海:上海技术科学出版社，2003:248-296.

［8］ 马昌凤.最优化方法及其Matlab程序设计［M］.北京:科学出版社，2010:53-68.

合集下载

求解随机线性互补问题的光滑牛顿投影算法

求解随机线性互补问题的光滑牛顿投影算法

Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ　Ｖｉｓｉｏｎ　科技视ＰＦ－　科技・探索・争鸣　求解随机线性互补问题的光滑牛顿投影算法　单锡泉　（山东科技大学数学与系统科学学院，山东青岛２６６５９０）　【摘要Ｊ本文通过引入惩罚ＦＢ函数的一个光滑逼近函数，给出一种求解随机线性互补问题的光滑牛顿投影算法，证明了算法的全局收　敛性。　【关键词】随机线性互补问题；光滑牛顿投影算法；全局收敛性　Ｓｍｏｏｔｈ　Ｐｒｏｊｅｃｔｅｄ　Ｎｅｗｔｏｎ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｓｏｌｖｉｎｇ　Ｓｔｏｃｈａｓｔｉｃ　Ｌｉｎｅａｒ　Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　Ｐｒｏｂｌｅｍｓ　ＳＨＡＮ　Ｘｉ－ｑｕａｎ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｓｙｓｔｅｍｓ　Ｓｃｉｅｎｃｅ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄａｏ　Ｓｈａｎｄｏｎｇ　２６６５９０，Ｃｈｉｎａ）　【Ａｂｓｔｒａｃｔ］Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｂｙ　ｉｎｔｒｏｄｕｃｉｎｇ　ａ　ｓｍｏｏｔｈ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｐｅｎａｌｉｚｅｄ　ＦＢ　ｆｕｎｃｔｉｏｎ，ａ　ｓｍｏｏｔｈ　ｐｒｏｊｅｃｔｅｄ　Ｎｅｗｔｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｓｔｏｃｈａｓｔｉｃ　ｌｉｎｅａｒ　ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　ｐｒｏｂｌｅｍｓ　ｉｓ　ｐｒｅｓｅｎｔｅｄ．Ａｎｄ　ｗｅ　ｐｒｏｖｅｄ　ｔｈｅ　ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．　【Ｋｅｙ　ｗｏｒｄｓ］Ｓｔｏｃｈａｓｔｉｃ　ｌｉｎｅａｒ　ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　ｐｒｏｂｌｅｍ；ｓｍｏｏｔｈ　ｐｒｏｊｅｃｔｅｄ　Ｎｅｗｔｏｎ　ｍｅｔｈｏｄ；ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　Ｏ引言　线性互补问题（ＬＣＰ）ｉ一宪义为：寻求　ＥＲｎ。满足　≥０，Ｍｘ＋ｑ　Ｏ，　（＾　＋ｇ）＝０，　其中Ｍ∈尺一是一个ｎＸｎ实矩阵．ｑ∈Ｒｎ是一个ｎ维矢量。　当我们研究实际问题时．总会受到许多不确定因素的影响．使得　线性互补问题包含了不确定的数据．这就是随机线性互补问题　（乩ｃ尸）　。本文研究一类特殊的随机线性互补问题，即样本空间ｎ只　包含有限个不确定因素ｃｃ，。假设ｎ＝｛　，　，…，　ｊ，该问题描述为：寻　求　∈　．满足　Ｏ，Ｆ（ｘ，ｑ）　＾　（ｑ　＋ｇ（ｑ）　０，　Ｆ（　ｑ）＝０，　ｌ＝１，２，．．．，ｍ，ｍ＞１．　（１）　我们假设　＝ｐ｛ｃｏ，∈Ｑ｝＞ｏ０＝１，２，．．．，Ｊ，，）。令　）表示随机函数的　期望值．则有　Ｆ　）＝目Ｆ（五ｃｏ）】＝Ｍ　＋ｇ＇　其中府　ｐ，Ｍ（ｃｏ，）￣ｔｌｑ一　∑　ｇ（ｑ　于是求解问题ｆｌ１等价于求ｉ　，、・　＝１　ｆ＝ｌ　ｏ　～一’…～　‘，’　－０’Ｊ’　解下列问题　Ｏ，ＭＸ＋ｑ≥０，　。（＾　＋ｑ）＝０　（２）　下面我１＂ｆｌ￣ｌ入几个概念　定义１．１　给定函数日：Ｒ　．我们称光滑函数　日　（。）：Ｒ　＿÷　（　＞Ｏ）为Ⅳ的光滑逼近函数，如果对任意的　∈　ｎ，存　在Ｋ＞Ｏ．使得　Ｉ　（　）一日（　）　Ｖ　＞０．　如果Ｋ不依赖于　，则称　（・）为日的一致光滑逼近函数。　定义１．２设Ｍ∈尺一，若肘的所有主子式皆为非负，则称肼为Ｒ　矩阵　定义ｌ－３函数ｄｐ：Ｒ　幔称为ＮＣＰ函数．如果它满足　＃Ｃａ，６）＝０曹ａ　Ｏ，ｂ≥０，ａｂ＝０．　惩罚ＦＢ函数【　Ｏｌ　（口，６）＝ａ＋ｂ一、，口　＋ｂ　＋　６＋，　＞０，　其中对任意的标量Ｃ，ｃ＋＝ｍａｘ｛Ｏ，ｃ｝是一类常见的ＮＣＰ函数。下面　我们构造惩罚ＦＢ函数的光滑逼近函数　（　６）＝口＋占一√　ｉ　＋导（　＋√　ｉ　）　＋√　）’　＞ｏ　继续考虑问题（１），这里使用　（　，　６）和松弛变量　ｙ＝Ｌｙ　，　Ｔ：，．．．，ＹｉＴｍ］　ＥＲ　，　∈Ｒ　（　ｌ，２，…，ｍ），把要考虑的问题（１）转化　成下面带有非负约束的光滑化方程组系统　厂　、　（　，　ＬＧ（　Ｊ　，Ｙ　，　（３）　其中　Ｇ（　，　，ｙ）＝　（　，　）　（　，　）　Ｍ（ｃｏ１）ｘ＋ｇ（ｑ）一　ｌ　＾　（　）　＋ｇ（　）一ｙ．ｍ　九（鸬　，【府　＋　】Ｉ）　丸（　，　，　＋　】　）　（，‘Ｘｎ，　＋ｇＬ）　因此，若问题（１）有解，问题（１）等价于问题（３）。　若令ｚ＝　ｙ）ｅＲ　．则其Ｊ　ｏｂｉａｎ矩阵可以表示为　㈣　【ａ　（　（　）Ｊ　ｆ　ｏ　０］　中　（　）ａ　（　）。｝　（４）　Ｌ　０　Ｍ　一，Ｊ　其中Ｍ＝　ｒ（ｑ）　，Ｍ（　）　．．．．，　（　）　】Ｔ，，是ｍｎ维单位矩阵。　令　＝　，　），系统（４）的价值函数可以定义为　（ｗ）＝￣ＩＩＨ＜ｗ）ｌｒ　若问题（１）有解，求解系统（３）等价７：￣，ＴｙｌＪ优化问题的全局解　ｒａｉｎ　ｗ）　．ｆ．ｗ≥０．　（５）　不难看出　（　）是连续可微的，且其梯度为Ｖ　（ｗ）＝Ｖ　（ｗ）　（ｗ）．　若令ｚ＝｛＝￡尺　。　：＝　０｝和矿一ＲｘＺ．定义投影梯度方向为　＝儿ｃｗ一　…６ｒＬ　一：）　㈤　其中ｙ＞Ｏ是一个与Ｗ有关的常数，则问题（５）的一个稳定点可以　用　如（　ｌ。ｏ来衡量…】。现在基于问题（５），给出其相应的算法。　１　光滑投影牛顿算法　该算法通过运用一些扰动技术和选择恰当的搜索方向策略．保证　了在相应最优化问题的任何非稳定点处光滑化变量严格为正这一关　键点。对于　＞Ｏ，算法通过使用一个扰动策略，可以保证在迭代中　＞　０。令ａ∈（０，１）为一常数，　＝ａｍｉｎ｛ｌ，ｌ　（１　｝。对ｋ＝Ｉ，２，…，定义序　列｛　｝为　一ｊ　如果勰ＩｉＩｌ｛ｌ，８　ｏ）　＞　，　ｌａｍｉｎＯ，Ｉｌａ￣ｏ）ｌｌ　｝，　否　（７）　作者简介：单锡泉（１９９Ｏ一），男，山东寿光人，硕士研究生，山东科技大学，研究方向概率论与数理统计。　ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎ。ｌ。ｇｙ　Ｖｉｓｉ。ｎ科技视界ｌ　１　１

混合互补问题的光滑算法及收敛性

混合互补问题的光滑算法及收敛性

龙源期刊网

混合互补问题的光滑算法及收敛性

作者：何郁波,马昌凤,董晓亮

来源：《经济数学》2010年第03期

摘 要 利用Fischer-Burmeister函数将混合互补问题转化为非线性方程组,由光滑函数逼近FB函数来求解非线性方程组.文中将信赖域方法和梯度法相结合,提出了Jacobian光滑化方法.算法在一定条件下的全局收敛性得到了证明,数值试验表明算法切实有效,有一定的优越性.

关键词 混合互补问题;Jacobian光滑算法;信赖域方法;梯度步;全局收敛;二阶收敛

中图分类号 O178 文献标识码:A

1 引 言

互补问题是运筹学与数学的一个交叉研究领域,许多经济、金融、控制等方面的问题都可以转化为互补问题来求解,其中混合互补问题是求∈[a,b],使得对任意x∈[a,b]满足

-

式中,a,b∈为连续可微的向量函数.这类问题也称作箱形约束的变分不等式问题引入松弛变量后系统的解满足系统

F(x)+y---

b--

文献[1]中采用了将信赖域方法和线搜索技巧相结合的光滑化方法来求解非线性互补问题,该方法推广了和Qi的方法[2].Ma和Kang在[3]中也采用两种下降方向相结合的方法求解变分不等式.

基于这种思想,本文推广文[2]的算法,针对混合互补问题,采用将信赖域和梯度方法相结合的方法,提出了逐次逼近光滑近似算法.

2 辅助函数及性质

问题(1)等价于系统

---- 龙源期刊网

由函数-a-b的性质知,问题(2)等价于求解非线性方程组

----

相应于方程组(3)的效益函数定义为形如问题(3)的非光滑方程组,研究得最多的是构造光滑逼近函数的方法,这些方法基本上每迭代一次,需求解广义牛顿方程,增加运算量.第2节我们将通过引入光滑函数,并介绍光滑逼近函数.

解决非线性互补问题的Derivative-Free算法

解决非线性互补问题的Derivative-Free算法

２００７年７月　第３１卷第４期　安徽大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ　Ｊｕｌｙ　２００７　Ｖｏ１．３１　Ｎｏ．４　

解决非线性互补问题的Ｄｅｒｉｖａｔｉｖｅ—Ｆｒｅｅ算法　

蒋利华　，徐安农　

（１．安徽理工大学数理系，安徽淮南２３２００１；　２．桂林电子科技大学数学与计算科学学院，广西桂林５４１００４）　

摘要：基于ＮＣＰ（Ｆ）的约束极小化变形，构造了一种新的ｍｅｒｉｔ函数，将原始的ＮＣＰ（Ｆ）问题转化　为约束极小化问题，并构造了相应的ｄｅｒｉｖａｔｉｖｅ—ｆｒｅｅ下降算法，并在ｍｅｒｉｔ函数严格单调的条件下证明　了ｄｅｒｉｖａｔｉｖｅ—ｆｒｅｅ算法的合理性以及整体收敛性．　关键词：非线性互补问题（ＮＣＰ（Ｆ））；ｍｅｒｉｔ函数；ｄｅｒｉｖａｔｉｖｅ—ｆｒｅｅ下降算法；整体收敛性　中图分类号：０１７５　文献标识码：Ａ　文章编号：１０００—２１６２（２００７）０４—００１７—０５　

非线性互补问题ＮＣＰ（Ｆ）［１－２］即求　∈Ｒ　，使得　

≥０，Ｙ＝Ｆ（ｘ）≥０，　Ｙ＝０　

其中Ｆ：　一Ｒ　连续可微．　为了解决ＮＣＰ（Ｆ），给出如下的ｍｅｒｉｔ函数　：　一　为　

（　）＝∑咖　（　Ｆ　（　））　

其中咖础：　，是如下的增广Ｆｉｓｃｈｅｒ—Ｂｕｒｍｅｉｓｔｅｒ　ＮＣＰ函数　

咖　ａ，６）＝詈（口６）　＋譬（　一口一６）　

且Ｏｔ≥０，口＞０为实的参数．　

类似文［３］，此函数具有如下的一些性质：　命题１由（３）式定义的ＮＣＰ函数咖础（口，ｂ）满足　

（ａ）咖础（口，ｂ）＝０甘口≥０，ｂ≥０，ａｂ＝０；　

（ｂ）咖础ａ，ｂ）≥０，Ｖ（口，ｂ）　∈Ｒ　；　

（ｃ）对Ｖ（口，ｂ）　∈Ｒ　，咖衄（口，ｂ）连续可导．且　

（ｏ，０）＝　（ｏ＇０）＝０Ｏａ　ｄＤ　

ｏａ　６）　㈨）＋＋卢（一１）（　一口－６）　。、　／，ｌ　＾　／　

６）…㈨）＋＋卢（　）（　一口－６）　

一种广义非线性互补问题的新的光滑牛顿算法

一种广义非线性互补问题的新的光滑牛顿算法

第１４卷第２期　２０１５年６月　南通大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｎａｎｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．１４　ＮＯ．２　Ｊｕｎ．２０ｌ５　

一种广义非线性互补问题的新的光滑牛顿算法　徐引玲　（西安财经学院应用数学系，陕西西安７１００６１）　摘要：提出了一种新的光滑牛顿法，即在算法中嵌入非单调的线搜索技术，并将该算法从非线性互补问题　（ＮＣＰ）推广到广义非线性互补问￣（ＧＮＣＰ）．通过证明，该算法对ＧＮＣＰ问题是适定的，并在ＧＮＣＰ解集非空有界　的假设条件下．证明了该算法的全局收敛性和局部二次收敛性．　关键词：非线性互补问题；光滑函数；非单调线搜索；光滑牛顿算法；全局收敛性；局部二次收敛性　中图分类号：０２２４　文献标志码：Ａ　文章编号：１６７３—２３４０（２０１５）０２—００８５－－０６　Ａ　Ｎｅｗ　Ｓｍｏｏｔｈｉｎｇ　Ｎｅｗｔｏｎ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｇｅｎｅｒａｌｉｚｅｄ　Ｎｏｎｌｉｎｅａｒ　Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　Ｐｒｏｂｌｅｍ　ＸＵＹｉｎｌｉｎｇ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ａｐｐｈｅｄ　Ｍａｔｈｅｍａｔｉｃｓ，Ｘｉ　ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｘｉ　ａｎ　７１００６１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｓｍｏｏｔｈｉｎｇ　Ｎｅｗｔｏｎ　ｍｅｔｈｏｄ　ｗａｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｅｍｂｅｄｄｅｄ　ｔｈｅ　ｎｏｎｍｏｎｏｔｏｎｅ　ｌｉｎｅ　ｓｅａｒｃｈ　ｔｅｃｈｎｉｑｕｅ．　Ｔｈｉｓ　ｔｅｃｈｎｉｑｕｅ　ｗａｓ　ｅｘｔｅｎｄｅｄ　ｆｒｏｍ　ｎｏｎ，ｎｅａｒ　ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　ｐｍｂｌｅｍ（ＮＣＰ）ｔｏ　ｔｈｅ　ｇｅｎｅｒａｌｉｚｅｄ　ｎｏｎｌｉｎｅａｒ　ｃｏｍｐｌｅｍｅｎ－　ｔａｒｉｔｙ　ｐｒｏｂｌｅｍ（ＧＣＮＰ）．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｗｅｌｌ—ｄｅｆｉｎｅｄ　ｆｏｒ　ＧＮＣＰ。ａｎｄ　ｕｎｄｅｒ　ｔｈｅ　ａｓｓｕｍｐｔｉｏｎ　ｔｈａｔ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｓｅｔ　ｏｆ　ＧＣＮＰ　ｗａｓ　ｂｏｕｎｄｅｄ　ａｎｄ　ｎｏｎｅｍｐｔｙ，Ｉｔ　ｃｏｎｆｉｒｍｅｄ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｌｏｃａｌｌｙ　ｑｕａｄｒａｔｉｃ　ｃｏｎｖｅｒｇｅｎｃｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｎｏｎｌｉｎｅａｒ　ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ　ｐｒｏｂｌｅｍ；ｓｍｏｏｔｈｉｎｇ　ｆｕｎｃｔｉｏｎ；ｎｏｎｍｏｎｏｔｏｎｅ　ｌｉｎｅ　ｓｅａｒｃｈ　ｔｅｃｈｎｉｑｕｅ；ｓｍｏｏｔｈｉｎｇ　Ｎｅｗｔｏｎ　ｍｅｔｈｏｄ；ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ；ｌｏｃａｌ　ｑｕａｄｒａｔｉｃ　ｃｏｎｖｅｒｇｅｎｃｅ