許婷婷

(南京鐵道職業(yè)技術(shù)學(xué)院社科部,江蘇 南京 210031)

1 概述

在優(yōu)化的研究領(lǐng)域中,有一類基本和重要的優(yōu)化問題- 互補(bǔ)問題(Complementarity Problems)。之所以說這類問題很重要是因?yàn)樵诹W(xué)、交通、經(jīng)濟(jì)、金融、控制等諸多領(lǐng)域的許多實(shí)際問題都最終可以轉(zhuǎn)化成互補(bǔ)問題?；パa(bǔ)問題是指這樣的問題,它包含的兩組決策變量間滿足“互補(bǔ)”關(guān)系,互補(bǔ)關(guān)系反映了變量間存在的一種基本關(guān)系。根據(jù)變量間滿足的條件不同,互補(bǔ)關(guān)系的形式不同,互補(bǔ)問題可以被分為若干不同類型,如線性互補(bǔ)問題、非線性互補(bǔ)問題、二階錐互補(bǔ)問題等。

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

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

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

二階錐互補(bǔ)問題分為線性和非線性兩種,當(dāng)f(z)是線性函數(shù)時(shí),(1)稱為線性二階錐互補(bǔ)問題,當(dāng)f(z)是非線性函數(shù)時(shí),(1)稱為非線性二階錐互補(bǔ)問題；二階錐互補(bǔ)問題有一個(gè)重要的特例就是二階錐規(guī)劃的KKT 優(yōu)化條件。

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

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

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

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

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

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

2.1 光滑函數(shù)

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

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

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

這樣的函數(shù)hμ被稱為是h 的光滑函數(shù)。

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

2.2 二階錐互補(bǔ)問題

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

為此我們給出了CHKS 光滑化函數(shù)。

CHKS 光滑化函數(shù)：

引入光滑化函數(shù)前我們先介紹一個(gè)常用的互補(bǔ)函數(shù)最小值函數(shù)

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

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

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

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

CHKS 光滑化函數(shù)已經(jīng)被成功擴(kuò)展到半定互補(bǔ)和二階錐互補(bǔ)問題中。

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

3 同倫方法描述

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

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

3.1 同倫的構(gòu)造與同倫路徑的存在性和收斂性

現(xiàn)在我們給出二階錐互補(bǔ)問題的同倫方程

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

當(dāng)μ=1 時(shí),同倫方程H(x,1)=0 等價(jià)于x=x0,同時(shí)也是此方程唯一的解。

當(dāng)μ=0 時(shí),同倫方程H(x,0)=0 等價(jià)于φ(x,0)=0,此時(shí)方程與二階錐互補(bǔ)問題的解一致。

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

3.2 預(yù)估校正算法

在本節(jié)我們給出了預(yù)估- 校正算法,并利用它對同倫路徑進(jìn)行跟蹤,它由三個(gè)主要不同的步組成,預(yù)估步,newton 校正步和調(diào)整步長。

算法3.2

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