求解非凸半定規劃的非線性拉格朗日函數法補充證明

李 陽，齊淑華，丁淑妍

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

近年來，半定規劃問題(SDP)因其應用范圍十分廣泛而成為優化領域的一個新的研究熱點。人們注意到它可以用來解決組合優化、最優控制、統計學、金融學、工程信號處理、交通管理等很多實際問題［1-2］。于是，研究能夠有效解決半定規劃問題的算法成為現實中生產生活的需要。

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

本文根據一階均差矩陣的定義以及4 種實值函數的特有性質，就上述問題給出詳盡的證明過程，對文獻［7］進行了必要的補充。

1 預備知識

文獻［7］研究了具有如下形式的非凸半定規劃問題:

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

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

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

文獻［7］中構成L?wner 算子的實值函數φ:R→R 要滿足的3 個假設條件如下:

(A1)φ 在(-∞，ω0)上是嚴格凸的，嚴格單調遞增的二次連續可微函數，這里ω0＞0 是一個常數;

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

(A3)對于任意固定的ω ＞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)相關的正數。

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

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

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

2 問題的證明

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

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

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

又因為φMC的有效域是(-∞，1)，所以t-1λ∈(-∞，1)，則可得

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

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

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

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

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

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

在(-∞，+∞)上，顯然φLS是二次連續可微的。φ″LS(t)=＞0，所以φLS(t)是嚴格凸的。φ'LS=2et(1 +et)-1＞0 說明φLS(t)在(-∞，+∞)上是嚴格單調遞增的。易得φ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。又因為對于任意固定的ω ＞0，任取λ，λk，λl∈(-∞，-ω］有

并且

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

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

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

并且，

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

3 結 語

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

［1］BOUD S，GHAOUI EL L，FERON 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..