形狀最佳化問題的並行區域分解算法研究

【摘要】：這些形狀最佳化問題都會含有某種偏微分方程作為約束條件,即屬於偏微分方程約束的最佳化問題(partial differential equation constrained optimization problem),其與其它偏微分方程約束問題,如邊界控制問題(boundary control problem)的主要區別在於此類問題的最佳化變數是物體的形狀,即其計算區域在問題的求解過程中會發生變化,從而使得這類問題的求解更加困難.求解這類問題的另一主要困難在於其規模非常龐大(偏微分方程只是它的一個子問題),普通的單處理器計算機很難精確求解此類問題,從而需要藉助大型的並行計算機來求解.本博士論文的目的是研究形狀最佳化問題的高效並行算法.常用的求解形狀最佳化問題的算法是通過求解其一階最優性條件(即極值點)來獲得此類問題的解,由於受計算機記憶體和計算速度的影響,在過去的二三十年里流行的算法通常把一階最優性條件分成三塊：狀態方程,共軛方程和設計方程,然後疊代地求解此三組方程.這類算法較容易實現,但收斂性和並行性不是很好,且其需要重複地多次精確求解狀態方程(通常為偏微分方程),從而其計算量非常大.此類算法類似於非線性的塊Gauss-Seidel算法.本文提出了一種新的求解形狀最佳化問題的全耦合(one-shot)並行Lagrange-Newton-Krylov-Schwarz (LNKSz)算法LNKSz(?)(?)最佳化問題的一階最優性條件看作一個整體來求解,在整個求解過程中只需要求解一次狀態方程,從而避免了傳統算法中收斂性,並行性差和計算量大的缺點.由於形狀最佳化問題在求解過程中,其計算區域會發生變化,本文首先介紹了形狀最佳化問題的移動格線有限元方法.接下來介紹了求解離散的形狀最佳化問題的一種基於重疊型區域分解算法的全耦合併行LNKSz算法.此類全耦合算法雖然避免了傳統算法中收斂性,並行性差和計算量大的缺點,但也帶來了新的困難.首先,此類算法中需要求解的非線性方程組的維數是傳統算法中的非線性方程組維數的兩到三倍.其次,此非線性方程組所對應的Jacobian矩陣的條件數一般都會變的非常大.從而設計一種好的預處理運算元成為此類全耦合算法中非常重要的一部分.此預處理運算元需要同時具有降低Jacobian矩陣的條件數的能力和很好的並行效果.本博士論文設計了一種具有以上能力的求解形狀最佳化問題的預處理運算元：限制Schwarz預處理運算元.將經典的限制|Schwarz預處理運算元套用到此類形狀最佳化問題並非一件簡單的事.由於此類問題的複雜性,將經典限制|Schwarz預處理運算元套用到形狀最佳化中時需要進行一些修正,如各個變數的排序和劃分等等.我們分別介紹了適用於形狀最佳化問題的一水平(one-level)和兩水平(two-level)限制Schwarz預處理運算元.在構造兩格線限制Schwarz預處理運算元時發現,經典的從粗格線到細格線的插值運算元並不適用此類問題.從而設計了一種新的從粗格線到細格線的插值運算元.作為套用,我們用此算法研究了醫學上心臟插管手術中管道的形狀設計問題和治療血管阻塞的血管搭橋手術中橋樑的形狀設計問題.從數值結果看,本文提出的的算法收斂性很好,且在上千個處理器的大型並行計算機上的並行效果也很好. 本文前四章研究的形狀最佳化問題,由於問題的複雜性,在其求解算法的收斂性和收斂速度方面尚無理論分析.在論文的最後一章,我們嘗試在這方面做一些初步的理論分析研究.我們首先將問題簡化,考慮了一類簡單的非線性最佳化問題,針對這類問題,提出了一種新的子空間校正算法,並對其收斂性和收斂速度進行了詳細分析.

形狀最佳化問題的並行區域分解算法研究

基本介紹

相關詞條

熱門詞條