廣義非線性互補問題的非光滑牛頓算法＊

李梅霞，田治平

（濰坊學院，山東 濰坊 261061；山東科技職業(yè)學院，山東 濰坊 261053）

廣義非線性互補問題的非光滑牛頓算法＊

李梅霞，田治平

（濰坊學院，山東 濰坊 261061；山東科技職業(yè)學院，山東 濰坊 261053）

研究了一類在多項式錐上的廣義非線性互補問題。借助罰FB互補函數(shù)建立了該類問題的非光滑方程，提出了求解該方程的非光滑牛頓算法，證明了與互補函數(shù)有關的穩(wěn)定點即為廣義非線性互補問題的解。在較弱的條件下給出了牛頓算法的全局和超線性收斂性。

廣義非線性互補問題；罰FB互補函數(shù)；穩(wěn)定點；超線性收斂

1 引言

考慮廣義非線性互補問題（簡記為GNCP（F，G，κ））：尋求向量x＊∈Rn使得

其中F，G：Rn→Rm，κ?Rm為非空閉凸錐，κ0為κ的極錐。

廣義非線性互補問題在工程和經濟中具有廣泛的應用。近幾年來，其理論和算法都得到了較快發(fā)展〔1〕。特別地，當κ＝且G（x）＝x時，廣義非線性互補問題即為傳統(tǒng)的非線性互補問題［2］。

在本文中，我們將考慮一類特殊的廣義非線性互補問題，即m＝n，F(xiàn)和G均為Rn上的連續(xù)可微函數(shù)，κ為Rn上的多項式錐，即存在A∈Rs×n使得

易證κ的極錐為

對于A＝I的情況，文獻［3］中應用一類互補函數(shù)研究了該類問題的解與無約束極小化問題的最優(yōu)解之間的關系。而對于κ＝｛v∈Rn｜Av≥0，Bv＝0｝的情況，文獻［4］中應用FB互補函數(shù)進行了研究，證明了與互補函數(shù)有關的穩(wěn)定點即為廣義互補問題的解。同時給出了求解對應非光滑方程的非光滑L－M方法，證明了算法的全局收斂性和超線性收斂速度。在本文中，我們將應用罰FB函數(shù)［5］研究GNCP（F，G，κ）。眾所周知，罰FB函數(shù)具有許多優(yōu)良性質，借助該類函數(shù)我們建立了GNCP（F，G，κ）的非光滑方程，給出了求解該類方程的非光滑牛頓算法，在算法中我們應用了非單調線搜索，這些都使得算法具有較好的收斂性和較快的收斂速度。理論結果顯示，（a）與互補函數(shù)有關的穩(wěn)定點即為GNCP（F，G，κ）的解；（b）非光滑牛頓算法具有全局和超線性收斂性。

2 預備知識

本部分將給出一些基本概念及其性質。首先引入罰FB函數(shù)。對任意的a，b∈R，φ：R2→R稱為罰FB函數(shù)，其形式為：

其中，x＋＝max｛0，x｝。

對任意的a，b∈Rn，定義

顯然有下式成立

定義向量值函數(shù)Ψρ：Rn＋s→Rn＋s和實值函數(shù)Hρ：Rn＋s→R如下：

Ψρ（x，λ）具有以下性質：

定理1 x＊為GNCP（F，G，κ）的解當且僅當存在λ＊∈Rs，使得Ψρ（x，λ）＝0。

下面的定義和定理在后面的證明中將會用到。

定義1 若n×n矩陣M的每一個主子式都是非負的，則稱矩陣M為P0－矩陣。若n×n矩陣M的每一個主子式都是正的，則稱矩陣M為P-矩陣。

關于P（P0）-矩陣的性質及應用請參見文獻［6］。

對任意的a∈Rn，定義Da＝diag（ai）為第i個對角元素為ai的對角矩陣。根據(jù)文獻［7］中相關定理的證明可得下面的引理。

引理1 （a）設M為P0－矩陣，Da，Db?Rn×n為正定對角矩陣，則矩陣Da＋DbM為非奇異的。

（b）設M為P-矩陣，Da，Db?Rn×n為半正定對角矩陣并且Da＋Db是正定的，則矩陣Da＋DbM為非奇異的。

下面引入半光滑函數(shù)的有關定義和性質。

設Θ：Rn→Rm為一個局部Lipschitz連續(xù)函數(shù)，定義?Θ（x）為Θ（x）在x∈Rn的Clarke廣義雅克比，?Θ（x）可以表示為

定義2［8］設Θ（x）：Rn→Rm是一個局部Lipschitz連續(xù)函數(shù)，若

存在，則稱Θ（x）在x∈Rn是半光滑的。

定義3［8］設Θ（x）：Rn→Rm在x∈Rn是半光滑的并且對任意的V∈?Θ（x＋h）和h→0，有

則稱Θ（x）在x∈Rn是強半光滑的。

引理2［8］設Θ（x）：Rn→Rm是一個局部Lipschitz連續(xù)的半光滑函數(shù)，則

（a）對任意的V∈?Θ（x＋h），h→0，有

（b）對任意的h→0，有

引理3［5］對任意的x∈Rn和λ∈Rs，有

其中，Da（x）＝diag｛ai（x）｝，Db（x）＝diag｛bi（x）｝，ai（x），bi（x）如下所示：

若［λ］2i＋［AF（x）］2i＞0，則

引理4［5］對式（2）和式（3）中定義的向量值函數(shù)Ψρ和實值函數(shù)Hρ，下面的結論成立。

（a）若F和G都是連續(xù)可微的，則Ψρ是半光滑的；若又有F′和G′都是局部Lipschitz的，則Ψρ是強半光滑的。

（b）若F和G都是連續(xù)可微的，則Hp是連續(xù)可微的，并且

其中，V∈?Ψρ（x，λ）。

定義4 設函數(shù)Θ（x）：Rn→Rn，若對任意的x∈Rn，V∈?Θ（x）是非奇異的，則稱Θ（x）是BD正則的。

3 穩(wěn)定點與非奇異性條件

由定理1知，x＊為式（1）的解當且僅當z＊＝（x＊，λ＊）為無約束優(yōu)化問題的全局最優(yōu)值點且最優(yōu)值為0。

定理2 設Z＊＝（X＊，λ＊）為式（4）的穩(wěn)定點，F(xiàn)′（x＊）是非奇異的，并且G′（x＊）［F′（x＊）］－1是正定的，則x＊是GNCP（F，G，κ）的解。

證明：令U＊＝Φρ（AF（x＊），λ＊），V＊＝G（x＊）－ATλ＊，M＊＝G′（x＊）［F′（x＊）］－1

因為z＊＝（x＊，λ＊）是式（4）的穩(wěn)定點，則▽Hρ（z＊）＝0。

由引理3和引理4知

計算可得

已知F′（x＊）非奇異，由式（5）和式（6）得

式（7）的兩端同時左乘V＊T可得

將式（8）代人式（9）得

由引理3知DaDb是半正定的并且已知M＊是正定的，故由式（10）得

將式（11）代入式（7）和式（8）得

由式（11）和式（14）知x＊是GNC（F，G，κ）的解。

定理3 設z＝（x，λ）∈Rn×Rs，若G′（x）是非奇異的，AF′（x）［G′（x）］－1AT是P-陣，則對任意的V∈?Ψρ（z），V是非奇異的并且z是GNCP（F，G，κ）的解。

證明：由于

已知AF′（x）［G′（x）］－1AT是P-陣，根據(jù)引理1知Db＋A［F′（x）G′（x）－1］TATDa是非奇異的，又因為G′（x）是非奇異的，所以VT是非奇異的，即V是非奇異的。

進一步，由引理3知0＝▽Hρ（x，λ）＝VTΨρ（x，λ），故Ψρ（z）＝0，所以z為GNCP（F，G，κ）的解。

4 算法及收斂性分析

在本部分中，我們將給出求解GNCP（F，G，κ）的帶非單調步長的非光滑牛頓算法，并證明它的收斂性和收斂速度。

算法1

Step0 初始化：取z0∈Rn＋s，σ，β，ρ∈（0，1），ε≥0，a＝10，M≥1為正整數(shù)，k：＝0。

Step1 若‖▽Hρ（zk）‖≤ε，停；否則，轉Step2。

Step2 選取Vk∈?Ψρ（zk）。求dk∈Rn＋s滿足下述線性系統(tǒng)，

其中，μk＝‖Ψρ（zk）‖，令α＝a。

下面給出求V∈?Ψρ（z）的算法。

算法2

根據(jù)文獻［4］和文獻［9］中相關定理的證明可得到如下定理。

定理4 設｛zk｝是由算法1產生的序列，則｛zk｝的任何聚點均為式（4）的穩(wěn)定點。

定理5 設｛zk｝是由算法2產生的序列，z＊是｛zk｝的一個聚點并且是Ψρ（z）＝0的BD正則解，則

（a）｛zk｝超線性收斂到z＊。

（b）若F′和G′又是Lipschitz連續(xù)的，則｛zk｝Q－二次收斂到z＊。

［1］Jiang H Y，F(xiàn)ukushima M，Qi L Q，et al.A trust region method for solving generalized complementarity problems［J］.SIAM J Optim，1998，8（1）：140－157.

［2］Facchinei F，Pang J S.Finite－dimensional variational inequalities and complementarity problems［M］.New York：Springer，2003.

［3］Kanzow C，F(xiàn)ukushima M.Equivalence of the generalized complementarity problem to differentiable unconstrained minimization［J］.J Optim Theory Appl，1996，90（3）：581－603.

［4］Wang Y J，Ma F M，Zhang J Z.A nonsmooth L－M method for solving the generalized nonlinear complementarity problem［J］.Appl Math Optim，2005，52（1）：73－92.

［5］Chen B T，Chen X J，Kanzow C.A penalized fischer－burmeister NCP－function［J］.Math Prog，2000，88（1）：211－216.

［6］Cottle R W，Pang J S，Stone R E.The linear complementarity problem［M］.New York：Academic Press，1992.

［7］Kanzow C，Kleinmichel H.A new class of semismooth Newton－type methods for nonlinear omplementarity problems［J］.Comput Optim Appl，1998，11（3）：227－251.

［8］Qi L Q，Sun J.A nonsmooth version of Newton’s method［J］.Math Programming，1993，58（3）：353－367.

［9］Li M X，Wang C Y.Convergence property of gradient－type methods with non－monotone line search in the presence of perturbation［J］.Appl Math Optim，2006，174（2）：854－868.

（責任編輯：肖恩忠）

A Nonsmooth Newton Method for Solving the Generalized Nonlinear Complementarity Problem

LI Mei－xia，TIAN Zhi－ping
（Weifang University，Weifang 261061，China；Shandong Vocational College of Science ＆Technology，Weifang 261053，China）

In this paper，the generalized nonlinear complementarity problem（abbr.GNCP）defined on a polyhedral cone is studied.Based on a penalized FB NCP－function a system of nonsmooth equations is built and the nonsmooth Newton algorithm is presented for solving this system.We prove that the stationary points of the penalized FB merit function are the solution of the GNCP.Under mild assumptions，we show that the Newton algorithm is both globally and superlinearly convergent.

GNCP，penalized FB NCP－function，stationary point，superlinear convergence

2011－04－26

國家自然科學基金資助項目（10901096）；山東省自然科學基金資助項目（ZR2009AL019）

李梅霞（1970－），女，山東高密人，濰坊學院數(shù)學與信息科學學院副教授，博士。研究方向：最優(yōu)化方法及其應用。

O221.2 文獻標識碼：A 文章編號：1671－4288（2011）06－0006－05