非線性互補問題計算機實現

摘 要：分析了非線性互補問題求解困難，利用粒子群算法并結合極大熵函數法給出了該類問題的一種新的有效算法。該算法首先利用極大熵函數將非線性互補問題轉化為一個無約束最優化問題，然后應用粒子群算法來優化該問題，計算機程序實現表明該算法是有效的。

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

中圖分類號：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）

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

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

性質3：若二次連續可微，在光滑，則二階連續可微且也為二次連續可微函數。

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

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

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

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

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

為粒子當前迭代數；為種群規模，為最大迭代代數。

3 數值模擬（Numerical Simulation）

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

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

4 結論（Conclusion）

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

參考文獻（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，Finite-demensional Variational inequalities and complenentarity problems Spring-Verlag NewYork，Inc.，2003.

[3] F.Faechinei and J-S.Pang，Finite-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].數學進展，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] 李興斯.一類不可微優化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數方法[J].計算結構力學及其應用，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-），男，碩士，講師.研究領域：計算數學，程序實現.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].數學進展，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] 李興斯.一類不可微優化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數方法[J].計算結構力學及其應用，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-），男，碩士，講師.研究領域：計算數學，程序實現.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].數學進展，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] 李興斯.一類不可微優化問題的有效解法.中國科學（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問題的凝聚函數方法[J].計算結構力學及其應用，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-），男，碩士，講師.研究領域：計算數學，程序實現.endprint