特征值優(yōu)化問題的若干算法研究.pdf

1、本文主要研究了兩類特征值優(yōu)化問題：一類是關(guān)于區(qū)域密度分布的約束優(yōu)化問題，一類是關(guān)于邊界控制的約束優(yōu)化問題。針對這兩類不同的問題，本論文提出了貪婪算法、單調(diào)算法以及邊界分片常數(shù)水平集方法。
　　 我們首先討論兩種密度時，負拉普拉斯算子的最小特征值取極小、極大以及次小特征值與最小特征值之差取極大這三類問題。利用貪婪算法在每次迭代過程中，都是朝著局部最好的方向發(fā)展的特性，我們提出兩類貪婪算法：第一類貪婪算法是從不滿足面積約束條件的情況

2、下，根據(jù)單元的測度選出最佳單元，改變該單元的密度值，循環(huán)迭代直到面積約束條件滿足時停止。第二類貪婪算法在一開始就滿足面積約束條件，在兩種密度所在的區(qū)域選出各自的最佳單元，然后交換彼此的密度值，直到迭代終止。這兩種貪婪算法都很好的解決了三類特征值優(yōu)化問題。為了加速迭代，我們還提出了針對兩類貪婪算法的加速算法。我們加速算法的思想是，把每次迭代只改變一個單元（或者一對單元）的密度值，變成每次迭代改變一組最佳單元的密度值。這樣，大大加快了收斂速

3、度，并且得到最優(yōu)解。在數(shù)值例子中，這兩類貪婪算法都十分有效且快速的求解了帶面積約束的極小化、極大化最小特征值以及極大億次小特征值與最小特征值之差這三類問題。
　　 其次，我們把兩種密度推廣到多種密度的情況。此時，我們只考慮極小化負拉普拉斯算子的最小特征值問題。我們把連續(xù)的問題用有限元方法離散后，根據(jù)離散問題的特性，設(shè)計的一種單調(diào)算法。我們對算法經(jīng)行了理論分析并且給出了算法單調(diào)性的證明。我們算法的出發(fā)點與文獻[21]不同。文獻[2

4、1]其主要思想是從優(yōu)化的角度，分析了各種密度區(qū)域的分界線。我們的算法主要思想是通過排序，更新下一次的密度分布。此外，我們的單調(diào)算法和參考文獻[73]中水平集方法也有顯著不同。與文獻[73]中跟蹤運動前端的水平集方法比較，我們的單調(diào)算法收斂的更快，使用很少幾步迭代就能達到λ1最小值。更進一步，在數(shù)值例子中，我們發(fā)現(xiàn)網(wǎng)格尺寸和計算minλ1有依賴關(guān)系。網(wǎng)格越細，最小特征值的極小值也越小。因此，在我們的算法中采用200×300網(wǎng)格尺寸，這個網(wǎng)

5、格尺寸是文獻[73]網(wǎng)格尺寸的25倍。在數(shù)值例子中，我們給出了兩種密度、三種密度和十種密度的情況，并且在矩形區(qū)域和L-型區(qū)域中分別應(yīng)用單調(diào)算法。我們的數(shù)值結(jié)果表明，單調(diào)算法能快速有效地求解多種密度時極小化最小特征值問題。
　　 最后，我們討論了特征值優(yōu)化問題的邊界控制問題。在分片常數(shù)水平集方法的基礎(chǔ)上，我們提出了邊界分片常數(shù)水平集方法，推廣了分片常數(shù)水平集函數(shù)。對于特征值優(yōu)化問題，我們首先通過正則化的方法把混合邊界條件變成一個R

6、obin邊界條件。然后引入邊界分片常數(shù)水平集函數(shù)，把最小特征值由原來依賴于邊界轉(zhuǎn)化為依賴于邊界分片常數(shù)水平集函數(shù)。根據(jù)約束條件的不同處理，我們提出了罰因子邊界分片常數(shù)水平集算法和增廣拉格朗日邊界分片常數(shù)水平集算法。對罰函數(shù)和拉格朗日函數(shù)關(guān)于邊界分片常數(shù)水平集函數(shù)求第一變分，我們引入人工時間項，并用三階Runge-Kutta格式來離散這個常微分方程。這樣，我們動態(tài)地更新邊界分片常數(shù)水平集函數(shù)。在數(shù)值例子中，我們的罰因子邊界分片常數(shù)水平集算