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

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

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

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