初始點(diǎn)任意的解非線(xiàn)性不等式約束優(yōu)化問(wèn)題的結(jié)合共軛梯度參數(shù)的超記憶梯度廣義投影算法

1、 初始點(diǎn)任意的解非線(xiàn)性不等式約束優(yōu)化問(wèn)題的結(jié)合共軛梯度參數(shù)的超記憶梯度廣義投影算法*孫清瀅 劉新海石油大學(xué)應(yīng)用數(shù)學(xué)系，山東，東營(yíng) 257061 GENERALIZED SUPER-MEMORY GRADIENT PROJECTION METHOD WITH ARBITRARY INITIAL POINT AND CONJUGATE GRADIENT SCALAR FOR NONLINEAR PROGRAMMING WITH NONLINEAR IN-EQUALITY CONSTRAINTSSun Qingying，liu xinhaiDepart. of Applied Mathematics

2、, University of petroleum, Dongying, 257061Abstract In this paper, by using generalized projection matrix, conditions are given on the scalars in the super-memory gradient direction to ensure that the super-memory gradient projection direction is a descent direction. A generalized super-memory gradi

3、ent projection method with arbitrary initial point for nonlinear programming with nonlinear in-equality constraints is presented. The global convergence properties of the new method are discussed. Combining with conjugate gradient scalar with our new method, a new class of generalized super-memory g

4、radient projection methods with conjugate gradient scalar is presented. The numerical results illustrate that the new methods are effective.Key words: Nonlinear programming, General projection, Nonlinear in-equality constraints, Super-memory gradient, Arbitrary initial point, Convergence 關(guān)鍵詞: 非線(xiàn)性規(guī)劃，

5、廣義投影, 非線(xiàn)性不等式約束，超記憶梯度，任意初始點(diǎn), 收斂1. 引言 梯度投影法是求解非線(xiàn)性約束最優(yōu)化問(wèn)題的基本方法之一，在最優(yōu)化領(lǐng)域占有重要地位16. 如高自友在文3中建立了求解非線(xiàn)性不等式約束優(yōu)化問(wèn)題的計(jì)算量小，算法穩(wěn)定的任意初始點(diǎn)下的廣義梯度投影算法, 但算法收斂速度慢. 超記憶梯度算法是求解無(wú)約束規(guī)劃的有效算法. 這類(lèi)方法在迭代中較多地利用了已經(jīng)得到的目標(biāo)函數(shù)的某些信息，因而具有較快的收斂速度78. 若能將此法推廣用于求解約束優(yōu)化問(wèn)題，可望改善現(xiàn)有算法的收斂速度. 高自友在文9 建立了求解非線(xiàn)性不等式約束優(yōu)化問(wèn)題的超記憶梯度算法. 時(shí)貞軍10,11對(duì)無(wú)約束規(guī)劃（p）提出了一種參數(shù)取值

6、為區(qū)間的改進(jìn)共軛梯度算法，并在水平集有界的條件下證明了算法的收斂性質(zhì). 受文獻(xiàn)9, 10, 11的啟發(fā)，本文利用廣義投影矩陣，對(duì)求解無(wú)約束規(guī)劃的超記憶梯度算法中的參數(shù)給出一種新的取值范圍以保證得到目標(biāo)函數(shù)的超記憶梯度廣義投影下降方向，并與處理任意初始點(diǎn)的方法技巧結(jié)合建立求解非線(xiàn)性不等式約束優(yōu)化問(wèn)題的一個(gè)初始點(diǎn)任意的超記憶梯度廣義投影算法，并在較弱條件下證明算法的收斂性. 同時(shí)給出具有好的收斂性質(zhì)的結(jié)合FR，PR，HS共軛梯度參數(shù)的超記憶梯度廣義投影算法, 從而將經(jīng)典的共軛梯度法推廣用于求解約束規(guī)劃問(wèn)題. 新算法保留梯度廣義投影算法的優(yōu)點(diǎn)，改進(jìn)了廣義梯度投影算法的收斂速度. 算法需要較小的存儲(chǔ)，

7、適合于大規(guī)模非線(xiàn)性不等式約束優(yōu)化問(wèn)題的計(jì)算. 數(shù)值例子表明算法是有效的. * 國(guó)家自然科學(xué)基金（10171055）資助項(xiàng)目2. 問(wèn)題與算法 考慮問(wèn)題（p）：，其中. 記，, , ; 為 維對(duì)角矩陣，其主對(duì)角元為： 本文始終假設(shè)： （H1）： （H2）：為線(xiàn)性無(wú)關(guān)的向量組，其中 . 和任何方向 ，定義：，稱(chēng)為 在 處關(guān)于方向 的方向?qū)?shù). 引理1. 如果 則 和任意方向 ，我們有 . 由引理1知，我們不妨記 ，顯然有. 引理2. ，矩陣正定. ，令： ， ， ，其中為階單位矩陣，我們稱(chēng)為 處的廣義投影矩陣。 引理3. ，矩陣 的任一特征值 滿(mǎn)足 . 對(duì)問(wèn)題 (P) 的非 K-T 點(diǎn)， 令： ，

8、. 按以下條件選取參數(shù), : （1） （2）其中， 為常數(shù).條件（1）實(shí)質(zhì)上給出了的一個(gè)取值范圍， 即 （3）（i） 當(dāng)時(shí)，由（3）得 .(ii)當(dāng)時(shí)，由（3）得 .由引理 3 知 . 因此可取 ： (4) 其中 , (5) . (6)其中 是和的夾角.引理 4. 若為問(wèn)題(P)的非 K-T 點(diǎn)，滿(mǎn)足（4），（5）和（6），則 .證明. 當(dāng)時(shí), 結(jié)論顯然成立. 以下分兩種情況討論: 1. . . （7）由 及（7）知結(jié)論成立。 2. . . （8）由及（8）知結(jié)論成立.在條件下, 條件(2)實(shí)質(zhì)上給出了的一個(gè)取值范圍，即. (9) （i）當(dāng)時(shí)，由（9）得 . (ii) 當(dāng)時(shí)，由（9）得 .由引

9、理4知可?。?, (10)其中 , (11) , (12)其中 是和的夾角.引理 5. 若為問(wèn)題(P)的非 K-T點(diǎn)，滿(mǎn)足（4），（5）和（6），滿(mǎn)足（10），（11）和（12）, 則 .證明. 當(dāng)時(shí)，結(jié)論顯然成立。以下分兩種情況討論： 1. . . （13）由 及（13）知結(jié)論成立。 2. . . （14）由 及（14）知結(jié)論成立. 引理6 若為問(wèn)題(P)的非K-T點(diǎn)，滿(mǎn)足（4），（5）和（6），滿(mǎn)足（10）,（11）和（12）, 則 . 初始點(diǎn)任意的超記憶梯度廣義投影算法(PSMGM): 設(shè) 為連續(xù)函數(shù)且滿(mǎn)足 , 其中. (1) 任取，, , 令 ;(2) 計(jì)算和.若有 和 同時(shí)成立時(shí),

10、為問(wèn)題(p)的K-T點(diǎn),停；否則,轉(zhuǎn)（3）；(3) 令, 其中， 滿(mǎn)足 (4), (5) 和 (6), 滿(mǎn)足 (10), (11) 和 (12)； （4）令，其中 （5） 令，其中是中滿(mǎn)足下列（a）或（b）的 最大值：(a) 若，則 (b) 若，則. （6）令，轉(zhuǎn)步（2）. 注： 算法步驟5（b）中的. 結(jié)合FR，PR，HS 共軛梯度法，給出的選取方法如下： ； ； .從而得到具有好的收斂性質(zhì)的結(jié)合FR，PR，HS共軛梯度參數(shù)的初始點(diǎn)任意的超記憶梯度廣義投影算法, 分別記為 PSFRM，PSPRM，PSHSM；取，算法退化為文獻(xiàn)3中的算法. 通過(guò)數(shù)值例子發(fā)現(xiàn)，, 的取法對(duì)算法收斂速度的影響很大

11、，適當(dāng)選取, 可有效地改善算法的收斂結(jié)果. 引理7. 若和同時(shí)成立，則為問(wèn)題（p）的K-T點(diǎn). 引理8 （1）當(dāng)，應(yīng)有；（2）若且為非K-T點(diǎn)，則必有，.證明. （1）對(duì)，我們有 . （15） 又因?yàn)?. 由于時(shí)，并注意到和的定義，應(yīng)有.（2）若，則，又若為問(wèn)題（p）的非K-T點(diǎn)，則由引理7及（15）式可得，. 同（1）可證：. 引理9. （1）若且為問(wèn)題（p）的非K-T點(diǎn)，則必為問(wèn)題（p）在處的可行下降方向；(2) 當(dāng)，則必為的一個(gè)下降方向.證明. 因?yàn)?（16） （17）（1） 因?yàn)?，則, 因而 . 由引理8及（17）知，.（2） 當(dāng)時(shí)，由（17）式知，, 有 .再由引理1的結(jié)論易知 .

12、（18） 注: 由引理9及步驟5（a）易知：若，則一定有，所以對(duì)算法產(chǎn)生的點(diǎn)列，若某步后，則以后由算法產(chǎn)生的點(diǎn)均為可行點(diǎn).3. 全局收斂性定理1. 如果（H1），（H2）成立，且處由算法產(chǎn)生的可行點(diǎn)組成的無(wú)窮點(diǎn)列，則其任一極限點(diǎn)都是問(wèn)題（p）的K-T點(diǎn).證明. 仿文獻(xiàn)4之定理3易證. 下設(shè)是由算法產(chǎn)生的非可行點(diǎn)組成的無(wú)窮點(diǎn)列，設(shè)其有極限點(diǎn)，注意到，只有有限多種選擇，故可找到子列，使其滿(mǎn)足： （i） （ii）與無(wú)關(guān).記作，注意到此時(shí)是一連續(xù)函數(shù)，則，又，可知是有界序列，故可取出收斂的子列，再由，及引理6知是有界序列，取其子列，是一無(wú)窮子集，這樣對(duì)可定義: ，顯然有 ，. 再定義： . 顯然應(yīng)有

13、. （19）這是因?yàn)?，都有? 令得 . 故由的定義知（a）式成立, 且.引理10. 設(shè)是一個(gè)由算法產(chǎn)生的非可行點(diǎn)組成的無(wú)窮點(diǎn)列，其極限點(diǎn)為問(wèn)題（p）的非K-T點(diǎn)，則一定有. 證明. 設(shè)，分兩種性況討論.(i) 若，由（18）式，令，并，注意到 則 . （20）因且為問(wèn)題（p）的非K-T點(diǎn)，故由引理8的證明易知，從而 由（20）式知此時(shí).(ii) 若，則由（20）式有 ,令: 得 . 定理2. 若是由算法產(chǎn)生的一個(gè)非可行點(diǎn)組成的無(wú)窮點(diǎn)列，則的任一極限點(diǎn)均是問(wèn)題（p）的K-T點(diǎn). 證明. 設(shè)，且假設(shè)不是問(wèn)題（p）的K-T點(diǎn)，由于是單調(diào)下降序列，則有 . (i) 當(dāng)時(shí)，由步驟5（b）知 ,令得：,

14、 此與引理10的結(jié)論矛盾.(ii) 當(dāng)時(shí)，由引理10知存在使得.因?yàn)榍?，則當(dāng)充分大時(shí)有 . （21） 由方向?qū)?shù)定義，有 ，從而由是連續(xù)函數(shù)且，則必存在和充分大的有 . (22)故根據(jù)步驟5(b)中的選擇規(guī)則并注意到(21), (22)式易知這種情況不出現(xiàn). 這樣, 由上述(i), (ii) 知必為問(wèn)題(p)的K-T點(diǎn).定理3. 若(H1),(H2)成立, 則算法或者有限步終止于問(wèn)題(p)的K-T點(diǎn), 或者產(chǎn)生無(wú)窮點(diǎn)列, 其任一極限點(diǎn)都是問(wèn)題 (p) 的K-T點(diǎn). 4. 數(shù)值例子 本節(jié)選擇了文獻(xiàn)5中的幾個(gè)算例，對(duì)本文算法進(jìn)行數(shù)值實(shí)驗(yàn)，在P-III933機(jī)器上利用matlab 編制程序，計(jì)算結(jié)果

15、表明算法是有效的. 用 IT 表示算法的迭代次數(shù)，F(xiàn)IT 表示算法到達(dá)可行域的迭代次數(shù)，t 表示所用時(shí)間，表示最優(yōu)解， 表示最優(yōu)值. 取, , , , ，,（PSCGM）. 例題給出在下三個(gè)不同初始點(diǎn)的計(jì)算結(jié)果. 例1 , s.t. . 最優(yōu)解為, 最優(yōu)值為. （PSMGM ）FITITt(8,8)010(0.5191,0.2405)0.50100.0499s(0,1)112(0.5239,0.2382)0.50160.0499s(-11,2)514(0.5196,0.2403)0.50100.0000s （PSFRM ）FITITt(8,8)013(0.4979,0.2514)0.50070

16、.2600s(0,1)323(0.5021,0.2492)0.50060.1600s(-11,2)629(0.5143,0.2431)0.50090.5999s （PSPRM ）FITITt(8,8)017(0.5051,0.2475)0.50040.1600s(0,1)122(0.4902,0.2575)0.50570.2600s(-11,2)117(0.5026,0.2490)0.50070.5500s （PSHSM ）FITITt(8,8)014(0.5075,0.2464)0.50040.1700s(0,1)324(0.4979,0.2512)0.50040.6000s(-11,2)5

17、22(0.5060,0.2471)0.50040.3899s例2 ,s.t. . 最優(yōu)解為, 最優(yōu)值為.（PSMGM ）FITITt(0,0)04(0.9924,0.9960)1.01510.0000s(-1,-1)14(0.9873,0.9927)1.02550.0000s(1,-1)13(0.9925,0.9971)1.01480.0000s （PSFRM ）FITITt(0,0)06(0.9921,1.0028)1.01560.0599s(-1,-1)37(0.9936,0.9970)1.01270.0000s(1,-1)16(0.9924,1.0021)1.01510.0600s （P

18、SPRM ）FITITt(0,0)06(0.9912,1.0043)1.01750.0000s(-1,-1)26(0.9895,0.9969)1.02090.0499s(1,-1)17(0.9907,1.0024)1.01860.4999s （PSHSM ）FITITt(0,0)06(0.9921,1.0028)1.01560.0000s(-1,-1)48(0.9904,0.9997)1.01910.0000s(1,-1)16(0.9924,1.0021)1.01510.0499s例3. ; s. t. . 最優(yōu)解為, 最優(yōu)值為. （PSMGM ）FITITt(0,0)03(0.8912,0)

19、1.01180.0000s(2,0)1618(0.9662,0.0030)1.00110.0500s(0,2)412(0.9318,-0.0034)1.00460.0500s （PSFRM ）FITITt(0,0)06(0.9138,0)1.00740.0600s(2,0)2020(0.9840,0)1.00020.0500s(0,2)2328(0.9453,-0.0037)1.00290.2799s （PSPRM ）FITITt(0,0)06(0.9118,0)1.00770.1099s(2,0)1919(0.9224,0)1.00600.0599s(0,2)2027(0.9841,0.00

20、00)1.00020.5000s （PSHSM ）FITITt(0,0)06(0.9138,0)1.00740.0599s(1,2)3953(0.9429,0.0063)1.00320.5500s(0,2)2633(0.9914,0.0021)1.00000.1700s 作者感謝審稿人和編輯對(duì)本文提出的寶貴意見(jiàn)。參 考 文 獻(xiàn)1 J. B. Rosen, The Gradient Projection Method for Nonlinear Programming, part I-Linear Constraints. J. SIAM, 8:1 (1960), 182-217.2 J. B. Rosen, The Gradient Projection Method for Nonlinear Programm