隨機非線性規(guī)劃問題

1、An efficient algorithm for large scale stochastic nonlinear programming problems隨機非線性規(guī)劃問題 (The stochastic nonlinear programming problems, SNLP) 是一類被廣泛應用的優(yōu)化問題。但 SNLP 問題的求解卻非常的困難，這是由于此類問題較復雜，計算工作量大，目前的算法都有一定的局限性。為此文獻提出了一個新的算法，the L-shaped BONUS，來求解大規(guī)模隨機非線性規(guī)劃問題。1. sampling based methods在隨機規(guī)劃問題中，當不確定性變量

2、的概率分布已知的條件下，通常采用樣本近似的方法來逼近含隨機變量的函數(shù)。為了使函數(shù)近似的精度能達到要求，樣本數(shù)量要足夠大。Monte Carlo 取樣法被普遍采用以實現(xiàn)函數(shù)近似。圖 1 描述了sampling based methods 的求解步驟。這個求解框架圖類似于決定性問題，不同之處在于決定性模型被隨機性模型取代，陰影部分的隨機性模型可以用 Monte Carlo 方法近似。這類求解 SNLP 的方法中比較有代表性的兩種算法是 the sampling based L-shaped method and the stochastic decomposition algorithm。這類求解

3、方法主要的缺點是在每一次迭代中，隨機模型都要通過Monte Carlo 取樣的方式模擬一次。當樣本數(shù)量很大時，計算量就會變得很大。因此文獻提出了 BONUS (better optimization of nonlinear uncertain systems) 算法克服這個困難。 圖 1. the sampling based methods 計算框圖2. BONUSBONUS 算法采用 re-weighting scheme 跳過每次迭代中隨機模型的模擬，即每次迭代，只需計算一次就可得到期望值的近似，而不用每一個樣本都模擬一次。 開始的時候，首先產生一個不確定性變量的均勻分布。在第一次迭代

4、中，算法類似于標準的 L-shaped method，每個樣本都模擬一次，以決定不確定性模型的出口分布。在隨后的迭代中，當 Optimizer 需要對目標函數(shù)的概率值做新的評估時，一套新的樣本被重新抽取，但這次不需要對每一個樣本都計算，the re-weighting approach 被使用去近似新的出口函數(shù)的概率。這種方法采用了初始樣本，初始出口函數(shù)分布和新的樣本的信息去評估新的出口函數(shù)的概率。The re-weighting approach 是 importance sampling 概念的擴展。即目標分布可以通過設計分布 的樣本來估計。這些分布有各自的概率密度函數(shù)。假設隨機變量 的概

5、率密度函數(shù)為， 是 的函數(shù)。則的期望表示為：采用 importance sampling 概念，以上期望可以通過解另外一個期望 得到： 以上關系式中的樣本從分布 中抽取。分布 可以被設計以便得到想要的結果，如更小的變異。The weigh function 被定義為 的期望可以表示為 上式中 表示基本樣本集合，它們滿足均勻分布 。通過對每一樣本做模擬計算，可以得到出口函數(shù)的分布 。 表示新的樣本集合，它從分布 中抽取。通過以上方式可以估算隨機模型 的期望對于新的樣本集合。文獻將以上提出的BONUS 算法和標準的 L-shaped method 相結合，形成了 the L-shaped BONUS 算法，用以求解大規(guī)模隨機非線性規(guī)劃