解帶線性或非線性約束最優(yōu)化問題的三項(xiàng)記憶梯度Rosen投影算法

1、解帶線性或非線性約束最優(yōu)化問題的三項(xiàng)記憶梯度Rosen投影算法孫清瀅石油大學(xué)應(yīng)用數(shù)學(xué)系，山東, 東營 257062摘要 利用 Rosen 投影矩陣, 建立求解帶線性或非線性不等式約束優(yōu)化問題的三項(xiàng)記憶梯度Rosen投影下降算法，并證明了算法的收斂性. 同時給出了結(jié)合FR，PR，HS共軛梯度參數(shù)的三項(xiàng)記憶梯度Rosen投影算法，從而將經(jīng)典的共軛梯度法推廣用于求解約束規(guī)劃問題. 數(shù)值例子表明算法是有效的.關(guān)鍵詞 非線性規(guī)劃， Rosen投影，三項(xiàng)記憶梯度，收斂分類號: AMS(1991) 49M07, 90C30 中圖分類號: 0221.2 文獻(xiàn)標(biāo)識碼: A 0 引言 Rosen 梯度投影法1,2

2、是求解非線性最優(yōu)化問題的基本方法之一，梯度投影算法與其它方法結(jié)合得到了許多有效算法，在最優(yōu)化領(lǐng)域占有重要地位. 如陳廣軍在文3中，利用Rosen投影建立了解帶線性或非線性約束最優(yōu)化問題的計算量小，穩(wěn)定的梯度投影算法，但收斂速度慢. 超記憶梯度算法是求解無約束規(guī)劃的有效算法, 由于算法在迭代中較多地利用了已經(jīng)得到的目標(biāo)函數(shù)的某些信息，因而具有較快的收斂速度，大量的數(shù)值例子證明了這一點(diǎn)5. 趙慶貞6對超記憶梯度算法進(jìn)行改進(jìn)，在理論上證明了算法在一定條件下具有步超線性收斂速度. 若能將此法推廣用于求解約束優(yōu)化問題，可望改善現(xiàn)有梯度投影算法的收斂速度. 時貞軍7,8對無約束規(guī)劃提出了一種在Armijo

3、步長搜索下較FR，PR共軛梯度法有效的超記憶梯度算法. 王宜舉等9對一般閉凸集約束下的優(yōu)化問題通過GLP投影建立了一族記憶梯度GLP投影算法. 受文8,9的啟發(fā), 本文利用 Rosen 投影矩陣，對求解無約束規(guī)劃的三項(xiàng)記憶梯度算法中的參數(shù)給一條件確定參數(shù)的取值范圍以保證得到目標(biāo)函數(shù)的三項(xiàng)記憶梯度Rosen投影下降方向，從而建立求解帶線性或非線性約束最優(yōu)化問題的三項(xiàng)記憶梯度Rosen 投影算法，并證明算法的收斂性. 新算法保留梯度Rosen投影算法的優(yōu)點(diǎn)，改進(jìn)Rosen梯度投影算法的收斂速度. 數(shù)值例子表明算法是有效的. 1問題、假設(shè)與算法 考慮問題（p）：,其中，設(shè)，當(dāng)時，為線性函數(shù)；當(dāng)時，為

4、非線性函數(shù). 再設(shè)，記， 對于指標(biāo)集，表示J中指標(biāo)的個數(shù)，并記 =, . 設(shè)M為問題（p）的K-T點(diǎn)集，對于，總假設(shè)條件（H）成立： （H）: . 引理 設(shè)，則S滿足正則條件（H）的充要條件為對于S的任一有界子集, 存在使得 ，. 這里約定：當(dāng)時，. 若有線性等式約束, 則不必作此約定. 設(shè), 令，滿足 ，其中.令：；其中，為階單位矩陣，稱為Rosen 投影矩陣. 引理 設(shè)，對于，若，, 則為問題（p）之K-T點(diǎn). 對問題（p）的非K-T點(diǎn)， 令： ， , 按下面條件選取參數(shù): （1）(2)其中為參數(shù). 條件（1）實(shí)質(zhì)上給出了的一個取值范圍，即： ， (3) , (4) , (5) 其中是和的

5、夾角. 引理3 若為問題 (p) 的非K-T點(diǎn), 滿足 (3), (4) 和 (5), 則. 證明 當(dāng)時， 結(jié)論顯然成立. 1. : 由的定義和的取法知 . (6)由 及（6）知結(jié)論成立.2. ：由的定義和的取法知 . （7）由 及（7）知結(jié)論成立. 在條件下，條件（2）實(shí)質(zhì)給出了的一個取值范圍，即： , (8) , (9) . (10)其中是和的夾角. 引理4 若為問題 (p) 的非K-T點(diǎn), 滿足 (3), (4) 和 (5), 滿足 (8),(9) 和 (10), 則. 證明 當(dāng)時，結(jié)論顯然成立. 1. ：由引理3，的定義和的取法知. (11)由 及（11）知結(jié)論成立.2. ：由引理3，

6、的定義和的取法知 . (12)由 及（12）知結(jié)論成立. 引理5 若 為問題 (p) 的非K-T點(diǎn), 滿足 (3), (4) 和 (5), 滿足 (8), (9) 和 (10), 則 . 證明 由及, 的定義易證. 求解帶線性或非線性約束最優(yōu)化問題的三項(xiàng)記憶梯度Rosen 投影算法（PTMG）： 設(shè)為二個連續(xù)函數(shù)且滿足： , ，其中. 又設(shè)為R 上非負(fù)連續(xù)函數(shù)，為R 上正值連續(xù)函數(shù)且在R的任一有界子集上有正的下界. （1） ， ， , 令；（2） 令. 如果，則轉(zhuǎn)步（3）；否則，令： , ，轉(zhuǎn)步（2）；（3） 計算： ，. 如果 ，則 停，為（p）之K-T點(diǎn); 否則，轉(zhuǎn)步（4）； （4） 其中

7、， 滿足（3），（4），（5）；滿足（8），（9），（10）. （5）令，其中是中滿足下列兩式的最大值 且 . 令轉(zhuǎn)步（2）. 注：結(jié)合FR，PR，HS 共軛梯度法，可給出的選取方法： ； ； .其中, , . .。. 從而得到結(jié)合FR，PR，HS算法的三項(xiàng)記憶梯度Rosen投影算法, 分別記為 PTFR，PTPR，PTHS；取，算法退化為文獻(xiàn)3Rosen梯度投影算法, 記為 PGM. 引理6 若，且為問題（p）的非K-T點(diǎn)，則為在點(diǎn)的下降方向. 證明 . 由，且為問題（p）的非K-T點(diǎn)及引理2知 . 引理7 若，且為問題（p）的非K-T點(diǎn), 則為R在點(diǎn)的可行方向，即，且存在使得. 證明 由引

8、理6知，對，由于，故存在使得： ，. 對于，由于 ，而 . 故有: （i）. 若，則 若，則于是存在使得：. （ii）. 若，則 ;若，則而 ，于是存在且 ，使得 .令，則 且 .2收斂性 引理8 假設(shè)條件（H）成立，算法產(chǎn)生無窮點(diǎn)列，若存在使得，N, 則必有. 證明 若存在使得，N, 則由算法知，. 因?yàn)?，設(shè)無窮子列使得，則有，于是，由假設(shè)（H）知，必有. 若引理8中的不存在，則為N之無窮子列，且和有相同的聚點(diǎn). 設(shè)為的任一有限聚點(diǎn)，則存在無窮子列使得，如果為問題（p）之非K-T點(diǎn)，則有： 引理 若為問題（p）之非K-T點(diǎn), 則存在，使得. 引理 若為問題（p）之非K-T點(diǎn), 則 滿足 且有

9、 ，.由取法的有限性知, 存在使得，其中為之無窮子列，由于，由引理10知, 于是，所以存在，且由之連續(xù)性知，（）. 由的構(gòu)造及引理5知有界且數(shù)列 有界，故可令 ， . 引理11 若為問題（p）之非K-T點(diǎn), 則，進(jìn)而, 進(jìn)而 . 證明 當(dāng)充分大時有 .令 得 .其中. 故若，則，因而為（p）之K-T點(diǎn)，矛盾. 因而，進(jìn)而, 再由引理6之證明知 ，故. 引理12 若為問題（p）之非K-T點(diǎn), 則 存在及，使得，. 證明 仿照文3引理6易證. 定理1 若假設(shè)條件（H）成立，算法產(chǎn)生無窮點(diǎn)列，若不存在使得，N, 設(shè)無限點(diǎn)列之任一有限聚點(diǎn)，則是問題（p）之K-T點(diǎn). 證明 (1). 若，在不等式中兩邊

10、令得，與引理11矛盾；(2). 若，不妨設(shè)，由 及的取法知，當(dāng)充分大時， ，其中. 令得，由知，與引理11矛盾. 故必為（p）之K-T點(diǎn). 定理2 若假設(shè)條件（H）成立，則算法或者在某一步終止于問題（P）的K-T點(diǎn)，或者產(chǎn)生無限點(diǎn)列，其任一有限聚點(diǎn)均為問題（p）之K-T點(diǎn). 證明 由引理2，引理8和定理1可證.3數(shù)值例子 本節(jié)選擇了文3中的幾個算例，對本文算法在P-III933機(jī)器上利用matlab編制程序進(jìn)行數(shù)值實(shí)驗(yàn), 計算結(jié)果表明算法是有效的, 特別是在規(guī)模較大時，新算法具有更好的表現(xiàn). 在PTMG()，PTFR，PTPR，PTHS算法中，取, , , , , . 用IT表示算法的迭代次數(shù)

11、，t 表示所用時間，表示最優(yōu)解， 表示最優(yōu)值.例1 ,s.t. .初始點(diǎn); 最優(yōu)解為, 最優(yōu)值為. methodITTPTMG14,20(0.5096,0.2454),(0.5012,0.2494)0.5005,0.50000.8200s,1.4200sPTFR12,18(0.5106,0.2465),(0.5013,0.2493)0.5038,0.50000.5500s,1.2600sPTPR18,25(0.5134,0.2433),(0.5.12,0.2493)0.5004,0.50000.7700s,1.5300sPTHS19,19(0.5095,0.2453),(0.5012,0.24

12、94)0.5003,0.50000.8300s,1.4200s 例2 ,s.t. 初始點(diǎn); 最優(yōu)解為，最優(yōu)值為. methodITTPTMG9,17(0.0465,0.0465,1.9979),(0.0076,0.0076,1.9999)-1.9945,-1.99900.0500s,0.1000sPTFR15,23(0.0189,0.0333,1.9966),(0.0065,0.0070,1.9999)-1.9900,-1.99920.1100s,0.1100sPTPR11,17(0.0228,0.0241,1.9989),(0.0074,0.0070,1.9999)-1.9941,-1.99

13、910.1100s,0.1100sPTHS11,22(0.0418,0.0195,1.9954),(0.0069,0.0063,1.9999)-1.9862,-1.99920.1100s,0.1700s 例3 ,s.t. . 初始點(diǎn); 最優(yōu)解為, 最優(yōu)值為. methodITTPTMG25,31(0.9978,1.0022),(0.9998,1.0002)1.0044,1.00050.0500s,0.1100sPTFR25,26(0.9974,1.0026),(0.9996,1.0004)1.0053,1.00080.0500s,0.1000sPTPR26,28(0.9973,1.0027),

14、(0.9997,1.0002)1.0053,1.00070.0600s,0.1100sPTHS25,26(0.9974,1.0028),(0.9996,1.0004)1.0053,1.00080.0500s,0.1100s 作者感謝審稿人和編輯對本文提出的寶貴意見.參考文獻(xiàn)：1 Rosen, J. B. The gradient projection method for nonlinear programmingJ, part I, Linear constraints. J. SIAM, 1960, 8(1): 182-217.2. Rosen, J. B. The gradient pr

15、ojection method for nonlinear programmingJ, Part II, Nonlinear constraints. J. SIAM, 1960, 9(4): 514-532.3. 陳廣軍，一個解帶線性或非線性約束最優(yōu)化問題的梯度投影算法J，計算數(shù)學(xué)，1987, 49: 356-364.4. 賴炎連等，非線性最優(yōu)化的廣義梯度投影方法J，中國科學(xué)A輯，1992, 9: 916-924.5. 孫麟平，無約束極小化的自是適應(yīng)多信息下降算法J, 高校計算數(shù)學(xué)學(xué)報，1982, 14(2): 107-114.6. 趙慶貞，一個改進(jìn)的超記憶梯度法的收斂性及斂速估計J, 應(yīng)用

16、數(shù)學(xué)學(xué)報，1983, 6(3): 376-385.7. 時貞軍，無約束優(yōu)化的超記憶梯度算法J，工程數(shù)學(xué)學(xué)報，2000, 17(2): 99-104.8. 時貞軍, 改進(jìn)HS 共軛梯度算法及其全局收斂性J，計算數(shù)學(xué)，2001，23(4): 393-406.9. Wang Yiju, Wang Changyu and Xiu, Naihua, A family of super-memory gradient projection methods for constrained optimizationJ, Optimization, 2002, 51(6) : 889-905. Three-Te

17、rm memory Gradient Rosen Projection Method for Nonlinear Programming with Linear or Nonlinear In-equality ConstraintsSun QingyingDepart. of Applied Maths, University of petroleum, Dongying, 257062Abstract In this paper, by using projection matrix, a new descent three-term memory gradient projection method for nonlinear programming with linear or nonlinear in-equality constraints is presented. The global convergence properties of the new method are discussed. Combining with conjugate gradient scalar with our new met