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

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

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

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

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

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