袁柳洋，唐秋華，賈世會(huì)

(1.武漢科技大學(xué)理學(xué)院，湖北 武漢，430065；2.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院，湖北 武漢，430081 )

?

求解非線性P0互補(bǔ)問(wèn)題的填充函數(shù)法

袁柳洋1，唐秋華2，賈世會(huì)1

(1.武漢科技大學(xué)理學(xué)院，湖北 武漢，430065；2.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院，湖北 武漢，430081 )

摘要：首先利用光滑F(xiàn)ischer-Burmeister函數(shù), 將非線性P0互補(bǔ)問(wèn)題轉(zhuǎn)化成相應(yīng)的約束優(yōu)化問(wèn)題；然后對(duì)此約束優(yōu)化問(wèn)題構(gòu)造出一種新的無(wú)參數(shù)的填充函數(shù), 討論了該填充函數(shù)的有關(guān)性質(zhì)，并提出了求解非線性P0互補(bǔ)問(wèn)題的填充函數(shù)算法。通過(guò)幾個(gè)數(shù)值算例驗(yàn)證了該算法的有效性。

關(guān)鍵詞：非線性互補(bǔ)問(wèn)題；P0函數(shù)；Fischer-Burmeister函數(shù)；填充函數(shù); 局部極小點(diǎn);全局極小點(diǎn)

1問(wèn)題描述

本文考慮如下形式的非線性互補(bǔ)問(wèn)題(簡(jiǎn)寫為NCP(F)):找到一個(gè)向量x*∈Rn, 滿足

(1)

式中：F(x)∶Rn→Rn是一個(gè)非線性向量函數(shù)。若F(x)=Mx+q, 其中M∈Rn×n,q∈Rn, 則NCP(F)被稱為線性互補(bǔ)問(wèn)題, 簡(jiǎn)寫為L(zhǎng)CP(M,q)。若F是P0函數(shù)，即對(duì)任意的u,v∈Rn,u≠v, 存在下標(biāo)k(1≤k≤n), 使得

(2)

同時(shí)成立, 則稱NCP(F)為非線性P0互補(bǔ)問(wèn)題。

非線性P0互補(bǔ)問(wèn)題是單調(diào)互補(bǔ)問(wèn)題和P函數(shù)互補(bǔ)問(wèn)題的推廣, 近年來(lái)受到許多學(xué)者的關(guān)注。求解非線性P0互補(bǔ)問(wèn)題最常用的方法是牛頓法[1-2]、磨光算法[3]等， 而本文將提出另外一種求解方法——填充函數(shù)法。

在大多數(shù)求解非線性P0互補(bǔ)問(wèn)題的算法中, 最普遍的做法是先通過(guò)NCP函數(shù)將非線性P0互補(bǔ)問(wèn)題轉(zhuǎn)化成一個(gè)方程組, 然后再用求解方程組的方法間接求解。本文則首先利用NCP函數(shù)中的光滑F(xiàn)ischer-Burmeister函數(shù), 將非線性P0互補(bǔ)問(wèn)題轉(zhuǎn)化成相應(yīng)的約束優(yōu)化問(wèn)題,然后根據(jù)填充函數(shù)的定義, 對(duì)此約束最優(yōu)化問(wèn)題構(gòu)造出一種新的無(wú)參數(shù)的填充函數(shù), 并分析討論該填充函數(shù)的有關(guān)性質(zhì)，最后建立求解非線性P0互補(bǔ)問(wèn)題的填充函數(shù)算法。

2非線性P0互補(bǔ)問(wèn)題的轉(zhuǎn)化

minθ(x)

(3)

并且θ()=0。

(4)

式中：x=(x1,…,xn)T；F(x)=(F1(x),…,Fn(x))T。

(5)

否則, θ定義為

(6)

NCP函數(shù)有很多種, 其中非常重要的一種是Fischer-Burmeister函數(shù):

(7)

(8)

令

(9)

并定義

(10)

顯然H(z)=0?μ=0,x是NCP(F)的解。

上述方程組又可轉(zhuǎn)化為如下的約束優(yōu)化問(wèn)題:

minf(z)=‖H(z)‖2

(11)

式中：‖·‖2為歐幾里得范數(shù)；X={(μ,x)|μ>0,x∈Rn}。

若x*是NCP(F)的一個(gè)解, 當(dāng)且僅當(dāng)z*是問(wèn)題(11)的全局最優(yōu)解且最優(yōu)值f(z*)=0。

3填充函數(shù)的構(gòu)造及其性質(zhì)分析

考慮問(wèn)題(11), 在本文中做如下假設(shè)。

假設(shè)2NCP(F)的解集非空且有界。

下面給出填充函數(shù)的定義。

定義3[4]函數(shù)P(z,z*)被稱為f(z)在局部極小點(diǎn)z*處的填充函數(shù), 如果它滿足:

(1)z*是P(z,z*)的一個(gè)嚴(yán)格局部極大點(diǎn);

(2)對(duì)任意的z∈S1, 有P(z,z*)≠0, 其中S1={z|f(z)≥f(z*),z∈X{z*}};

不少研究人員[4-11]提出的填充函數(shù)都具有一個(gè)或兩個(gè)參數(shù), 而在實(shí)際計(jì)算中, 這些填充函數(shù)參數(shù)必須滿足一些條件才能符合其定義，而這將大大增加計(jì)算量。文獻(xiàn)[5]中指出, 要克服其所提出的填充函數(shù)的缺陷,有一種方法是構(gòu)造單參數(shù)或無(wú)參數(shù)的填充函數(shù)。本文據(jù)此提出了一種新的無(wú)參數(shù)的填充函數(shù):

(12)

式中：z*是問(wèn)題(11)的當(dāng)前局部極小點(diǎn)；對(duì)r>0,hr(t)定義為

(13)

以下的定理表明F(z,z*)滿足填充函數(shù)的定義3。

定理1若z*∈X滿足f(z*)>0, 則z*是F(z,z*)的嚴(yán)格極大點(diǎn)。

證明：由于當(dāng)t∈R時(shí), 0≤hr(t)≤1, 則由F(z,z*)的定義, 可得

因此,z*是F(z,z*)的嚴(yán)格極大點(diǎn)。

定理1表明F(z,z*)滿足定義3的條件(1)。

定理2若z*∈X滿足f(z*)>0, 則對(duì)任意的z∈S1={z|f(z)≥f(z*),z∈X{z*}} , 有F(z,z*)≠0。

因此，對(duì)任意的z∈S1, 有F(z,z*)≠0。

定理2表明F(z,z*) 滿足定義3的條件(2)。

定理3表明F(z,z*)滿足定義3的條件(3)。

4算法描述

考慮如下的填充函數(shù)問(wèn)題:

(14)

本文算法簡(jiǎn)稱為APPF，具體步驟如下。

步驟0選擇足夠小的正數(shù)λL；選擇一個(gè)正整數(shù)K和方向ei,i=1,…,K；選擇一個(gè)初始點(diǎn)z0∈X；置k∶=0。

步驟2令

其中，

置l∶=1和λ∶=1。

步驟3

(a) 若l≤K, 轉(zhuǎn)(b); 否則, 轉(zhuǎn)步驟5。

(15)

APPF算法的主要思想是：

(1)按以下方法選取步驟0中的方向ei。例如,當(dāng)n=2時(shí), 取K=6n,方向ei被選為

當(dāng)n≥3時(shí), 取K=2n,這時(shí)，當(dāng)i=1,…,n時(shí),ei中的第i個(gè)分量為1, 其他分量為0；當(dāng)i=n+1,…,K時(shí),ei中的第i個(gè)分量為-1, 其他分量為0。

5算法驗(yàn)證

例1NCP(F)中的函數(shù)F由下式給出：

該函數(shù)是P0函數(shù), 它有唯一的解(2,0,1,0)T, 取μ的初值μ0=0.1。

例1的數(shù)值計(jì)算結(jié)果見(jiàn)表1。由表1可知, 兩種算法的計(jì)算結(jié)果相同, 但本文APPF算法所需要的CPU時(shí)間更短。

表1　例1的數(shù)值計(jì)算結(jié)果

注：t為找到第k個(gè)局部極小點(diǎn)時(shí)所需要的CPU時(shí)間。

例2NCP(F)中的函數(shù)F由下式給出：

例2的數(shù)值計(jì)算結(jié)果見(jiàn)表2。同樣,APPF算法與AOPF算法的計(jì)算結(jié)果相同, 但前者所花CPU時(shí)間更少。

由以上算例可推知, 采用APPF算法和AOPF算法可得到相同的數(shù)值結(jié)果, 但大多數(shù)情況下前者的計(jì)算效率更高。這是因?yàn)?，一般?lái)說(shuō)判斷目前的點(diǎn)是全局極小點(diǎn)比找到全局極小點(diǎn)更花時(shí)間。

表2　例2的數(shù)值計(jì)算結(jié)果

注：t為找到第k個(gè)局部極小點(diǎn)時(shí)所需要的CPU時(shí)間。

6結(jié)語(yǔ)

本文首先通過(guò)光滑的Fischer-Burmeister函數(shù), 將非線性P0互補(bǔ)問(wèn)題轉(zhuǎn)化為相應(yīng)的約束優(yōu)化問(wèn)題(11)。然后根據(jù)填充函數(shù)的定義, 對(duì)問(wèn)題(11) 構(gòu)造出了一種無(wú)參數(shù)的填充函數(shù)F(z，z*),分析討論了該填充函數(shù)的有關(guān)性質(zhì)。最后構(gòu)造了求解非線性P0互補(bǔ)問(wèn)題的填充函數(shù)算法, 并對(duì)該算法進(jìn)行了數(shù)值實(shí)驗(yàn)。針對(duì)所給的兩個(gè)算例，本文APPF算法和文獻(xiàn)[6]中AOPF算法雖有同樣的數(shù)值結(jié)果，但APPF算法所使用的CPU時(shí)間更少，因此該填充函數(shù)算法是有效的。

參考文獻(xiàn)

[1]Huang N, Ma C F. The numerical study of a regularized smoothing Newton method for solvingP0-NCP based on the generalized smoothing Fischer-Burmeister function[J].Applied Mathematics and Computation, 2012, 218: 7253-7269.

[2]Zhang L P, Wu S -Y, Gao T R. Improved smoothing Newton methods forP0nonlinear complementarity problems[J]. Applied Mathematics and Computation, 2009, 215: 324-332.

[3]Zhu J G, Liu H W, Li X L. A regularized smoothing-type algorithm for solving a system of inequalities with aP0-function[J]. Journal of Computational and Applied Mathematics, 2010, 233:2611-2619.

[4]Yang Y J, Shang Y L. A new filled function method for unconstrained global optimization[J]. Applied Mathematics and Computation, 2006, 173: 501-512.

[5]Ge R P. A filled function method for finding a global minimizer of a function of several variables[J]. Mathematical Programming, 1990, 46: 191-204.

[6]Yuan L Y, Wan Z P, Zhang J J, et al. A filled function method for solving nonlinear complementarity problem[J]. Journal of Industrial and Management Optimization, 2009, 5(4): 911-928.

[7]Zhang L S, Ng C-K, Li D, et al. A new filled function method for global optimization[J]. Journal of Global Optimization, 2004, 28:17-43.

[8]Xu Z, Huang H-X, Pardalos P M, et al. Filled functions for unconstrained global optimization[J]. Journal of Global Optimization, 2001, 20:49-65.

[9]Liu H W, Gao Y L，Wang Y P. A continuously differentiable filled function method for global optimization[J]. Numerical Algorithms, 2014, 66: 511-523.

[10]Wei F, Wang Y P，Lin H W. A new filled function method with two parameters for global optimization[J]. Journal of Optimization Theory and Applications, 2014, 163: 510-527.

[11]Yuan L Y, Wan Z P, Tang Q H. A criterion for an approximation global optimal solution based on the filled functions[J]. Journal of Industrial and Management Optimization, 2016, 12(1): 375-387.

[責(zé)任編輯尚晶]

A filled function method for nonlinearP0complementarity problems

YuanLiuyang1，TangQiuhua2，JiaShihui1

(1.College of Science, Wuhan University of Science and Technology, Wuhan 430065, China；2. College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China)

Abstract:Firstly, the nonlinear P0 complementarity problem is converted into a corresponding constrained optimization problem by using the smoothing Fischer-Burmeister function. Subsequently, a novel parameter-free filled function is constructed for the constrained optimization problem,and the function’s properties are also discussed. A filled function algorithm is proposed to solve the nonlinear P0 complementarity problem, and its validity is verified by several numerical examples.

Key words：nonlinear complementarity problem; P0 function; Fischer-Burmeister function; filled function; local minimizer; global minimizer

收稿日期：2016-01-21

基金項(xiàng)目：國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(11401450，11401126)；國(guó)家自然科學(xué)基金面上項(xiàng)目(51275366).

作者簡(jiǎn)介：袁柳洋(1988-)，女，武漢科技大學(xué)講師，博士. E-mail:yangly0601@126.com通訊作者：唐秋華(1971-)，女，武漢科技大學(xué)教授，博士生導(dǎo)師. E-mail:tangqiuhua@wust.edu.cn

中圖分類號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-3644(2016)03-0236-05