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

1、本文旨在研究應(yīng)用十分廣泛的隨機優(yōu)化算法及其收斂性問題.首先研究了第二階段問題為二次規(guī)劃的補償隨機規(guī)劃問題,提出了該問題的基于Montc CarIo或Quasi-MontcCarlo 模擬的近似Lagrange-Nevton 算法和隨機SSLE算法.其次探討了一般形式的非線性隨機規(guī)劃問題,提出了一個新的隨機搜索算法. 第二章討論了第一階段約束為等式約束的補償隨機規(guī)劃問題.本章第二節(jié)通過利用Montc Carlo模擬方法近似目標(biāo)函數(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 子問題來獲得迭代方向,不需要目標(biāo)函數(shù)的二階信息,因而也避免了 Birge 等人提出的隨機 Newton 型算法中由求解SQp子問題引起的近似海色矩陣的計算.第三節(jié)在線性獨立假設(shè)下討論了算法的全局收斂性.第四節(jié)在嚴(yán)格互補條件下證明了算法的超線性收斂

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

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

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

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