幾類優(yōu)化問題的數(shù)值方法研究.pdf

1、本文研究了幾個相互關(guān)聯(lián)的優(yōu)化問題的數(shù)值方法。文中所涉及到的問題分別是互補(bǔ)問題、分裂可行問題和隨機(jī)分裂可行問題。本研究分為四個部分：
　　 第一章介紹了本文所研究的幾個優(yōu)化問題,它們之間的關(guān)系以及文中要用到的一些記號。
　　 第二章研究了一類非線性互補(bǔ)問題?；パa(bǔ)問題是運(yùn)籌學(xué)與計(jì)算科學(xué)的一個交叉研究領(lǐng)域,它與非線性規(guī)劃、極大極小、對策論、不動點(diǎn)理論等分支有緊密聯(lián)系,在力學(xué)、工程、經(jīng)濟(jì)、交通等許多實(shí)際部門有廣泛的應(yīng)用?；パa(bǔ)問題

2、的標(biāo)準(zhǔn)形式是:給定連續(xù)可微的向量函數(shù)F(x):Rn→Rn,求一向量x∈Rn使得x≥O,F(x)≥0,xTF(x)=0。當(dāng)F(x)為線性函數(shù)(令F(x)=Mx+q,M∈Rn×n.q∈Rn)時,稱其為線性互補(bǔ)問題,記為LCP(M.q)；否則,稱其為非線性互補(bǔ)問題,記為NCP(F).互補(bǔ)問題的一個自然的推廣就是變分不等式問題(VI),即求解一向量x∈C使得(y-X)TF(x)≥0,()y∈C,這里C∈Rn為一個非空閉凸集。針對非線性互補(bǔ)問題(

3、P0-NCP),研究了一類非內(nèi)點(diǎn)路徑跟蹤算法。相對于標(biāo)準(zhǔn)中心路徑,我們使用了尺度化的中心路徑?；诔叨然闹行穆窂?我們給出了一個求解P0-NCP的一步式非內(nèi)點(diǎn)連續(xù)光滑化牛頓算法。在不需要嚴(yán)格互補(bǔ)性的假設(shè)條件下,證明了該算法的全局收斂性,并在適當(dāng)?shù)募僭O(shè)下,證明了局部二次收斂性。最后,我們通過幾個算例與另一類求解P0-NCP的一步式光滑化牛頓法進(jìn)行了比較。
　　 第三章研究了求解分裂可行問題的幾種投影方法。所謂分裂可行問題(SFP

4、)是:求x∈C,使得Ax∈Q,其中集合C和Q分別是RN和RM中的非空閉凸集,A是M×N階實(shí)矩陣。這類問題產(chǎn)生于信號處理中,特別是在圖像重構(gòu)和其他的圖像還原問題中。近年來,分裂可行問題在調(diào)強(qiáng)放療(IMRT)方面也有了重大的應(yīng)用。同時,分裂可行問題還與凸可行問題密切相關(guān)。凸可行問題(CFP)就是要找有限個閉凸集的非空交集中的點(diǎn),它在數(shù)學(xué),物理等許多學(xué)科中是一個基本的問題。因此,研究如何求解分裂可行問題具有重要的意義。CQ算法是求解SFP的一

5、種簡潔的方法。在本文中,我們首先給出了CQ算法的一個非精確松弛格式,當(dāng)正交投影PC和PQ不容易求得時,此格式比CQ算法更具實(shí)用性。然后我們討論了變步長的CQ算法,并且說明,不論是帶固定步長的CQ算法,還是變步長的CQ算法,都是梯度投影算法的一個具體實(shí)現(xiàn)。相對于固定步長,變步長可以提高算法的收斂速度。最后,我們提出了變步長CQ算法的非精確格式以及非精確松弛格式。
　　 第四章應(yīng)用樣本均值近似(SAA)方法研究了隨機(jī)分裂可行問題(S

6、SFP)。樣本均值近似方法的基本思想是利用Monte Carlo樣本技術(shù)產(chǎn)生具有獨(dú)立同分布(iid.)的樣本,來模擬隨機(jī)模型中的隨機(jī)參數(shù)。利用 MonteCarlo樣本技術(shù),南隨機(jī)樣本產(chǎn)生的樣本均值來近似估計(jì)隨機(jī)優(yōu)化問題的目標(biāo)函數(shù)的數(shù)學(xué)期望函數(shù),由此產(chǎn)生的樣木均值近似問題,可以利用確定性優(yōu)化技術(shù)來求解。用不同的樣本重復(fù)上述過程,可以用統(tǒng)計(jì)方法估計(jì)產(chǎn)生的候選解的優(yōu)化間隙。首先定義了隨機(jī)分裂可行問題(SSFP),然后討論用樣本均值近似(SA