線性約束優(yōu)化的仿射內(nèi)點預條件共軛梯度路徑法.pdf

1、本文主要討論利用仿射投影既約預條件共軛梯度路徑內(nèi)點方法解帶線性等式約束和有界變量約束的最優(yōu)化問題。 共軛梯度法是最優(yōu)化中最常用的方法之一，它具有算法簡便、不需要矩陣存儲等優(yōu)點，十分適合于大規(guī)模優(yōu)化問題。無約束優(yōu)化問題的共軛梯度路徑構(gòu)造的思想啟迪我們用其來解帶線性等式約束和有界變量約束的優(yōu)化問題?；趶V義消去法，本文中原問題可轉(zhuǎn)化為等式約束矩陣的零空間中的一個無約束優(yōu)化問題。將共軛方向法應用于零空間中的近似二次模型，得到一組共軛方

2、向序列，共軛方向序列生成了共軛梯度路徑。共軛梯度路徑類似于信賴域的一些重要性質(zhì)，將對算法整體收斂性的證明起重要的作用。本文通過一個增廣系統(tǒng)解既約預條件方程，克服了既約矩陣不保持原矩陣的充分稀疏。在信賴域子問題中產(chǎn)生可行方向滿足嚴格可行性將導致計算的困難，使用嚴格可行的信賴域子問題可能要重復解多次才能接受步長，因此完成一次迭代的計算可能是昂貴和困難的。為了克服這一困難，本文通過引進一個仿射變換矩陣，構(gòu)造仿射投影既約預條件共軛梯度路徑來搜索

3、獲得迭代方向。當搜索方向不被接受時，采用回代線搜索技術(shù)得到可接受步長，從而定義新的迭代點。由此得到的算法不僅具有整體收斂性，而且保持快速的局部超線性收斂速率。 全文共分五章。第一章簡單地介紹最優(yōu)化的一些基本理論和概念。第二章構(gòu)造仿射投影既約預條件共軛梯度路徑，并給出其基本性質(zhì)，在此基礎上，結(jié)合既約預條件技術(shù)、共軛梯度路徑搜索策略、內(nèi)點仿射變換和回代線搜索技術(shù)等技巧提供了算法。第三章基于仿射共軛梯度路徑的良好性質(zhì)，在合理的假設條件