APP下载

随机约束非光滑凸优化的空间分解方法

2016-05-09徐琳,李丹

沈阳大学学报(自然科学版) 2016年2期

徐 琳, 李 丹

(1. 沈阳大学 师范学院, 辽宁 沈阳 110044; 2. 沈阳市第二中学, 辽宁 沈阳 110016)



随机约束非光滑凸优化的空间分解方法

徐琳1, 李丹2

(1. 沈阳大学 师范学院, 辽宁 沈阳110044; 2. 沈阳市第二中学, 辽宁 沈阳110016)

摘要:讨论了随机约束非光滑凸优化的基于空间分解的样本均值近似(SAA)方法.在适当的条件下,SAA问题的解以概率1收敛到其真实解,并且随着样本容量的增加,收敛速度是指数的.基于分解理论,给出了求解SAA问题的超线性收敛速度的算法框架.

关键词:随机优化; 样本均值近似; 空间分解; 超线性收敛

考虑如下的随机约束非光滑凸优化

(1)

式中,f(x)=max{E[fi(x,ξ)]:i∈I=0,…,m}.对每个固定的ξ和和η,函数fi(·,ξ),i∈I和gj(·,η),j∈J是二次连续可微的凸函数.ξ和η是概率空间(Ω,γ,P)的两个随机变量,E是数学期望.

假设对任意x∈Rn,E[fi(x,ξ)],i∈I和E[gj(x,η)],j∈J有定义,令ξ1,…,ξN是ξ的样本,并且η1,…,ηN是η的样本.本文考虑基于样本的均值近似(SAA)方法,即利用fi(·,ξ)和gj(·,η)的样本均值近似它们的期望值.式(1)的SAA问题为

(2)

目前,SAA方法是随机优化的研究热点.文献[1]是随机优化和SAA方法的一个概述,亦可参见文献[2-6].SAA方法的基本思想是由蒙特卡罗模拟产生独立同分布的样本,并利用样本均值函数近似代替目标函数,然后利用确定型的优化方法来解决SAA问题,最后得到原问题的近似解.由于文献[1-6]中的目标函数均是光滑的,因此,其SAA问题都可由光滑牛顿法求解.

1SAA问题的收敛性分析

是在x处的积极指标集.

接下来讨论随着N的增大,式(2)收敛到式(1).具体地,当N→∞时,式(2)的SAA问题的解收敛到原问题的解.下面给出SAA方法的基本假……

登录APP查看全文