約束優(yōu)化問(wèn)題過(guò)濾不精確的既約Hessian法和正割法.pdf

1、在求解大規(guī)模非線(xiàn)性規(guī)劃和非線(xiàn)性方程組問(wèn)題的時(shí)候,想要在每一步迭代過(guò)程中都得到精確解將耗費(fèi)太多的時(shí)間,因此Dembo,Eisenstat和Steihaug提出了一種不精確牛頓方法用來(lái)求解大規(guī)模非線(xiàn)性方程組.在此之后,Dembo和Steihaug義將這類(lèi)方法應(yīng)用到求解無(wú)約束最小化問(wèn)題中.
　　 Byrd,Curtis和Nocedal曾提出過(guò)一種不精確序列二次規(guī)劃算法求解大規(guī)模等式約束最優(yōu)化問(wèn)題.這種算法可以確保整體收斂性.在算法中,

2、一個(gè)精確罰函數(shù)被用來(lái)判斷非線(xiàn)性規(guī)劃子問(wèn)題的不精確解是否被接受.不精確算法的使用將可以節(jié)省大量的計(jì)算時(shí)間.
　　 Fletcher和Leyffer提出了一類(lèi)濾子方法,在這種方法中不會(huì)要求選取罰參數(shù),而且它所得到的數(shù)值結(jié)果非常好.濾子方法的基本思想是尋找一個(gè)試探點(diǎn),如果這個(gè)試探點(diǎn)能夠改進(jìn)目標(biāo)函數(shù)的值(使目標(biāo)函數(shù)下降)或者改進(jìn)約束違反度(使其更靠近可行域),那么就接受該試探點(diǎn).后來(lái),濾子技術(shù)又被應(yīng)用到許多方法中,例如,序列線(xiàn)性規(guī)劃方法

3、,序列二次規(guī)劃方法(SQP),內(nèi)點(diǎn)法等等.在此之后,Fletcher和Leyffer通過(guò)應(yīng)用信賴(lài)域技術(shù)給出了濾子SQP方法的整體收斂性證明,Ulbrich又證明了算法的局部超線(xiàn)性收斂性.對(duì)于非線(xiàn)性等式約束優(yōu)化問(wèn)題,W(a)chter和Biegler提出了一種線(xiàn)搜索濾子方法并且討論了它的整體和局部收斂性.
　　 根據(jù)上面的思想和方法,本文提出一種結(jié)合線(xiàn)搜索濾子技術(shù)的不精確SQP方法,該方法將能夠確保整體收斂性和q階局部超線(xiàn)性收斂速

4、率.Fletcher和Leyffer曾注意到濾子方法類(lèi)似于罰函數(shù)法同樣會(huì)遇到Maratos效應(yīng),因此文章中將采用二階修正步來(lái)克服Maratos效應(yīng).另外,文中還將證明算法產(chǎn)生的點(diǎn)是q階超線(xiàn)性收斂的.
　　 投影既約Hessian方法和正割方法是求解非線(xiàn)性規(guī)劃的兩種最成功的方法.
　　 Coleman和Conn最早提出了使用近似雙邊投影既約Hessian陣的SQP算法.為了處理大規(guī)模問(wèn)題,Gurwitz提出一種雙邊投影既約

5、Hessian矩陣的兩塊矯正法.既約Hessian方法只需要Lagrangian函數(shù)的Hessian陣的部分信息,因此,在每步運(yùn)算中所需要的儲(chǔ)存量較少.本文將提出一種結(jié)合線(xiàn)搜索濾子技術(shù)的不精確雙邊投影既約Hessian方法.文中使用Lagrangian函數(shù)來(lái)代替濾子中的目標(biāo)函數(shù),如此做可以克服Maratos效應(yīng),這樣就避免了二階修正步的計(jì)算.另外,文中將證明算法的q階超線(xiàn)性收斂性.
　　 最近,針對(duì)非凸等式約束優(yōu)化,Byrd,C

6、urtis和Nocedal提出了一種不精確牛頓方法.該方法允許負(fù)曲率的存在,而無(wú)需非凸問(wèn)題的原始對(duì)偶迭代矩陣的慣性信息.本文將提出一種不精確的投影既約Hessian方法解決非凸問(wèn)題.采用線(xiàn)搜索技術(shù)以及將Fletcher罰函數(shù)作為價(jià)值函數(shù),能夠確保算法的整體收斂性.
　　 在大多數(shù)的既約Hessian方法中,當(dāng)前迭代點(diǎn)xk相應(yīng)約束的切空間的正交基會(huì)隨著k改變而改變.相比之下,正割方法具有的優(yōu)勢(shì)是它使用一個(gè)連續(xù)的正交投影算子.正割算

7、法的基本思想可以歸納為:在每步迭代中,方向步由水平方向步和垂直方向步合成.本文將提出一類(lèi)改進(jìn)的具有整體收斂性的不精確正割方法,這種方法還具有q階局部超線(xiàn)性收斂速率.此外,通過(guò)使用Fletcher罰函數(shù)作為價(jià)值函數(shù)避免了Maratos效應(yīng).還將證明在每次迭代中,如果對(duì)約束進(jìn)行一次額外的計(jì)算,新的算法將具有一步q階超線(xiàn)性收斂性.針對(duì)非凸問(wèn)題,本文同樣給出一類(lèi)不精確正割方法,在這類(lèi)方法中,將采用l1罰函數(shù)作為價(jià)值函數(shù).
　　 對(duì)于帶邊