變測(cè)度的積分—水平集確定性算法.pdf

1、在科學(xué)、經(jīng)濟(jì)和工程中，許多最新的發(fā)展依賴于計(jì)算相應(yīng)的優(yōu)化問題的全局最優(yōu)解的數(shù)值技術(shù)。全局最優(yōu)化問題的來源是相當(dāng)廣泛的，包括經(jīng)濟(jì)建模、固定費(fèi)用、金融、網(wǎng)絡(luò)和運(yùn)輸、數(shù)據(jù)庫和芯片設(shè)計(jì)、圖像處理、化學(xué)工程設(shè)計(jì)與控制、分子生物學(xué)、環(huán)境工程及軍事科學(xué)等等。早在20世紀(jì)60年代，就有人開始研究全局優(yōu)化問題，主要集中于線性規(guī)劃和非線性規(guī)劃局部化數(shù)值算法方面的研究，經(jīng)過40多年的發(fā)展，全局優(yōu)化已經(jīng)成長(zhǎng)為最優(yōu)化學(xué)科領(lǐng)域中一個(gè)獨(dú)立的學(xué)科分支，成為人們研究實(shí)際

2、問題時(shí)進(jìn)行建模和分析的重要手段之一。 通常一個(gè)全局最優(yōu)化問題可表述為：對(duì)于給定的一個(gè)n維空間的緊集D()Rn，及給定的連續(xù)函數(shù)f：Rn→R1上，尋找某一點(diǎn)x*∈D，使得對(duì)于一切的x∈D，滿足f(x*)≤f(x)。即求下列問題的解： globminx∈Df(x)或考慮求解更一般問題的解： globminx∈Sf(x)其中S是一個(gè)n維歐氏空間的約束集，S={x|gi(x)≤0，i=1，2…，r}且S()Rn，gi(x

3、)，i=1，2，…，m.為連續(xù)函數(shù)。 本文對(duì)鄭權(quán)、張連生、鄔冬華等教授提出的有關(guān)積分型求總極值的方法作了認(rèn)真細(xì)致的學(xué)習(xí)和研究。鄭權(quán)等1978年提出了求總極值的積分－水平集方法，主要特點(diǎn)有判別總極值的收斂準(zhǔn)則，且僅需假設(shè)目標(biāo)函數(shù)與約束函數(shù)為連續(xù)的，是現(xiàn)有少量具有特色的求全局優(yōu)化方法之一。但其概念算法與Monte-Carlo隨機(jī)投點(diǎn)的實(shí)現(xiàn)算法不匹配，易遺失總極值外，其實(shí)現(xiàn)算法收斂性至今未解決。1995年張連生教授等提出了離散均值-水

4、平集算法，并證明了其算法的收斂性。接著，鄔冬華等又給出了基于鄭權(quán)的概念性算法，構(gòu)造與概念算法較為吻合的修正算法，并用數(shù)論方法進(jìn)行數(shù)值計(jì)算，得到了實(shí)現(xiàn)算法的收斂性。 在他們工作的基礎(chǔ)上，本文提出了一個(gè)變測(cè)度的積分水平集的確定性算法，對(duì)不同的箱子采用不同的測(cè)度，結(jié)合確定性數(shù)論方法選取一致分布佳點(diǎn)集來代替Monte-Carlo隨機(jī)投點(diǎn)，使水平值充分地下降，更快地到達(dá)全局最小，從而提高算法的計(jì)算效率，并給出了算法的收斂性證明。此外，還對(duì)

5、帶有約束條件的全局優(yōu)化問題作了進(jìn)一步的研究，給出相應(yīng)的有約束的變測(cè)度積分－水平集算法，利用罰函數(shù)方法來處理有約束問題，將有約束問題轉(zhuǎn)化為無約束問題，證明了理論算法和實(shí)現(xiàn)算法的收斂性并通過數(shù)值算例驗(yàn)證了算法的有效性。 本文共有四章組成，第一章對(duì)全局優(yōu)化問題的目前發(fā)展?fàn)顩r以及比較流行的全局最優(yōu)化方法作了簡(jiǎn)單的介紹。第二章引入了我們證明中所需要的數(shù)論中的主要結(jié)果。第三章提出了變測(cè)度的積分——水平集確定性算法，并證明了此算法的收斂性。第