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

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

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

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

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

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

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