随机非线性规划问题

1、An efficient algorithm for large scale stochastic nonlinear programming problems随机非线性规划问题 (The stochastic nonlinear programming problems, SNLP) 是一类被广泛应用的优化问题。但 SNLP 问题的求解却非常的困难，这是由于此类问题较复杂，计算工作量大，目前的算法都有一定的局限性。为此文献提出了一个新的算法，the L-shaped BONUS，来求解大规模随机非线性规划问题。1. sampling based methods在随机规划问题中，当不确定性变量

2、的概率分布已知的条件下，通常采用样本近似的方法来逼近含随机变量的函数。为了使函数近似的精度能达到要求，样本数量要足够大。Monte Carlo 取样法被普遍采用以实现函数近似。图 1 描述了sampling based methods 的求解步骤。这个求解框架图类似于决定性问题，不同之处在于决定性模型被随机性模型取代，阴影部分的随机性模型可以用 Monte Carlo 方法近似。这类求解 SNLP 的方法中比较有代表性的两种算法是 the sampling based L-shaped method and the stochastic decomposition algorithm。这类求解

3、方法主要的缺点是在每一次迭代中，随机模型都要通过Monte Carlo 取样的方式模拟一次。当样本数量很大时，计算量就会变得很大。因此文献提出了 BONUS (better optimization of nonlinear uncertain systems) 算法克服这个困难。 图 1. the sampling based methods 计算框图2. BONUSBONUS 算法采用 re-weighting scheme 跳过每次迭代中随机模型的模拟，即每次迭代，只需计算一次就可得到期望值的近似，而不用每一个样本都模拟一次。 开始的时候，首先产生一个不确定性变量的均匀分布。在第一次迭代

4、中，算法类似于标准的 L-shaped method，每个样本都模拟一次，以决定不确定性模型的出口分布。在随后的迭代中，当 Optimizer 需要对目标函数的概率值做新的评估时，一套新的样本被重新抽取，但这次不需要对每一个样本都计算，the re-weighting approach 被使用去近似新的出口函数的概率。这种方法采用了初始样本，初始出口函数分布和新的样本的信息去评估新的出口函数的概率。The re-weighting approach 是 importance sampling 概念的扩展。即目标分布可以通过设计分布 的样本来估计。这些分布有各自的概率密度函数。假设随机变量 的概

5、率密度函数为， 是 的函数。则的期望表示为：采用 importance sampling 概念，以上期望可以通过解另外一个期望 得到： 以上关系式中的样本从分布 中抽取。分布 可以被设计以便得到想要的结果，如更小的变异。The weigh function 被定义为 的期望可以表示为 上式中 表示基本样本集合，它们满足均匀分布 。通过对每一样本做模拟计算，可以得到出口函数的分布 。 表示新的样本集合，它从分布 中抽取。通过以上方式可以估算随机模型 的期望对于新的样本集合。文献将以上提出的BONUS 算法和标准的 L-shaped method 相结合，形成了 the L-shaped BONUS 算法，用以求解大规模随机非线性规划