求解非凸半定規(guī)劃的非線性拉格朗日函數(shù)法補(bǔ)充證明

李 陽，齊淑華，丁淑妍

(大連民族學(xué)院 理學(xué)院，遼寧 大連116605)

近年來，半定規(guī)劃問題(SDP)因其應(yīng)用范圍十分廣泛而成為優(yōu)化領(lǐng)域的一個(gè)新的研究熱點(diǎn)。人們注意到它可以用來解決組合優(yōu)化、最優(yōu)控制、統(tǒng)計(jì)學(xué)、金融學(xué)、工程信號(hào)處理、交通管理等很多實(shí)際問題［1-2］。于是，研究能夠有效解決半定規(guī)劃問題的算法成為現(xiàn)實(shí)中生產(chǎn)生活的需要。

半定規(guī)劃問題主要分為線性半定規(guī)劃和非線性半定規(guī)劃。對(duì)于線性半定規(guī)劃算法的研究，目前的成果已經(jīng)比較豐富了，而對(duì)于非線性半定規(guī)劃問題，主要的求解算法是非線性拉格朗日函數(shù)方法。2003 年，Kocavra 和Stingl 在求解非線性半定規(guī)劃問題的算法研究方面做了大量工作，給出了解決較大規(guī)模問題的一類修正障礙函數(shù)法并給出了數(shù)值程序PENNON［3］。2006 年，Stingl 在他的博士論文中給出了一類非線性拉格朗日函數(shù)法［4］，這項(xiàng)工作為后續(xù)研究奠定了堅(jiān)實(shí)的基礎(chǔ)。隨后，Noll 在2007 年給出了一個(gè)求解非線性半定規(guī)劃問題的具有局部收斂性的增廣拉格朗日函數(shù)法［5］，提出了wedge 收斂的定義，并從新的角度給出了收斂定理證明。另外，Sun，Sun 和Zhang 在2008 年還研究了當(dāng)嚴(yán)格互補(bǔ)條件不成立時(shí)的求解非線性半定規(guī)劃問題的增廣拉格朗日函數(shù)法的收斂速度［6］，在算法理論研究上取得了突破。2013 年，Zhang，Li 和Wu 在文獻(xiàn)［7］中給出了一類求解非凸半定規(guī)劃問題的非線性拉格朗日函數(shù)法的框架，這是一項(xiàng)相對(duì)完整的工作，但是該文獻(xiàn)并沒有證明與構(gòu)成非線性拉格朗日函數(shù)的L?wner算子相關(guān)的4 種具體的實(shí)值函數(shù)是如何滿足假設(shè)條件的，而這些結(jié)論在某種程度上并不是顯然的。

本文根據(jù)一階均差矩陣的定義以及4 種實(shí)值函數(shù)的特有性質(zhì)，就上述問題給出詳盡的證明過程，對(duì)文獻(xiàn)［7］進(jìn)行了必要的補(bǔ)充。

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

文獻(xiàn)［7］研究了具有如下形式的非凸半定規(guī)劃問題:

式中，f:Rn→R，h:Rn→Rq，G:Rn→Sp都是二次連續(xù)可微的，Sp是p ×p 維實(shí)對(duì)稱矩陣構(gòu)成的空間;并構(gòu)造了形式如下的一類非線性拉格朗日函數(shù):

這里t ＞0 是一個(gè)懲罰參數(shù)，在數(shù)值試驗(yàn)取值時(shí)，t往往是一個(gè)很小的數(shù)?！ぁ?代表Frobenius 范數(shù)，〈A，B〉表示矩陣A 和B 的內(nèi)積，Φ 是L?wner算子，且

在這里，diag(μi)，i=1，2，…p 表示以μi為對(duì)角線元素構(gòu)成的對(duì)角陣，對(duì)G(x)做譜分解得

文獻(xiàn)［7］中構(gòu)成L?wner 算子的實(shí)值函數(shù)φ:R→R 要滿足的3 個(gè)假設(shè)條件如下:

(A1)φ 在(-∞，ω0)上是嚴(yán)格凸的，嚴(yán)格單調(diào)遞增的二次連續(xù)可微函數(shù)，這里ω0＞0 是一個(gè)常數(shù);

(A2)φ(0)=0，φ'(0)=1 并且φ″(0)＞0;

(A3)對(duì)于任意固定的ω ＞0，任取λ，λk，λl∈(-∞，-ω］，有|t-1φ［1］(0，t-1λ)|≤c1(ω，λ)，且|t-1φ［1］(t-1λk，t-1λl)|≤c2(ω，λk，λl)，這里c1(ω，λ)和c2(ω，λk，λl)是分別與(ω，λ)和(ω，λk，λl)相關(guān)的正數(shù)。

同時(shí)文獻(xiàn)［7］給出了4 種實(shí)值函數(shù)滿足上述假設(shè)條件，分別為修正的Carroll’s 函數(shù)φMC(t)=(1 -t)-1-1、修正的指數(shù)函數(shù)φME(t)=et-1、Log-Sigmoid 函數(shù)φLS(t)=2(lg(1 +et)-lg2)與函數(shù)φ1(t)=2lg((1 -t)-1+1)-2lg2。這些實(shí)值函數(shù)在研究求解經(jīng)典的非線性規(guī)劃的非線性拉格朗日方法時(shí)，常常被用來構(gòu)造非線性拉格朗日函數(shù)。

為了解釋假設(shè)條件中φ［1］(λk，λl)的定義，我們給出定義。

定義1 實(shí)值函數(shù)φ 在λ∈Rp處的一階均差矩陣記為φ［1］(λ)，它的第k 行第l 列的元素有如下定義:

2 問題的證明

下面分別證明這4 種函數(shù)滿足假設(shè)條件(A1)—(A3)。

證明 (1)修正的Carroll’s 函數(shù)φMC(t)=(1 -t)-1-1。

在(-∞，1)上，顯然φMC是二次連續(xù)可微的。φ″MC(t)=＞0，所以φMC是嚴(yán)格凸的。而且φ'MC=＞0 表明φMC是嚴(yán)格單調(diào)遞增的。易驗(yàn)證φMC(0)=0，φ'MC(0)=1 和φ″MC(0)|t=0=t=0=2 ＞0。又因?yàn)閷?duì)于任意固定的ω ＞0，任取λ，λk，λl∈(-∞，-ω］有

又因?yàn)棣誐C的有效域是(-∞，1)，所以t-1λ∈(-∞，1)，則可得

因此，φMC滿足假設(shè)條件(A1)—(A3)，并且c1(ω，λ)=c2(ω，λk，λl)=ω-1。

(2)修正的指數(shù)函數(shù)φME(t)=et-1。

在(-∞，+∞)上，顯然φME是二次連續(xù)可微的。φ″ME(t)=et＞0，所以φME是嚴(yán)格凸的。并且，φ'ME=et＞0 表明φME是嚴(yán)格單調(diào)遞增的。易得φME(0)=0，φ'ME(0)|t=0=1 和φ″ME(0)|t=0=e0=1 ＞0。又因?yàn)閷?duì)于任意的ω ＞0，任取λ，λk，λl∈(-∞，-ω］有

|t-1(0，t-1λ)|=|t-1(t-1λ，0)|=t-1|=|| ≤| λ-1| ≤ω-1。并且

因此，φME滿足假設(shè)條件(A1)—(A3)，并且c1(ω，λ)=ω-1，c2(ω，λk，λl)=1/|λk-λl|。

(3)Log-Sigmoid 函數(shù)φLS(t)=2(lg(1 +et)-lg2)。

在(-∞，+∞)上，顯然φLS是二次連續(xù)可微的。φ″LS(t)=＞0，所以φLS(t)是嚴(yán)格凸的。φ'LS=2et(1 +et)-1＞0 說明φLS(t)在(-∞，+∞)上是嚴(yán)格單調(diào)遞增的。易得φLS(0)=0，φ'LS(0)|t=0=2|t=0=1 和φ″LS(0)|t=0=2et(1+et)-1-2e2t(1 +et)-2|t=0=＞0。又因?yàn)閷?duì)于任意固定的ω ＞0，任取λ，λk，λl∈(-∞，-ω］有

并且

因此，φLS滿足假設(shè)條件(A1)—(A3)。并且c1(ω，λ)=2lg2ω-1，c2(ω，λk，λl)=。

(4)φ1(t)=2(lg (+1)-lg2)。

在(-∞，1.5)上，顯然φ1是二次連續(xù)可微的且φ″1(t)=＞0，所以φ″1(t)是嚴(yán)格凸的。而且，φ'1=＞0，說明φ1是嚴(yán)格單調(diào)遞增的，易得φ1(0)=0，φ'1(0)|t=0=2=1 和φ″1(0)|t=0=-=＞0。又因?yàn)閷?duì)于任意固定的ω ＞0，任取λ，λk，λl∈(-∞，-ω］有

并且，

因此，φ1滿足假設(shè)條件(A1)—(A3)，并且c1(ω，λ)=2lg2ω-1，c2(ω，λk，λl)=。

3 結(jié) 語

本文在文獻(xiàn)［7］工作的基礎(chǔ)上進(jìn)行補(bǔ)充，借助實(shí)值函數(shù)一階均差矩陣的定義，給出了4 種拉格朗日函數(shù)滿足假設(shè)條件(A1)—(A3)的詳細(xì)證明。當(dāng)然，在求解非凸半定規(guī)劃問題的算法方面還有很多值得關(guān)注的課題。例如，如何給出好的數(shù)值算法來求解實(shí)際中的非凸半定規(guī)劃問題就是一個(gè)值得研究的課題，今后我們將致力于這方面的研究。

［1］BOUD S，GHAOUI EL L，F(xiàn)ERON E，et al. Linear Matrix Inequalities in System and Control Theory ［M］.Philadelphis:Society for Industrial and Applied Mathematics，1994.

［2］JARRE F，WOLKWIEZ H，SAIGAL R. Handbook of Semidefinite Programming:Theory，Algorithm and Applications［M］. New York:Springer-Verlag，2000.

［3］KOCVARA M，STINGL M. PENNON—A code for convex nonlinear and semidefinite programming［J］. Optimization Methods and Software，2003，18:317 -333.

［4］STINGL M. On the solution of nonlinear semidenite programs by augmented lagrangian methods［D］. Aachen:Erlangen University，2006.

［5］NOLL D. Local convergence of an augmented Lagrangian method for matrix inequality constrained progrmming［J］. Optimization Methods and Software，2007，22:777 -802.

［6］SUN D，SUN J，ZHANG L. The rate of convergence of the augmented Lagrangian method for nonlinear semidenite programming［J］. Mathematical Programming，2008，114:349 -391.

［7］ZHANG L，LI Y，WU J. Nonlinear rescaling Lagrangians for nonconvex semidefinite programming［J］. Optimization. 2014，63:(6):899 -920..