求解NSOCP 的增廣拉格朗日方法 的局部收斂性分析

張思雨，劉陶文

(湖南大學(xué)數(shù)學(xué)與計(jì)量經(jīng)濟(jì)學(xué)院，湖南 長(zhǎng)沙 410082)

0 引言

二階錐規(guī)劃是在一個(gè)仿射空間和有限個(gè)二階錐的笛卡爾積的交上極小化或極大化一個(gè)線性函數(shù)的問(wèn)題, 其約束是非光滑的,并且是凸的,因此它屬于非光滑凸規(guī)劃。在近幾十年里,隨著線性規(guī)劃和半定規(guī)劃等優(yōu)化問(wèn)題的理論、算法和應(yīng)用的不斷發(fā)展,二階錐規(guī)劃逐漸受到人們的關(guān)注,在設(shè)施選址、工程設(shè)計(jì)等領(lǐng)域得到了廣泛的應(yīng)用[1]。二階錐規(guī)劃包含線性規(guī)劃,同時(shí)又是半定規(guī)劃的特例,因此在求解二階錐規(guī)劃問(wèn)題時(shí),可以將線性規(guī)劃的原始對(duì)偶方法推廣到二階錐規(guī)劃上,也可以將其轉(zhuǎn)化為半定規(guī)劃問(wèn)題,用半定規(guī)劃的相關(guān)算法來(lái)求解,但這樣做,會(huì)使問(wèn)題的維數(shù)大大升高,從而給求解帶來(lái)困難。因此,對(duì)二階錐規(guī)劃問(wèn)題的算法研究是非常必要的,目前求解二階錐規(guī)劃問(wèn)題的算法主要有內(nèi)點(diǎn)法[2,11]、光滑化算法[3,12]、序列二次規(guī)劃法、增廣拉格朗日函數(shù)法等,其中增廣拉格朗日函數(shù)法是最有效的方法之一。

1969 年,Hestenes 和Powell 在求解帶等式約束的非線性規(guī)劃問(wèn)題時(shí),提出了增廣拉格朗日函數(shù)法[4],隨后Rockafellar 將這一方法推廣到了帶有不等式約束的非線性規(guī)劃問(wèn)題上[5],盡管已經(jīng)過(guò)去了將近50 年,增廣拉格朗日方法及其衍生的方法仍然是求解約束優(yōu)化問(wèn)題的核心工具。2004 年,Shapiro 和Sun 在文獻(xiàn)[6]中給出了錐約束條件下增廣拉格朗日函數(shù)的一些性質(zhì),2007 年,Sun 等人在文獻(xiàn)[7]中利用兩個(gè)基本假設(shè)條件,給出了增廣拉格朗日函數(shù)法求解一般約束優(yōu)化問(wèn)題的局部收斂性結(jié)果,并將其應(yīng)用于非凸的非線性半定規(guī)劃問(wèn)題,特別地,這些結(jié)果的獲得并不需要滿足嚴(yán)格互補(bǔ)條件和罰參數(shù)趨于無(wú)窮,從而避免了數(shù)值不穩(wěn)定性和因罰參數(shù)過(guò)大而導(dǎo)致病態(tài)問(wèn)題.考慮如下的非線性二階錐規(guī)劃問(wèn)題(NSOCP)[8]：

1 解NSOCP 的增廣拉格朗日方法

問(wèn)題(1)的拉格朗日函數(shù)定義為：

求解問(wèn)題（1）的增廣拉格朗日方法可以描述如下：

算法1（增廣拉格朗日方法）

步3：更新乘子

則稱在x*處二階充分條件成立。其中且

定義2[9]若在x*處滿足：

則稱在x*處約束非退化條件成立。

定義3 若在x*處滿足：

則稱在x*處嚴(yán)格互補(bǔ)條件成立。

2006 年,Liu 和Zhang 在文獻(xiàn)[10]中,利用二階充分條件、約束非退化條件和嚴(yán)格互補(bǔ)條件證明了求解非線性二階錐規(guī)劃問(wèn)題的增廣拉格朗日方法具有局部收斂性且收斂速度與1/ρ成正比,但嚴(yán)格互補(bǔ)條件通常不容易成立,例如,考慮下面的非線性二階錐規(guī)劃問(wèn)題[3]：

由于x*是最優(yōu)解,故存在使得在處滿足KKT 條件,計(jì)算可得：

經(jīng)驗(yàn)證在x*處強(qiáng)二階充分條件和約束非退化條件均成立,因此,本文我們僅在強(qiáng)二階充分條件和約束非退化條件下分析增廣拉格朗日方法求解非線性二階錐規(guī)劃問(wèn)題的局部收斂性。

2 局部收斂性

首先給出一些在收斂性分析中用到的預(yù)備知識(shí)。

設(shè)X和Y是兩個(gè)有限維的實(shí)Hilbert空間,B是X的一個(gè)開子集,在B上是局部Lipschitz連續(xù)函數(shù),由Rademacher's 定理可知,ψ在B上是幾乎處處F可微的,用表示ψ在B中所有F可微點(diǎn)的集合,則可定義ψ在x∈B處的B次微分：

設(shè)x*是穩(wěn)定點(diǎn),是x*處的拉格朗日乘子,對(duì)任意的映射,定義：

若嚴(yán)格互補(bǔ)條件在x*處不成立,則存在1,2, ,…J的一個(gè)劃分(C,T)使得：

定義C的三個(gè)指標(biāo)集：

定義T的三個(gè)指標(biāo)集：

下面我們將僅在約束非退化條件和強(qiáng)二階充分條件下,證明求解非線性二階錐規(guī)劃問(wèn)題的增廣拉格朗日方法是局部收斂的,且收斂速度與1/ρ成正比,為此,我們需要下面的引理。

引理1[7]令,若約束非退化條件和強(qiáng)二階充分條件在x*處成立,則存在,使得對(duì)任意的,有：

和

其中：

引理2[10]設(shè)是連續(xù)函數(shù),滿足：

基于上述預(yù)備知識(shí)及引理2,我們給出下面一個(gè)重要的結(jié)論,它對(duì)本文的收斂性分析是至關(guān)重要的.

定理1設(shè)x*是非線性二階錐規(guī)劃問(wèn)題（1）的穩(wěn)定點(diǎn),且約束非退化條件和強(qiáng)二階充分條件均在x*處成立,,則有以下結(jié)論成立：

證明：由約束非退化條件在x*處成立,及文獻(xiàn)[4],可知是單點(diǎn)集,故存在是x*處唯一的拉格朗日乘子,即；

令

因此

由強(qiáng)二階充分條件在x*處成立,可知存在使得：

即：

文獻(xiàn)[7]將引理1 和定理1 作為兩個(gè)基本假設(shè)條件,并在此條件下證明了增廣拉格朗日方法求解一般錐約束規(guī)劃問(wèn)題具有局部收斂性,且收斂速度與1/ρ成正比,因此本文只需證明引理1 和定理1 的結(jié)論對(duì)非線性二階錐規(guī)劃問(wèn)題成立,便可以得到增廣拉格朗日方法求解非線性二階錐規(guī)劃問(wèn)題的局部收斂結(jié)果,引理1 的詳細(xì)證明可參考文獻(xiàn)[7].

其中τ是一個(gè)常數(shù),且

由強(qiáng)二階充分條件在x*處成立及式(23)可知,中的每個(gè)元素都是正定的,從而是非奇異的,因此,由文獻(xiàn)[7]可得：存在和局部Lipschitz 連續(xù)函數(shù),使得對(duì)任意的,有

3 結(jié)論

因嚴(yán)格互補(bǔ)條件通常不容易滿足,所以本文在沒(méi)有嚴(yán)格互補(bǔ)條件下研究了增廣拉格朗日函數(shù)法求解非 線性二階錐規(guī)劃問(wèn)題的局部收斂性,利用約束非退化條件和強(qiáng)二階充分條件,得到增廣拉格朗日函數(shù)法求解非線性二階錐規(guī)劃問(wèn)題是局部收斂的,且收斂速度1/ρ成正比,并通過(guò)一個(gè)具體的例子表明這樣做是有意義的,從而使得增廣拉格朗日方法的應(yīng)用范圍更廣。