同倫算法求解二階錐問題

許婷婷

(南京鐵道職業技術學院社科部,江蘇 南京 210031)

1 概述

在優化的研究領域中,有一類基本和重要的優化問題- 互補問題(Complementarity Problems)。之所以說這類問題很重要是因為在力學、交通、經濟、金融、控制等諸多領域的許多實際問題都最終可以轉化成互補問題。互補問題是指這樣的問題,它包含的兩組決策變量間滿足“互補”關系,互補關系反映了變量間存在的一種基本關系。根據變量間滿足的條件不同,互補關系的形式不同,互補問題可以被分為若干不同類型,如線性互補問題、非線性互補問題、二階錐互補問題等。

二階錐互補問題(SOCCP)是互補問題中的一種,是一類比二階錐規劃問題(SOCP)更廣的均衡優化問題,最常見的SOCCP的一般模型是：尋找向量z∈Rn,使得

其中f:Rn→Rn是一個連續可微映射,<·,·>表示向量的內積,K?Rn是有限個二階錐的笛卡爾積,即：

其中||.||表示歐幾里得2- 范數。顯然當n1=n2=…=nm=1 時這里的二階錐互補問題(SOCCP)等價于非線性互補問題(NCP)。

二階錐互補問題分為線性和非線性兩種,當f(z)是線性函數時,(1)稱為線性二階錐互補問題,當f(z)是非線性函數時,(1)稱為非線性二階錐互補問題；二階錐互補問題有一個重要的特例就是二階錐規劃的KKT 優化條件。

近些年來,二階錐互補問題在應用方面在發揮其巨大的作用,比如,二階錐優化被應用于求解帶噪聲數據和丟失數據的支持向量機,組合優化,工程設計,凸網絡流問題,等。也因此吸引了國內外一些學者對二階錐互補問題的研究興趣,二階錐互補問題[1]包括二次約束問題、二階錐規劃的最優性問題、和一般的非線性互補性問題。關于SOCCP 的研究,在理論研究和算法實現方面都取得了突破性進展,算法方面, 近幾年出現了一些求解SOCCP 的新算法,代表性的有:光滑算法[2]、效益函數法[3,4]、半光滑算法[5,6]等。本文獻使用了同倫方法對二階錐互補問題進行求解,將本文的二階錐互補問題利用光滑化函數將其轉換為一個與之等價的非線性方程組, 然后用求解非線性方程組的方法間接對其進行求解,從而得到二階錐互補問題的光滑化同倫方法。

同倫方法基本思想用數學語言可以表述為：首先,我們通過求解下面的非線性方程組來闡述同倫方法的基本思想,非線性方程組如下：

其中F(x)是光滑函數。

則在一定的條件下,同倫方程H(x,μ)=0 的解定義了一條從(x0,1)出發趨向于超平面μ=0 的光滑曲線。該曲線另一端的任一極限點x 的分量x*是F(X)=0 的解,這就是同倫方法。

2 預備知識

其中ω 為Rk-1中任意滿足||ω||=1 的向量,λ1,λ2是向量x 的譜值,u(1),u(2)是x 的譜向量。

2.1 光滑函數

其中?φ(.)表示φ 的廣義雅克比矩陣。

光滑函數是半光滑函數的一種特殊情況,不可微函數的光滑函數的概念最早由Hayashi,Yamashita 和Fukushim[9]提出。

定義2.2[10]對于不可微函數h:Rn→Rm則帶參數μ>0 的函數hμ:Rn→Rm具有下述性質：

這樣的函數hμ被稱為是h 的光滑函數。

接下來的定義在本節也有很重要的作用。

2.2 二階錐互補問題

本節我們來討論二階錐互補問題的模型：尋找x,y∈Rn使得

為此我們給出了CHKS 光滑化函數。

CHKS 光滑化函數：

引入光滑化函數前我們先介紹一個常用的互補函數最小值函數

在文獻[11]中證明了φmin(a,b)滿足：

然而φmin(a,b)是非光滑函數。

在這之后B. Chen, P. T. Harker, C. Kanzow and S. Smale

[9]首次提出了對稱擾動技巧,通過光滑化對稱擾動函數將φmin(a,b)函數轉化為著名的CHKS 光滑化函數：

CHKS 光滑化函數已經被成功擴展到半定互補和二階錐互補問題中。

令y=f(x),可知我們本文提到的二階錐互補問題等價于以下非線性等式

3 同倫方法描述

構造同倫映射H(x,t):Ω×[0,1]→Rn有以下原則：對于想要求解的非線性方程φ(x)=0,要選擇一個易于求解的方程g(x)使得

其中φ(x)是光滑函數,

3.1 同倫的構造與同倫路徑的存在性和收斂性

現在我們給出二階錐互補問題的同倫方程

其中x,x0∈Rn,μ∈(0,1].對此(x0,1)是同倫路徑上的一個已知點,并且從這個已知點出發跟蹤這條路徑,即作為路徑跟蹤算法的初始點,當μ→0 時,同倫路徑收斂到(4)式的解,相應的就可以求出該二階錐互補問題的解。對?x∈,H(x, μ)的零點集為

當μ=1 時,同倫方程H(x,1)=0 等價于x=x0,同時也是此方程唯一的解。

當μ=0 時,同倫方程H(x,0)=0 等價于φ(x,0)=0,此時方程與二階錐互補問題的解一致。

定理3.1(參數化scard 定理)[12]假設U?,V?是兩個開集,F:U×V→Rm是一個Cr映射,其中r>max{0,n-m}如果0∈Rm是F 的一個正則值,則對于幾乎所有的a∈V,0 是F(0,a)的一個正則值。

3.2 預估校正算法

在本節我們給出了預估- 校正算法,并利用它對同倫路徑進行跟蹤,它由三個主要不同的步組成,預估步,newton 校正步和調整步長。

算法3.2

在算法中,從(x0,1)出發,跟蹤曲線Γ,直到μ=0 這個過程中曲線Γ 的一個點有兩個切向量(如圖1),若選擇負方向,則算法執行到最后必會回到初始點(x0,1),而不可能到達目標映射的零點(x*,0),因此我們沿著正方向。