同倫算法求解二階錐問題

許婷婷

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

1 概述

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

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

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

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

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

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

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

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

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

2 預(yù)備知識

其中ω 為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 二階錐互補問題

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

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

CHKS 光滑化函數(shù)：

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

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

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

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

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

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

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

3 同倫方法描述

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

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

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

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

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

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

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

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

3.2 預(yù)估校正算法

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

算法3.2

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