非線性互補問題計算機實現(xiàn)

摘 要：分析了非線性互補問題求解困難，利用粒子群算法并結(jié)合極大熵函數(shù)法給出了該類問題的一種新的有效算法。該算法首先利用極大熵函數(shù)將非線性互補問題轉(zhuǎn)化為一個無約束最優(yōu)化問題，然后應用粒子群算法來優(yōu)化該問題，計算機程序?qū)崿F(xiàn)表明該算法是有效的。

關鍵詞：計算機實現(xiàn)；非線性互補問題；粒子群算法

中圖分類號：O224 文獻標識碼：A

Abstract：According to a class of nonlinear complementary problems difficult a new evolution algorithm is proposed this algorithm combines with maximum entropy function method.Firstly，the maximum entropy function is used to transform the nonlinear complementary problems into unconstrained optimization problem.Then particle swarm optimization algorithm（PSO） is applied to solving the unconstrained optimization problem.Lastly，computer procedure realization show that the proposed new algorithm has effectiveness.

Keywords：computer realization；nonlinear complementary problem；PSO

1 引言（Introduction）

經(jīng)典的非線性互補問題[1]就是求一個向量使得

互補問題是數(shù)學規(guī)劃的一個基本問題，在工程和經(jīng)濟等領域也有重要應用[3-5]，其算法研究引起廣泛重視[6]：如非光滑法、內(nèi)點法等。內(nèi)點法對單調(diào)的互補問題具有多項式復雜界限，即算法的執(zhí)行時間在最壞的情況下為問題規(guī)模的多項式函數(shù)。但在計算機不易實現(xiàn)，原因是初始點難以找到。非光滑牛頓法是將互補問題通過NCP函數(shù)轉(zhuǎn)化為解方程組的問題，它的奇妙之處在于將包含等式和不等式的三個條件化為只含一個等式的問題，但基于可微的NCP函數(shù)的方程組在退化解處（互補問題（1）的退化解是指對某坐標下標有）的雅可比矩陣是奇異的[7]，這樣牛頓法的局部快速收斂性不再具備?？偟膩碚f，目前這些算法都需要計算梯度，且需要給定初始點，并且針對解不唯一的互補問題，傳統(tǒng)算法無法同時找到多個最優(yōu)解。利用NCP函數(shù)把NCP（F）轉(zhuǎn)化為非線性方程組的方法頗受青睞。如果函數(shù)滿足條件

性質(zhì)3：若二次連續(xù)可微，在光滑，則二階連續(xù)可微且也為二次連續(xù)可微函數(shù)。

對于問題（6）我們采用粒子群優(yōu)化算法[10，11]。粒子群優(yōu)化（Particle Swarm Optimization，簡稱PSO）算法是由kennedy和Eberhart[12]于1995年提出，該方法對優(yōu)化目標函數(shù)的連續(xù)可微性沒有要求，且不需要給定初始點和梯度信息，簡單易行，且收斂速度快，受到國內(nèi)外學者的廣泛關注。

2 粒子群算法（Particle Swarm Optimization algorithm（PSO））

文獻[13]從量子力學角度，在標準PSO基礎上提出量子粒子群算法（，

）。在中，由于粒子滿足聚離態(tài)性質(zhì)不同，粒子在整個可行解空間搜索尋求全局最優(yōu)解。中，粒子群中每個粒子必須收斂于各自的隨機點為粒子維數(shù)，粒子群按式（8）式（11）移動。

其中，為第個粒子在迭代中位置；為第個粒子本身所找到的局部最優(yōu)位置；為整個種群目前找到的全局最優(yōu)位置；為第個粒子最優(yōu)位置中心；都是隨機數(shù)；為收縮擴張系數(shù)，

為粒子當前迭代數(shù)；為種群規(guī)模，為最大迭代代數(shù)。

3 數(shù)值模擬（Numerical Simulation）

為了測試本文算法的求解性能，下面選擇經(jīng)典非線性互補問題，這些算例均來自MCPLIB算例庫，其意義在文獻 [14]中有所闡述。

本文參數(shù)設置如下：，，，程序由matlab編程，并在普通PC機上運行（CPU2.00GHz，內(nèi)存1024MB），算法運行100次，取平均計算結(jié)果。限于篇幅，表1給出其中運行結(jié)果。

4 結(jié)論（Conclusion）

本文提出了混合量子粒子群優(yōu)化算法來求解非線性互補問題。該方法主要是利用進化算法處理優(yōu)化問題，計算結(jié)果更可靠。另外本文算法給求解非線性互補問題提供一種新途徑，對于線性互補問題同樣適用，同時也拓展了群智能優(yōu)化算法適用范圍。數(shù)值實驗表明新算法的有效性。

參考文獻（References）

[1] Harker P T，Pang Js.Finite-dimensional Variational inequality and nonliner complementarity problems， a survey review of theory，algorithms and applications[J].Math Prog，1990：161-220.

[2] F.Facchinei，J.S.Rang，F(xiàn)inite-demensional Variational inequalities and complenentarity problems Spring-Verlag NewYork，Inc.，2003.

[3] F.Faechinei and J-S.Pang，F(xiàn)inite-dimensional variationaline inequalities and complementarity probles，Springer-Verlag，NewYork，2003.endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補問題算法的新進展[J].數(shù)學進展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數(shù)方法[J].計算結(jié)構力學及其應用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡介：

朱鐵鋒（1979-），男，碩士，講師.研究領域：計算數(shù)學，程序?qū)崿F(xiàn).endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補問題算法的新進展[J].數(shù)學進展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數(shù)方法[J].計算結(jié)構力學及其應用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡介：

朱鐵鋒（1979-），男，碩士，講師.研究領域：計算數(shù)學，程序?qū)崿F(xiàn).endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補問題算法的新進展[J].數(shù)學進展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數(shù)方法[J].計算結(jié)構力學及其應用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡介：

朱鐵鋒（1979-），男，碩士，講師.研究領域：計算數(shù)學，程序?qū)崿F(xiàn).endprint