約束優(yōu)化問(wèn)題的序列近似方法收斂性

段 慶 松

( 大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連　116024 )

?

約束優(yōu)化問(wèn)題的序列近似方法收斂性

段 慶 松*

( 大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連116024 )

摘要：對(duì)抽象約束優(yōu)化問(wèn)題的序列近似方法的收斂性進(jìn)行討論，證明了在目標(biāo)函數(shù)序列連續(xù)收斂和約束集合序列收斂的條件下，序列近似問(wèn)題的全局最優(yōu)值收斂到原問(wèn)題的最優(yōu)值．進(jìn)一步，證明了在序列近似問(wèn)題目標(biāo)函數(shù)和約束集合具有某些單調(diào)性質(zhì)的前提下，把目標(biāo)函數(shù)序列連續(xù)收斂減弱到上圖收斂，該結(jié)論仍然成立．最后，將這一結(jié)果用于分析互補(bǔ)約束優(yōu)化問(wèn)題的光滑化方法的收斂性中．

關(guān)鍵詞：連續(xù)收斂；上圖收斂；全局最優(yōu)解；互補(bǔ)約束優(yōu)化

0引言

Rockafellar等[1]1998年在著作Variational Analysis中討論了很重要的集值映射和函數(shù)列的收斂問(wèn)題，其中集合序列的極限是集值映射的極限與連續(xù)性的基礎(chǔ)，集值映射序列的收斂包含了逐點(diǎn)收斂、圖收斂、連續(xù)收斂、一致收斂，函數(shù)列的收斂有逐點(diǎn)收斂、連續(xù)收斂、上圖收斂、一致收斂等．隨著對(duì)更多的關(guān)于收斂問(wèn)題的深入了解，這些序列收斂在約束優(yōu)化近似方法中的應(yīng)用越來(lái)越重要．Mordukhovich[2-3]也給出了關(guān)于集值映射序列很多重要的性質(zhì)．

考慮下面的約束優(yōu)化問(wèn)題：

若存在ε>0使得

為了得到問(wèn)題(P)的最優(yōu)解，往往需要驗(yàn)證下面的最優(yōu)必要性條件：

0∈f(x)+N(x)

f(x)、N(x

目前，學(xué)者們對(duì)問(wèn)題(P)的求解方法已經(jīng)有了很多研究，例如罰函數(shù)方法、內(nèi)點(diǎn)法、增廣拉格朗日法、序列二次規(guī)劃方法等，想要了解非線性問(wèn)題的求解方法可以參考文獻(xiàn)[7]等．在許多問(wèn)題中，都要用到序列近似方法來(lái)解決，即遇到復(fù)雜難以求解的問(wèn)題時(shí)，往往用一系列性質(zhì)簡(jiǎn)單且容易解決的問(wèn)題來(lái)近似原問(wèn)題，Hong等[8]運(yùn)用序列凸近似方法解決了復(fù)雜的DC問(wèn)題，而在一般情況下，通?？紤]序列問(wèn)題：

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

若滿足上述定理中的條件，則可通過(guò)對(duì)序列問(wèn)題(Pv)的求解來(lái)得到原問(wèn)題(P)的最優(yōu)值．本文將會(huì)基于此定理，進(jìn)一步考慮序列問(wèn)題(Pv)與原問(wèn)題(P)的最優(yōu)值之間的關(guān)系．

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

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

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

(1)

(2)

如果內(nèi)極限與外極限相等，則稱序列的極限C存在，

(3)

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

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

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

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

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

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

(4)

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

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

命題1[1](對(duì)于下半連續(xù)的刻畫) 設(shè)f:Rn→R，下述等價(jià)：

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

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

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

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

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

(5)

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

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

2求解帶約束的序列問(wèn)題的連續(xù)收斂方法

2.1約束優(yōu)化問(wèn)題的轉(zhuǎn)化模型

考慮下面的序列問(wèn)題：

以及問(wèn)題

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

為了求解該問(wèn)題，將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題．利用指示函數(shù)，可以將問(wèn)題(Pv)等價(jià)地轉(zhuǎn)化為無(wú)約束問(wèn)題：

問(wèn)題(P)轉(zhuǎn)化為無(wú)約束問(wèn)題：

2.2連續(xù)收斂

考慮研究約束優(yōu)化方法的關(guān)鍵條件：連續(xù)收斂和當(dāng)v→∞時(shí)，Cv→C的等價(jià)條件．

定理2 當(dāng)v→∞時(shí)，Cv→C等價(jià)于epiδCv→epiδC．

證明 觀察指示函數(shù)的上圖集合

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

α≥0}=Cv×R+

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

α≥0}=C×R+

可知當(dāng)v→∞時(shí)，epiδCv→epiδC等價(jià)于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+等價(jià)于

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

(x，1)∈C×R+

則可知當(dāng)v→∞時(shí)，Cv→C．可知上述包含關(guān)系成立．

綜上，當(dāng)v→∞時(shí)，

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

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

□

接下來(lái)，給出本章的關(guān)鍵性結(jié)論，即上圖收斂的充分條件．

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

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

(6)

□

2.3最終水平有界性

除了滿足無(wú)約束目標(biāo)函數(shù)序列fv上圖收斂到f，本文還研究約束優(yōu)化問(wèn)題的序列近似方法的另一個(gè)條件：{fv}最終水平有界性．

□

(7)

由于fv下半連續(xù)，有

(8)

又由指示函數(shù)知

(9)

□

綜上所述：fv、f是下半連續(xù)、正常的，Cv是閉集時(shí)，還需要下面3個(gè)條件：

(a)Cv最終有界；

(b)Cv→C；

(c)fv連續(xù)收斂到f．

3用上圖收斂解決帶約束的單調(diào)序列問(wèn)題

3.1約束優(yōu)化問(wèn)題的轉(zhuǎn)化

考慮如下問(wèn)題：

該問(wèn)題等價(jià)于

下面的序列問(wèn)題

等價(jià)于

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

為了求解該問(wèn)題，將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題．利用指示函數(shù)，可以將問(wèn)題(Pv)等價(jià)地轉(zhuǎn)化為無(wú)約束問(wèn)題：

問(wèn)題(P)轉(zhuǎn)化為無(wú)約束問(wèn)題：

3.2用上圖收斂解決帶約束的單調(diào)序列問(wèn)題

定理6 若fvf，且fv下半連續(xù)，則有

證明 由引理1知

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

□

對(duì)于fvf，有?v∈N，fv≤fv+1，且fv→f．對(duì)于?x∈Rn，fv(x)≤fv+1(x)，則?(x，αv)∈epifv，?(x，αv+1)∈epifv+1，有epifv?epifv+1，所以epifvepif．另一方面，對(duì)于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(xiàn)(xv)有界}

這里F取fv或δCv．

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

x∈xv+εB∈Cv+εB

所以C有界．

存在等價(jià)關(guān)系

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}

即對(duì)于?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](有界性的地平準(zhǔn)則) 集合C?Rn有界的充分必要條件是它的地平錐為0錐：C∞={0}．

引理3[1](水平集合的地平錐) 對(duì)函數(shù)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下半連續(xù)，Cv是有界閉集，證明Dv→D．

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

先證左邊的包含關(guān)系，由內(nèi)外極限的定義1知

?xv∈Av∩Bv，

現(xiàn)在證右邊的包含關(guān)系，即證

由C為閉集和定理1知，上式等價(jià)于證明對(duì)任意ρ>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

□

綜述：對(duì)于滿足fv、f下半連續(xù)、正常的，Cv閉集的序列問(wèn)題，結(jié)合地平函數(shù)，滿足條件

(b)fvf；

(c)CvC．

就可由引言中定理得到

4實(shí)例

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

例1 考慮下面的問(wèn)題，其中f:Rn→R是正常下半連續(xù)函數(shù)，F(xiàn):Rn→Rm連續(xù)，D?Rm是一閉集合，

設(shè)用指示函數(shù)轉(zhuǎn)化為下面問(wèn)題：

用罰函數(shù)構(gòu)造序列近似問(wèn)題

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

例2 考慮下面的問(wèn)題，其中f:Rn×Rn→R為正常下半連續(xù)函數(shù)，h:Rn×Rn→Rl，g:Rn×Rn→Rm，

由于互補(bǔ)條件的出現(xiàn)，該問(wèn)題不滿足通常的約束條件，從而無(wú)法得到一階必要性條件，給求解帶來(lái)了極大的困難．對(duì)此，先將其轉(zhuǎn)化為

下面構(gòu)造序列近似問(wèn)題

集合Cv是對(duì)集合C的松弛．其中對(duì)于N∈N∞，?v∈N，?εv0．上述問(wèn)題不存在互補(bǔ)條件，并且將等式與不等式約束罰到目標(biāo)函數(shù)上去，是一系列相對(duì)容易求解的問(wèn)題．

觀察可得隨著v越大，有εvv．證明隨著v越大，CvC，由構(gòu)造知Cv單調(diào)，只需證Cv→C，即證

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

?(xv，yv)∈Cv，

例3 對(duì)于正常的下半連續(xù)函數(shù)f:Rn→R，考慮下面問(wèn)題：

構(gòu)造一近似序列函數(shù)：

從而(x，Zv，Yv)∈C．左邊的包含關(guān)系得證，即有CvC．同時(shí)由例2可知是正常下半連續(xù)的，Cv為閉集合．構(gòu)造滿足單調(diào)問(wèn)題，從而可通過(guò)解決單調(diào)問(wèn)題來(lái)解決抽象約束優(yōu)化問(wèn)題的序列近似方法的收斂性．

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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. 非線性最優(yōu)化基礎(chǔ)[M]. 林貴華,譯. 北京:科學(xué)出版社, 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

中圖分類號(hào)：O224

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.7511/dllgxb201603015

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

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

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