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

張襄松，周宏安

（西安工業大學 理學院，西安710021）

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

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

K＝Kn1×Kn2×…×Knm

其中‖·‖表示歐幾里德范數．

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

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

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

1 預備知識

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

可定義若當積

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

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

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

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

譜向量為

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

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

2 預估校正算法

3 收斂性分析

4 數值實驗分析

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

5 結 論

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

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

［2］ HAYASHI S，YAMASHITA N，FUKUSHIMA 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．