最優(yōu)化問題的Lanczos路徑方法.pdf

1、最優(yōu)化(Optimization)，就是在復(fù)雜環(huán)境中遇到的許多可能的決策中，挑選“最好”決策的科學(xué)。在本世紀(jì)30年代末，由于軍事和工業(yè)生產(chǎn)發(fā)展的需要，提出了一些不能用古典微分法和變分法解決的問題。在許多學(xué)者和專家的共同努力下，逐漸產(chǎn)生、發(fā)展和形成了一些新的方法，即最優(yōu)化方法。它是一門應(yīng)用十分廣泛的學(xué)科，隨著計算機(jī)的日趨發(fā)展，以及工程設(shè)計，系統(tǒng)識別，管理科學(xué)等方面的不斷深入，最優(yōu)化的應(yīng)用越來越廣泛。本文將探討用Lanczos路徑方法解非線

2、性最優(yōu)化問題。 Lanczos方法，是用來求解對稱方程組Ax=b的解，將對稱矩陣A進(jìn)行三對角化然后再利用回代技術(shù)求出方程的解。它也可以用來解特定的大規(guī)模稀疏對稱特征值問題Ax=λx。該方法涉及到給定的矩陣A進(jìn)行局部三對角化。重要的是，在算法過程中不會有滿的子矩陣產(chǎn)生，同樣重要的是，A的兩端的特征值的信息在三對角化完成之前早得多就已經(jīng)出現(xiàn)。 共軛梯度法是最優(yōu)化中常用的方法之一，由于具有算法簡便，只需要一階信息，易于編程，以

3、及需要存儲空間小等優(yōu)點，共軛梯度法已經(jīng)成為求解大規(guī)模問題的一種主要方法。Bulteau和Vial在[7]中構(gòu)造了無約束最優(yōu)化問題的共軛梯度路徑，其基本思想是將標(biāo)準(zhǔn)共軛方向法應(yīng)用于無約束優(yōu)化目標(biāo)函數(shù)．廠的局部二次近似函數(shù)，得到一組共軛方向序列。共軛梯度路徑定義為該共軛方向序列的線性組合，獲得了共軛梯度路徑的一些重要性質(zhì)?？梢宰C明當(dāng)共軛梯度路徑中的參數(shù)趨向于無窮時，產(chǎn)生的搜索方向即為牛頓步或者擬牛頓步，以導(dǎo)致算法局部超線性收斂的一個重要依據(jù)

4、。 Lanczos方法和共軛梯度路徑法的思想啟迪我們，如果將二者相結(jié)合，構(gòu)造一條新的路徑，使得這條路徑既具有Lanczos向量的性質(zhì)，又具有共軛向量的性質(zhì)。最優(yōu)化問題的近似二次模型應(yīng)用Lanczos方法過程中同時應(yīng)用共軛梯度法，即對問題三對角化的同時也計算出了共軛方向序列，這樣可以得到Lanczos方向序列和共軛方向序列，由此生成一條新的路徑，稱為Lanczos路徑。此路徑有類似于共軛梯度路徑的一些重要性質(zhì)，在合理的假設(shè)下，證明

5、了此算法具有整體收斂性和局部超線性收斂速率。數(shù)值實驗，表明Lanczos路徑法對于解大型稀疏優(yōu)化問題有更顯著的收斂速率。 本文共分為四章。第一章簡單地介紹了無約束優(yōu)化，約束優(yōu)化的一些基本概念；Lanczos法，共軛梯度法及信賴域方法等內(nèi)容。第二章用Lanczos路徑法求解線性等式約束最優(yōu)化問題，通過構(gòu)造原問題的零空間，將Lanczos法和共軛梯度法相結(jié)合應(yīng)用于零空間中的近似二次模型，構(gòu)造了Lanczos路徑，利用線性搜索技術(shù)得到

6、接受步長，證明了算法既具有整體收斂性又保持了局部超線性收斂速率。在本章最后給出了部分題目的數(shù)值結(jié)果。第三章中給出了有界變量約束優(yōu)化問題的非單調(diào)預(yù)處理Lanczos路徑算法，先構(gòu)造預(yù)處理Lanczos路徑，沿這條路徑獲得搜索迭代方向，利用非單調(diào)回代技術(shù)得到可接受的步長因子，從而獲得新的有足夠下降的迭代點。非單調(diào)能克服高度非線性化函數(shù)的最優(yōu)化問題。在本章最后給出了數(shù)值結(jié)果，表明所提供的算法有效性。最后一章，對本文的工作進(jìn)行總結(jié)，并提出進(jìn)一步