非線性約束優(yōu)化問題的QP-FREE型算法研究.pdf

1、本文主要研究求解非線性約束優(yōu)化問題的QP-Free型算法. QP-Free算法,有時亦稱序列線性方程組算法,主要是針對傳統(tǒng)的序列二次規(guī)劃算法中存在的子問題不相容及計算工作量大等缺陷而提出的.論文共分為六個部分.首先,在第一章中我們回顧了求解非線性約束優(yōu)化問題的QP-Free和序列線性方程組算法的發(fā)展及研究現(xiàn)狀,并對現(xiàn)有的算法加以分類總結(jié),從而引出我們需要進一步解決的問題及本文的主要工作. 本文的第二部分,我們針對不等式約束優(yōu)化問

2、題,給出一個新的線性方程組與輔結(jié)合的可行下降算法.當?shù)綌?shù)充分大后,算法每步只需解一個線性方程輔助方向的投影矩陣只涉及近似有效約束集中的元素,計算量較以往大大嚴格互補松弛條件,算法全局且超線性收斂.在附加條件下可以達到二次第三部分,通過一個l<,1>-l<,∞>混合精確罰函數(shù),我們對既含等式約束又含不等式約束的一般約束優(yōu)化問題提出了一種非可行序列線性方程組算法,成功地解決了在無嚴格互補松弛條件的情況下建立其超線性收斂性這一重要研究課題

3、.算法引入了一種罰參數(shù)的自調(diào)整規(guī)則,每次迭代只需求解兩到三個同系數(shù)的線性方程組以得到迭代方向.在線性無關約束條件下,算法全局收斂到原問題的KKT點.另外,文中還將Facchinei- ischer-Kanzow,的有效集識別技術(shù)推廣到一般約束問題,提出了相應的識別函數(shù),并給出了推廣后的擬正則點的定義.在一個比強二階充分條件弱的假設下證明了算法的一步超線性收斂性. 在第四章中,我們給出了一個求解不等式約束優(yōu)化問題的可行有效集QP-

4、Free算法.算法每步迭代只需求解四個同系數(shù)的線性方程組,且只包含工作集中的約束,與現(xiàn)有的QP-Free算法相比,計算量大大減少且在較弱的假設條件下算法具有較快的收斂速度.特別的,為了確定工作集算法無需計算新的乘子估計而是利用上一步得到的近似乘子信息.同時,算法也不需要通過求解額外的線性方程組來選取線性無關約束梯度.此外,我們還引入了一個新技術(shù)用以避免由于對偶退化而可能導致的牛頓方程的病態(tài)性.在線性無關約束規(guī)范下,算法全局收斂到原問題的

5、KKT點,且在強二二階充分條件下算法具有局部超線性收斂速度而無需假設(i)嚴格互補松弛條件成立,(ii)所有的拉格朗日乘子都小于一個事先給定的數(shù).本文的第五部分,我們針對不等式約束變分不等式問題給出了一個序列線性方程組新算法.算法每步至多求解三個維數(shù)降低的線性方程組,且其中的兩個方程組具有相同的系數(shù)矩陣,從而大大減少了計算量并很好的解決了牛頓法中存在的子問題不相容的問題.特別的,如果映射F是強單調(diào)的,則算法全局收斂到變分不等式問題的唯一