段 庆 松

( 大连理工大学 数学科学学院, 辽宁 大连　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