隨機優(yōu)化算法及其收斂性研究.pdf

1、本文旨在研究應用十分廣泛的隨機優(yōu)化算法及其收斂性問題.首先研究了第二階段問題為二次規(guī)劃的補償隨機規(guī)劃問題,提出了該問題的基于Montc CarIo或Quasi-MontcCarlo 模擬的近似Lagrange-Nevton 算法和隨機SSLE算法.其次探討了一般形式的非線性隨機規(guī)劃問題,提出了一個新的隨機搜索算法. 第二章討論了第一階段約束為等式約束的補償隨機規(guī)劃問題.本章第二節(jié)通過利用Montc Carlo模擬方法近似目標函數(shù)

2、及其一(二)階信息,給出了解這類問題的一個近似Lagraage-Newton算法.第二、三節(jié)在依概率1條件下分別證明了該算法的全局收斂性和局部超線性收斂性. 第三章將SSLE方法引入補償隨機規(guī)劃問題,給出了一個基于 Quasi-Monte carlo 模擬的隨機 SSLE 算法.在工作集I<,nк>(x<'к+1>,x<'к>,λ<'к>,λ<'к>,ε<.к>)計算方面,我們提出了一個新的方法,該方法不再計算乘子函數(shù),而是利用

3、算法上一步迭代獲得的近似乘子λ<'к>代替現(xiàn)有算法中的乘子函數(shù)λ(x<,к>),從而避免了有效集識別過程中因計算乘子函數(shù)而帶來的矩陣求逆的運算.同時 SSLE 方法用若干線性方程組代替 SQP 子問題來獲得迭代方向,不需要目標函數(shù)的二階信息,因而也避免了 Birge 等人提出的隨機 Newton 型算法中由求解SQp子問題引起的近似海色矩陣的計算.第三節(jié)在線性獨立假設下討論了算法的全局收斂性.第四節(jié)在嚴格互補條件下證明了算法的超線性收斂

4、性. 第四章討論了第一階段約束為線性不等式約束的補償隨機規(guī)劃問題.本章第二節(jié)基于Monte-Carlo模擬構造了一個新的子問題規(guī)摸小的隨機 SSLE 算法.該算法的每步迭代只需解一個或三個同系數(shù)的線性方程組來獲得迭代方向,特別地,當算法趨于最優(yōu)解時,每步迭代只需解一個線性方程組,因此與 SQP 和 Newton 型算法相比減少了計算量.第二、三節(jié)證明了算法依概率1具有全局收斂性和超線性收斂性.特別是第四節(jié)的超線性收斂性證明中去掉

5、了嚴格互補條件,在由 F.Facchinei 提出的擬-正則條件下,算法依概率1具有局部超線性收斂速度,且在證明工作集對有效集的精確識別時,沒有利用F.Facchinei提出的有效集識別函數(shù),而是由本章定義的工作集I<'к>自身的結構直接證明了這一結果. 第五章進一步討論了第一階段約束為非線性不等式約束的補償隨機規(guī)劃問題.本章第二節(jié)基于Quasi-Monte-Carlo模擬技巧給出了該問題的一個隨機SSLE算法.第二、三節(jié)證明了

6、算法的全局收斂性和超線性收斂性.第四節(jié)的超線性收斂性證明仍然不需要嚴格互補條件.該算法綜合了本文第三、四章給出的隨機SSLE算法幾乎所有的優(yōu)點.此外,在該算法的序列方程組中我們定義了兩個新的乘子A<'к>和B<'к>,這使得算法只需解兩到三個同系數(shù)對稱矩陣的線性方程組,特別地,當算法產(chǎn)生的點列充分靠近最優(yōu)解時,在每步迭代算法僅需解兩個線性方程組.因此,該算法與現(xiàn)有的SSLE算法相比,每次迭代減少了解方程組的個數(shù). 第六章探討了補

7、償隨機規(guī)劃問題的啟發(fā)式方法.本章第二節(jié)將一般補償隨機規(guī)劃問題看作具有一般約束的全局最優(yōu)化問題,給出了該問題的一個全局收斂算法.該算法利用簡單的隨機搜索方法從可行域中選取樣本點.第三節(jié)證明了該算法依概率1全局收斂于該問題的ε一最優(yōu)解,這一收斂結果比sIlkcr Birb訂和Shu-Chcrng Fang提出的算法要好.收斂性證明不需要迭代點列的Markov性條件,僅要求目標函數(shù)滿足BoreI可測性,直接利用測度理論就可獲得.因此,算法適用