張襄松，周宏安

（西安工業(yè)大學(xué) 理學(xué)院，西安710021）

二階錐互補(bǔ)問(wèn)題（SOCCP）是指尋找向量x∈Rn使

成立，其中〈·，·〉表示歐幾里德內(nèi)積，f是連續(xù)可微映射．K是二階錐上的笛卡爾積，即

K＝Kn1×Kn2×…×Knm

其中‖·‖表示歐幾里德范數(shù)．

特別地，當(dāng)ni＝1，（i＝1，…，m）時(shí)，二階錐互補(bǔ)問(wèn)題等價(jià)于非線性互補(bǔ)（Nonliear Comple mentarity Problems，NCP）問(wèn)題．

在研究二階錐規(guī)劃的庫(kù)恩-塔克條件（Karush Kunh Tucker Conditions，KKT）和許多實(shí)際問(wèn)題時(shí)，經(jīng)常會(huì)面臨二階錐互補(bǔ)問(wèn)題［1-2］，因此給出可行有效的方法來(lái)求解二階錐互補(bǔ)問(wèn)題成為近年來(lái)的研究熱點(diǎn)之一．類似于非線性互補(bǔ)問(wèn)題和半定互補(bǔ)問(wèn)題［3-4］，一個(gè)途徑就是基于一個(gè)適合的互補(bǔ)函數(shù)將其轉(zhuǎn)化為Rn上的某個(gè)價(jià)值函數(shù)的無(wú)約束最小化問(wèn)題或一個(gè)非線性方程組來(lái)求解．目前，求解這類問(wèn)題方法主要有內(nèi)點(diǎn)算法、光滑方法等．其中由于內(nèi)點(diǎn)算法在求解許多數(shù)學(xué)規(guī)劃問(wèn)題時(shí)都被證明具有多項(xiàng)式計(jì)算復(fù)雜性，使得該算法在求解尤其是大規(guī)模優(yōu)化問(wèn)題具有優(yōu)勢(shì)，但是現(xiàn)有的內(nèi)點(diǎn)算法對(duì)初始點(diǎn)的選取卻相對(duì)苛刻，一般要求初始點(diǎn)是嚴(yán)格可行的，然而對(duì)許多實(shí)際問(wèn)題，找到嚴(yán)格可行的初始點(diǎn)并不容易．而近年來(lái)由于良好的性能而受到關(guān)注的光滑方法，則可以彌補(bǔ)這種不足：光滑化方法對(duì)初始點(diǎn)的選取沒(méi)有嚴(yán)格要求，并且在算法實(shí)施的過(guò)程中，也不需要內(nèi)點(diǎn)的限制，因此，光滑化方法成為求解優(yōu)化問(wèn)題特別是互補(bǔ)問(wèn)題的一種頗受青睞的方法．求解二階錐互補(bǔ)問(wèn)題方法主要有內(nèi)點(diǎn)算法、光滑方法等．內(nèi)點(diǎn)算法是求解二階錐規(guī)劃的一類非常重要的算法，這類算法的優(yōu)點(diǎn)在于它具有多項(xiàng)式計(jì)算復(fù)雜性，適合于大規(guī)模問(wèn)題的計(jì)算，但是現(xiàn)有的內(nèi)點(diǎn)算法大多數(shù)要求初始點(diǎn)是嚴(yán)格可行的，然而許多實(shí)際問(wèn)題難以直接找到嚴(yán)格可行的初始點(diǎn)．另一方面，近年來(lái)出現(xiàn)的光滑方法，由于其良好的性能而受到優(yōu)化問(wèn)題研究者的極大關(guān)注，這類方法與內(nèi)點(diǎn)法不同的是光滑化方法可以任意選取初始點(diǎn)，并且在算法實(shí)施的過(guò)程中，不需要內(nèi)點(diǎn)的限制，因此，光滑化方法成為求解優(yōu)化問(wèn)題特別是互補(bǔ)問(wèn)題的一種頗受青睞的方法．

本文通過(guò)對(duì)Fischer-Burmeister互補(bǔ)函數(shù)進(jìn)行對(duì)稱擾動(dòng)，得到了一個(gè)新的光滑函數(shù)，利用得到的光滑函數(shù)，把二階錐互補(bǔ)問(wèn)題轉(zhuǎn)化為一個(gè)非線性方程組問(wèn)題，給出求解單調(diào)二階錐互補(bǔ)問(wèn)題的預(yù)估校正光滑算法．文中所有向量均為列向量，R＋＋表示非負(fù)實(shí)數(shù)集，T表示向量或矩陣的轉(zhuǎn)置，I表示一個(gè)適當(dāng)維數(shù)的單位矩陣．可微函數(shù)f：Rn→Rn在點(diǎn)x的梯度記作▽f（x）．intK表示K的內(nèi)部，x?y表示x-y∈intK．

1 預(yù)備知識(shí)

若當(dāng)代數(shù)是研究二階錐問(wèn)題的有力工具［1］．在若當(dāng)代數(shù)J中，對(duì)任意向量

可定義若當(dāng)積

x＋y表示通常意義下的加法．給定若當(dāng)代數(shù)中一個(gè)向量x，定義一個(gè)對(duì)稱矩陣

其中I表示n-1階的單位陣．

定理1 （譜分解定理［1］）

對(duì)向量x＝ （x1，x2）∈R×Rn-1，與二階錐相伴的譜分解定義為x＝λ1u（1）＋λ2u（2）．其中

譜向量為

下面給出任意一個(gè)向量x的譜分解的基本性質(zhì)．

性質(zhì)1 對(duì)任意向量x∈Rn，它的譜值λ1，λ2和譜向量u（1），u（2）分別由式（2）和式（3）給出．則

2 預(yù)估校正算法

3 收斂性分析

4 數(shù)值實(shí)驗(yàn)分析

表1 預(yù)估校正算法對(duì)隨機(jī)問(wèn)題的實(shí)驗(yàn)結(jié)果Tab．1 Numerical results of predictor-corrector algorithm for the random problem

5 結(jié) 論

針對(duì)單調(diào)的二階錐互補(bǔ)問(wèn)題，利用對(duì)稱擾動(dòng)的FB光滑函數(shù)，給出了求解該問(wèn)題的預(yù)估校正算法．與內(nèi)點(diǎn)算法相比，該算法不依賴于初始點(diǎn)的選取，同時(shí)證明了算法在迭代過(guò)程中能保證迭代點(diǎn)列在給定的鄰域內(nèi)且不需要額外運(yùn)算．如果迭代點(diǎn)列滿足非奇異假設(shè)，則該算法是全局收斂和局部二次收斂的．實(shí)驗(yàn)結(jié)果表明算法是可行且有效的．

［1］ ALIZADEH F，GOLDFARB D．Second-order Cone Programming［J］．Mathematical Programming，2003，95（1）：3．

［2］ HAYASHI S，YAMASHITA N，F(xiàn)UKUSHIMA M．Robust Nash Equilibria and Second Order Cone Complementarity Problems［J］．Journal of Nonlinear and Convex Analysis，2005，6（2）：283．

［3］ CHEN X，TSENG P．Non-Interior Continuous Methods for Solving Semidefinite Complementarity Problems［J］．Mathematical Programming，2003，95（3）：431．

［4］ HUANG Z H，HAN J Y，CHEN Z W．Predictor-Corrector Smoothing Newton Method Based on a New Smoothing Function for Solving the Nonlinear Complementarity［J］．Journal of Optimization Theory and Applications，2003，117（1）：39．

［5］ SUN D F，SUN J．Strong Semismoothness of Fischer-Burmeister SDC and SOC Complementarity Functions［J］．Mathematical Programming，2005，103（3）：575．

［6］ HUANG Z H，SUN D F，ZHAO G Y．A Smoothing Newton-Vtype Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming［J］．Computational Optimization and Applications，2006，35（2）：199．

［7］ FUKUSHIMA M，LUO Z Q，TSENG P．Smoothing Functions for Second-order Cone Complementarity Problems［J］．SIAM Journal on Optimization，2001，12（2）：436．

［8］ ZHANG X S，LIU S Y，LIU Z H．A Regularization Smoothing Method for Second-order Cone Complementarity Problem ［J］．Nonlinear Analysis：Real World Applications，2011，12（1）：731．