求解二階錐互補問題的預(yù)估校正算法＊

張襄松，周宏安

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

二階錐互補問題（SOCCP）是指尋找向量x∈Rn使

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

K＝Kn1×Kn2×…×Knm

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

特別地，當ni＝1，（i＝1，…，m）時，二階錐互補問題等價于非線性互補（Nonliear Comple mentarity Problems，NCP）問題．

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

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

1 預(yù)備知識

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

可定義若當積

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

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

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

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

譜向量為

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

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

2 預(yù)估校正算法

3 收斂性分析

4 數(shù)值實驗分析

表1 預(yù)估校正算法對隨機問題的實驗結(jié)果Tab．1 Numerical results of predictor-corrector algorithm for the random problem

5 結(jié) 論

針對單調(diào)的二階錐互補問題，利用對稱擾動的FB光滑函數(shù)，給出了求解該問題的預(yù)估校正算法．與內(nèi)點算法相比，該算法不依賴于初始點的選取，同時證明了算法在迭代過程中能保證迭代點列在給定的鄰域內(nèi)且不需要額外運算．如果迭代點列滿足非奇異假設(shè)，則該算法是全局收斂和局部二次收斂的．實驗結(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．