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

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

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

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

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

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

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

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