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

袁柳洋，唐秋華，賈世會

(1.武漢科技大學理學院，湖北 武漢，430065；2.武漢科技大學機械自動化學院，湖北 武漢，430081 )

?

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

袁柳洋1，唐秋華2，賈世會1

(1.武漢科技大學理學院，湖北 武漢，430065；2.武漢科技大學機械自動化學院，湖北 武漢，430081 )

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

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

1問題描述

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

(1)

式中：F(x)∶Rn→Rn是一個非線性向量函數(shù)。若F(x)=Mx+q, 其中M∈Rn×n,q∈Rn, 則NCP(F)被稱為線性互補問題, 簡寫為LCP(M,q)。若F是P0函數(shù)，即對任意的u,v∈Rn,u≠v, 存在下標k(1≤k≤n), 使得

(2)

同時成立, 則稱NCP(F)為非線性P0互補問題。

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

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

2非線性P0互補問題的轉(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)化問題:

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

(11)

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

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

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

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

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

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

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

(1)z*是P(z,z*)的一個嚴格局部極大點;

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

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

(12)

式中：z*是問題(11)的當前局部極小點；對r>0,hr(t)定義為

(13)

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

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

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

因此,z*是F(z,z*)的嚴格極大點。

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

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

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

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

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

4算法描述

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

(14)

本文算法簡稱為APPF，具體步驟如下。

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

步驟2令

其中，

置l∶=1和λ∶=1。

步驟3

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

(15)

APPF算法的主要思想是：

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

當n≥3時, 取K=2n,這時，當i=1,…,n時,ei中的第i個分量為1, 其他分量為0；當i=n+1,…,K時,ei中的第i個分量為-1, 其他分量為0。

5算法驗證

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

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

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

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

注：t為找到第k個局部極小點時所需要的CPU時間。

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

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

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

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

注：t為找到第k個局部極小點時所需要的CPU時間。

6結(jié)語

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

參考文獻

[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.

[責任編輯尚晶]

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

基金項目：國家自然科學基金青年科學基金項目(11401450，11401126)；國家自然科學基金面上項目(51275366).

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

中圖分類號：O224

文獻標志碼：A

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