約束優化問題的序列近似方法收斂性

段 慶 松

( 大連理工大學 數學科學學院, 遼寧 大連　116024 )

?

約束優化問題的序列近似方法收斂性

段 慶 松*

( 大連理工大學 數學科學學院, 遼寧 大連116024 )

摘要：對抽象約束優化問題的序列近似方法的收斂性進行討論，證明了在目標函數序列連續收斂和約束集合序列收斂的條件下，序列近似問題的全局最優值收斂到原問題的最優值．進一步，證明了在序列近似問題目標函數和約束集合具有某些單調性質的前提下，把目標函數序列連續收斂減弱到上圖收斂，該結論仍然成立．最后，將這一結果用于分析互補約束優化問題的光滑化方法的收斂性中．

關鍵詞：連續收斂；上圖收斂；全局最優解；互補約束優化

0引言

Rockafellar等[1]1998年在著作Variational Analysis中討論了很重要的集值映射和函數列的收斂問題，其中集合序列的極限是集值映射的極限與連續性的基礎，集值映射序列的收斂包含了逐點收斂、圖收斂、連續收斂、一致收斂，函數列的收斂有逐點收斂、連續收斂、上圖收斂、一致收斂等．隨著對更多的關于收斂問題的深入了解，這些序列收斂在約束優化近似方法中的應用越來越重要．Mordukhovich[2-3]也給出了關于集值映射序列很多重要的性質．

考慮下面的約束優化問題：

若存在ε>0使得

為了得到問題(P)的最優解，往往需要驗證下面的最優必要性條件：

0∈f(x)+N(x)

f(x)、N(x

目前，學者們對問題(P)的求解方法已經有了很多研究，例如罰函數方法、內點法、增廣拉格朗日法、序列二次規劃方法等，想要了解非線性問題的求解方法可以參考文獻[7]等．在許多問題中，都要用到序列近似方法來解決，即遇到復雜難以求解的問題時，往往用一系列性質簡單且容易解決的問題來近似原問題，Hong等[8]運用序列凸近似方法解決了復雜的DC問題，而在一般情況下，通常考慮序列問題：

其中v∈N是自然數序列．問題(Pv)通常是一列容易求解的近似問題，然而為了得到原問題(P)的最優值，近似問題序列(Pv)需要滿足一定的條件，即問題(Pv)的最優值收斂到問題(P)的最優值．很多文獻都考慮了這個條件．如文獻[1]中有如下定理：

若滿足上述定理中的條件，則可通過對序列問題(Pv)的求解來得到原問題(P)的最優值．本文將會基于此定理，進一步考慮序列問題(Pv)與原問題(P)的最優值之間的關系．

1預備知識

在本章中介紹一些將要用到的定義和基本結果．

定義1[1](內外極限的定義)

(1)

(2)

如果內極限與外極限相等，則稱序列的極限C存在，

(3)

定義2[1](連續收斂) 函數列fv連續收斂到f，若當xv→x，有fv(xv)→f(x)．

定義3[1](上圖) 對于函數f:Rn→R，f的上圖是集合

epif∶={(x，α)∈Rn×R:α≥f(x)}

定義4[1](上圖收斂) 設{fv}是定義在Rn上的函數序列，x是Rn中的一點，則

定義5[1](有效域) 對于函數f:X→R，它的有效域定義為

domf∶={x∈X:f(x)<∞}

(4)

如果至少存在一點x∈X滿足f(x)<∞，且對所有的y∈X，f(y)<∞；否則稱f是非正常的．

定義6[1](指示函數) 集合C的指示函數

命題1[1](對于下半連續的刻畫) 設f:Rn→R，下述等價：

(a)f在Rn上下半連續；

(b)上圖epif是Rn×R中的一閉集合；

(c)對任何α∈R，水平集合lev≤αf均是Rn中的閉集合．

定義8[1](水平有界性) 稱函數f:Rn→R是水平有界的，如果對每一α∈R，水平集合lev≤αf是有界的(可能是空集)．

{x:f(x，u)≤α}?B； ?u∈V

(5)

命題2[1](最終水平有界) 設f:Rn→R，下述等價：

(a)如果存在一水平有界函數g，有當v充分大時，fv≥g，或如果集合序列domfv是最終有界的，則序列{fv}v∈N是最終水平有界的．

2求解帶約束的序列問題的連續收斂方法

2.1約束優化問題的轉化模型

考慮下面的序列問題：

以及問題

其中fv、f為正常的下半連續函數，Cv、C為閉集，v∈N．

為了求解該問題，將約束問題轉化為無約束問題．利用指示函數，可以將問題(Pv)等價地轉化為無約束問題：

問題(P)轉化為無約束問題：

2.2連續收斂

考慮研究約束優化方法的關鍵條件：連續收斂和當v→∞時，Cv→C的等價條件．

定理2 當v→∞時，Cv→C等價于epiδCv→epiδC．

證明 觀察指示函數的上圖集合

epiδCv={(x，α):δCv≤α}={(x，α):x∈Cv，

α≥0}=Cv×R+

epiδC={(x，α):δC≤α}={(x，α):x∈C，

α≥0}=C×R+

可知當v→∞時，epiδCv→epiδC等價于Cv×R+→C×R+．

(i)首先證明由左式能得到右式．由Cv→C得，?xv∈Cv，?x∈C，有xv→x．顯然有(xv，1)→(x，1)，即得證．

(ii)再證由右式可以得到左式．由式(3)知，欲證Cv→C，即證

同理，Cv×R+→C×R+等價于

由xv∈Cv知，(xv，1)∈Cv×R+，又Cv×R+→C×R+，得

(x，1)∈C×R+

則可知當v→∞時，Cv→C．可知上述包含關系成立．

綜上，當v→∞時，

Cv→C?Cv×R+→C×R+

即Cv→C?epiδCv→epiδC．

□

接下來，給出本章的關鍵性結論，即上圖收斂的充分條件．

由fv連續收斂到f，及定義2可知，?xv→x，zv→x，有

由(a)+(c)、(b)+(d)得，?x，可以得到如下的不等式：

(6)

□

2.3最終水平有界性

除了滿足無約束目標函數序列fv上圖收斂到f，本文還研究約束優化問題的序列近似方法的另一個條件：{fv}最終水平有界性．

□

(7)

由于fv下半連續，有

(8)

又由指示函數知

(9)

□

綜上所述：fv、f是下半連續、正常的，Cv是閉集時，還需要下面3個條件：

(a)Cv最終有界；

(b)Cv→C；

(c)fv連續收斂到f．

3用上圖收斂解決帶約束的單調序列問題

3.1約束優化問題的轉化

考慮如下問題：

該問題等價于

下面的序列問題

等價于

其中fv、f為正常的下半連續函數，Cv、C為閉集，v∈N．

為了求解該問題，將約束問題轉化為無約束問題．利用指示函數，可以將問題(Pv)等價地轉化為無約束問題：

問題(P)轉化為無約束問題：

3.2用上圖收斂解決帶約束的單調序列問題

定理6 若fvf，且fv下半連續，則有

證明 由引理1知

由于fv下半連續，則clfv=fv，并且由fvf知所以有，即

□

對于fvf，有?v∈N，fv≤fv+1，且fv→f．對于?x∈Rn，fv(x)≤fv+1(x)，則?(x，αv)∈epifv，?(x，αv+1)∈epifv+1，有epifv?epifv+1，所以epifvepif．另一方面，對于CvC，則有Cv?Cv+1，Cv→C．由epiδCv(x)=Cv×R+，顯然有Cv×R+?Cv+1×R+，則集合列epiδCvepiδC．

K={0}∪{x≠0，?xv→dir x，F(xv)有界}

這里F取fv或δCv．

矛盾，所以{xv}是有界集．由xv∈Cv知，Cv是有界集．由于Cv→C，所以?x∈C，?xv∈Cv，xv→x，即

x∈xv+εB∈Cv+εB

所以C有界．

存在等價關系

lev≤αδC={x:δC(x)≤α}={x:x∈C，α≥0}=C

所以δC水平有界且顯然δC?∞，又lev≤αδC連通，可以由命題2(c)知，序列{δCv}最終水平有界，從而?α∈R，lev≤αδCv最終有界，即{Cv}最終有界．

□

定理8 若A=B∩C，則A∞?B∞∩C∞．

證明 由地平錐定義知

A∞={x:?λv0，?xv∈A，s.t.λvxv→x}

即對于?x∈A∞，?xv∈A=B∩C，使xv→dir x(x≠0)．顯然由xv∈B，xv→dir x，知x∈B∞，同理x∈C∞，x∈B∞∩C∞．

□

引理2[1](有界性的地平準則) 集合C?Rn有界的充分必要條件是它的地平錐為0錐：C∞={0}．

引理3[1](水平集合的地平錐) 對函數f:Rn→R與α∈R，有(lev≤αf)∞?lev≤0f∞．

由觀察可得

epiδCv=Dv={(x，t):x∈Cv，fv(x)-t≤0}=

(Cv×R+)∩epifv=epiδCv∩epifv

epiδC=D={(x，t):x∈C，f(x)-t≤0}=

(C×R+)∩epif=epiδC∩epif

(Dv)∞?(epifv)∞∩(epiδCv)∞=

(lev≤tfv×(-∞，t))∞∩(Cv×R+)∞?

(lev≤0fv∞×{-1})∩({0}×{1})=

{0}×{0}

定理9 已知AvA，BvB，fv下半連續，Cv是有界閉集，證明Dv→D．

證明 由fv下半連續知Av是閉集，由Cv=lev≤αδCv是有界閉集知Bv是有界閉集．只需證明

先證左邊的包含關系，由內外極限的定義1知

?xv∈Av∩Bv，

現在證右邊的包含關系，即證

由C為閉集和定理1知，上式等價于證明對任意ρ>0，ε>0，存在N∈N∞，使得

A∩B∩ρB?Av∩Bv+εB

由于AvA，BvB，則Av?Av+1?A，Bv?Bv+1?B，則Av∩Bv?A∩B，所以有

Av∩Bv+εB?A∩B∩ρB

即右邊也成立．從而有

epiδCv∩epifv→epiδC∩epif

□

綜述：對于滿足fv、f下半連續、正常的，Cv閉集的序列問題，結合地平函數，滿足條件

(b)fvf；

(c)CvC．

就可由引言中定理得到

4實例

為了驗證單調問題在實際中的意義，下面以3個比較常用的問題作為例子．對于正常的下半連續函數f及約束集合C，構造正常的下半連續函數序列fv使fvf，以及閉約束集合Cv使CvC．這樣構造出滿足上圖收斂的單調序列問題，然后就利用條件Cv={0}且{C}都是連通的，就能得出序列近似問題的全局最優值收斂到原問題的最優值，即

例1 考慮下面的問題，其中f:Rn→R是正常下半連續函數，F:Rn→Rm連續，D?Rm是一閉集合，

設用指示函數轉化為下面問題：

用罰函數構造序列近似問題

函數θ:Rm×(0，∞)→R是下半連續的(文獻[1]中有證明)，滿足當rv→∞時，-∞<θ(F(x)，rv)δD(F(x))．由D是閉集合，可知δD下半連續，又由函數θ的下半連續性及定理5可得是正常下半連續的，Cv=Rn閉．由此可得當v越大時，rv越大，且rv→∞，有v，即．設存在某一∈(0，∞)充分大使得函數)的水平集是有界的．考慮參數序列滿足rv→∞，則有設xv是對應于參數rv的問題的最優解，則序列{xv}v∈N有界，即Cv有界．又由C=F-1(D)，F是連續的，D是閉集，從而C是有界閉集，只要給出連通的條件，就可以利用極小化收斂定理得到序列近似問題全局最優值的收斂性．

例2 考慮下面的問題，其中f:Rn×Rn→R為正常下半連續函數，h:Rn×Rn→Rl，g:Rn×Rn→Rm，

由于互補條件的出現，該問題不滿足通常的約束條件，從而無法得到一階必要性條件，給求解帶來了極大的困難．對此，先將其轉化為

下面構造序列近似問題

集合Cv是對集合C的松弛．其中對于N∈N∞，?v∈N，?εv0．上述問題不存在互補條件，并且將等式與不等式約束罰到目標函數上去，是一系列相對容易求解的問題．

觀察可得隨著v越大，有εvv．證明隨著v越大，CvC，由構造知Cv單調，只需證Cv→C，即證

右邊顯然可得．左邊若成立，等價地有

?(xv，yv)∈Cv，

例3 對于正常的下半連續函數f:Rn→R，考慮下面問題：

構造一近似序列函數：

從而(x，Zv，Yv)∈C．左邊的包含關系得證，即有CvC．同時由例2可知是正常下半連續的，Cv為閉集合．構造滿足單調問題，從而可通過解決單調問題來解決抽象約束優化問題的序列近似方法的收斂性．

5結語

為了解決約束優化問題的序列近似方法收斂性，本文先用目標函數序列連續收斂、約束集合序列收斂以及最終有界3個條件，得到序列近似問題的全局最優值收斂到原問題的最優值，從而將一復雜問題成功轉化為一系列簡單可解的問題．由于連續收斂的條件比較強，利用比較弱的上圖收斂來替換連續收斂，需要證明兩上圖收斂集合的交的收斂性，在非凸的條件下很難證明，所以考慮目標函數序列和約束集合序列單調的情況下證明．另一方面，利用地平函數和地平錐證明約束集合的最終有界性從而解決約束優化問題的序列近似方法收斂性，并將這一結果用于分析一些簡單的互補約束優化問題的光滑化方法的收斂性．在接下來的工作中，將研究使兩個單調序列的條件弱化的情況，在只有一個為單調序列的條件，或者更弱的條件下用上圖收斂解決約束優化問題的序列近似方法的收斂性．

參考文獻：

[1] Rockafellar R T, Wets R J B. Variational Analysis [M]. New York:Springer-Verlag, 1998.

[2]Mordukhovich B S. Variational Analysis and Generalized Differentiation Ⅰ: Basic Theory [M]. Berlin:Springer, 2006.

[3]Mordukhovich B S. Variational Analysis and Generalized Differentiation Ⅱ: Applications [M]. Berlin:Springer, 2006.

[4]Fukushima Masao. 非線性最優化基礎[M]. 林貴華,譯. 北京:科學出版社, 2011.

Fukushima Masao. Nonlinear Optimization [M]. LIN Gui-hua, trans. Beijing:Science Press, 2011. (in Chinese)

[5]Clarke F H. Optimization and Nonsmooth Analysis [M]. New York:Wiley-Interscience, 1983.

[6]Clarke F H, Ledyaev Y S, Stern R J,etal. Nonsmooth Analysis and Control Theory [M] New York:Springer, 1998.

[7]Polak E, Womersley R S, Yin H X. An algorithm based on active sets and smoothing for discretized semi-infinite minimax problems [J]. Journal of Optimization Theory and Applications, 2008, 138(2):311-328.

[8]Hong L J, YANG Yi, ZHANG Li-wei. Sequential convex approximations to joint chance constrained programs:A Monte Carlo approach [J]. Operations Research, 2011, 59(3):16-17.

Convergence of sequential approximation method for constrained optimization problems

DUANQing-song*

( School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China )

Abstract：The convergence of the sequential approximation method for abstract constrained optimization problems is discussed. It is proved that the global optimal solutions of the sequential approximation problems converge to the optimal solutions of the original problem under the continuous convergency of the objective function sequence and the convergency of the constrained set sequence. Moreover, if the objective function sequence is assumed to be epi-convergence instead of continuous convergence, the conclusion still holds when some monotonicity property of the objective functions and the constrained sets of the sequential approximation problems is satisfied. At last, the research result can be applied to analyze the convergence of the smoothing method in solving complementarity constraint optimization problem.

Key words：continuous convergence; epi-convergence;global optimal solution; complementarity constraint optimization

中圖分類號：O224

文獻標識碼：A

doi:10.7511/dllgxb201603015

作者簡介:段慶松*(1989-)，男，博士生，E-mail:duanqs@mail.dlut.edu.cn.

收稿日期：2015-08-31；修回日期: 2016-03-10．

文章編號：1000-8608(2016)03-0313-08