解带线性或非线性约束最优化问题的三项记忆梯度Rosen投影算法

1、解带线性或非线性约束最优化问题的三项记忆梯度Rosen投影算法孙清滢石油大学应用数学系，山东, 东营 257062摘要 利用 Rosen 投影矩阵, 建立求解带线性或非线性不等式约束优化问题的三项记忆梯度Rosen投影下降算法，并证明了算法的收敛性. 同时给出了结合FR，PR，HS共轭梯度参数的三项记忆梯度Rosen投影算法，从而将经典的共轭梯度法推广用于求解约束规划问题. 数值例子表明算法是有效的.关键词 非线性规划， Rosen投影，三项记忆梯度，收敛分类号: AMS(1991) 49M07, 90C30 中图分类号: 0221.2 文献标识码: A 0 引言 Rosen 梯度投影法1,2

2、是求解非线性最优化问题的基本方法之一，梯度投影算法与其它方法结合得到了许多有效算法，在最优化领域占有重要地位. 如陈广军在文3中，利用Rosen投影建立了解带线性或非线性约束最优化问题的计算量小，稳定的梯度投影算法，但收敛速度慢. 超记忆梯度算法是求解无约束规划的有效算法, 由于算法在迭代中较多地利用了已经得到的目标函数的某些信息，因而具有较快的收敛速度，大量的数值例子证明了这一点5. 赵庆贞6对超记忆梯度算法进行改进，在理论上证明了算法在一定条件下具有步超线性收敛速度. 若能将此法推广用于求解约束优化问题，可望改善现有梯度投影算法的收敛速度. 时贞军7,8对无约束规划提出了一种在Armijo

3、步长搜索下较FR，PR共轭梯度法有效的超记忆梯度算法. 王宜举等9对一般闭凸集约束下的优化问题通过GLP投影建立了一族记忆梯度GLP投影算法. 受文8,9的启发, 本文利用 Rosen 投影矩阵，对求解无约束规划的三项记忆梯度算法中的参数给一条件确定参数的取值范围以保证得到目标函数的三项记忆梯度Rosen投影下降方向，从而建立求解带线性或非线性约束最优化问题的三项记忆梯度Rosen 投影算法，并证明算法的收敛性. 新算法保留梯度Rosen投影算法的优点，改进Rosen梯度投影算法的收敛速度. 数值例子表明算法是有效的. 1问题、假设与算法 考虑问题（p）：,其中，设，当时，为线性函数；当时，为

4、非线性函数. 再设，记， 对于指标集，表示J中指标的个数，并记 =, . 设M为问题（p）的K-T点集，对于，总假设条件（H）成立： （H）: . 引理 设，则S满足正则条件（H）的充要条件为对于S的任一有界子集, 存在使得 ，. 这里约定：当时，. 若有线性等式约束, 则不必作此约定. 设, 令，满足 ，其中.令：；其中，为阶单位矩阵，称为Rosen 投影矩阵. 引理 设，对于，若，, 则为问题（p）之K-T点. 对问题（p）的非K-T点， 令： ， , 按下面条件选取参数: （1）(2)其中为参数. 条件（1）实质上给出了的一个取值范围，即： ， (3) , (4) , (5) 其中是和的

5、夹角. 引理3 若为问题 (p) 的非K-T点, 满足 (3), (4) 和 (5), 则. 证明 当时， 结论显然成立. 1. : 由的定义和的取法知 . (6)由 及（6）知结论成立.2. ：由的定义和的取法知 . （7）由 及（7）知结论成立. 在条件下，条件（2）实质给出了的一个取值范围，即： , (8) , (9) . (10)其中是和的夹角. 引理4 若为问题 (p) 的非K-T点, 满足 (3), (4) 和 (5), 满足 (8),(9) 和 (10), 则. 证明 当时，结论显然成立. 1. ：由引理3，的定义和的取法知. (11)由 及（11）知结论成立.2. ：由引理3，

6、的定义和的取法知 . (12)由 及（12）知结论成立. 引理5 若 为问题 (p) 的非K-T点, 满足 (3), (4) 和 (5), 满足 (8), (9) 和 (10), 则 . 证明 由及, 的定义易证. 求解带线性或非线性约束最优化问题的三项记忆梯度Rosen 投影算法（PTMG）： 设为二个连续函数且满足： , ，其中. 又设为R 上非负连续函数，为R 上正值连续函数且在R的任一有界子集上有正的下界. （1） ， ， , 令；（2） 令. 如果，则转步（3）；否则，令： , ，转步（2）；（3） 计算： ，. 如果 ，则 停，为（p）之K-T点; 否则，转步（4）； （4） 其中

7、， 满足（3），（4），（5）；满足（8），（9），（10）. （5）令，其中是中满足下列两式的最大值 且 . 令转步（2）. 注：结合FR，PR，HS 共轭梯度法，可给出的选取方法： ； ； .其中, , . .。. 从而得到结合FR，PR，HS算法的三项记忆梯度Rosen投影算法, 分别记为 PTFR，PTPR，PTHS；取，算法退化为文献3Rosen梯度投影算法, 记为 PGM. 引理6 若，且为问题（p）的非K-T点，则为在点的下降方向. 证明 . 由，且为问题（p）的非K-T点及引理2知 . 引理7 若，且为问题（p）的非K-T点, 则为R在点的可行方向，即，且存在使得. 证明 由引

8、理6知，对，由于，故存在使得： ，. 对于，由于 ，而 . 故有: （i）. 若，则 若，则于是存在使得：. （ii）. 若，则 ;若，则而 ，于是存在且 ，使得 .令，则 且 .2收敛性 引理8 假设条件（H）成立，算法产生无穷点列，若存在使得，N, 则必有. 证明 若存在使得，N, 则由算法知，. 因为，设无穷子列使得，则有，于是，由假设（H）知，必有. 若引理8中的不存在，则为N之无穷子列，且和有相同的聚点. 设为的任一有限聚点，则存在无穷子列使得，如果为问题（p）之非K-T点，则有： 引理 若为问题（p）之非K-T点, 则存在，使得. 引理 若为问题（p）之非K-T点, 则 满足 且有

9、 ，.由取法的有限性知, 存在使得，其中为之无穷子列，由于，由引理10知, 于是，所以存在，且由之连续性知，（）. 由的构造及引理5知有界且数列 有界，故可令 ， . 引理11 若为问题（p）之非K-T点, 则，进而, 进而 . 证明 当充分大时有 .令 得 .其中. 故若，则，因而为（p）之K-T点，矛盾. 因而，进而, 再由引理6之证明知 ，故. 引理12 若为问题（p）之非K-T点, 则 存在及，使得，. 证明 仿照文3引理6易证. 定理1 若假设条件（H）成立，算法产生无穷点列，若不存在使得，N, 设无限点列之任一有限聚点，则是问题（p）之K-T点. 证明 (1). 若，在不等式中两边

10、令得，与引理11矛盾；(2). 若，不妨设，由 及的取法知，当充分大时， ，其中. 令得，由知，与引理11矛盾. 故必为（p）之K-T点. 定理2 若假设条件（H）成立，则算法或者在某一步终止于问题（P）的K-T点，或者产生无限点列，其任一有限聚点均为问题（p）之K-T点. 证明 由引理2，引理8和定理1可证.3数值例子 本节选择了文3中的几个算例，对本文算法在P-III933机器上利用matlab编制程序进行数值实验, 计算结果表明算法是有效的, 特别是在规模较大时，新算法具有更好的表现. 在PTMG()，PTFR，PTPR，PTHS算法中，取, , , , , . 用IT表示算法的迭代次数

11、，t 表示所用时间，表示最优解， 表示最优值.例1 ,s.t. .初始点; 最优解为, 最优值为. 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. 初始点; 最优解为，最优值为. 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. . 初始点; 最优解为, 最优值为. 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 作者感谢审稿人和编辑对本文提出的宝贵意见.参考文献：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. 陈广军，一个解带线性或非线性约束最优化问题的梯度投影算法J，计算数学，1987, 49: 356-364.4. 赖炎连等，非线性最优化的广义梯度投影方法J，中国科学A辑，1992, 9: 916-924.5. 孙麟平，无约束极小化的自是适应多信息下降算法J, 高校计算数学学报，1982, 14(2): 107-114.6. 赵庆贞，一个改进的超记忆梯度法的收敛性及敛速估计J, 应用

16、数学学报，1983, 6(3): 376-385.7. 时贞军，无约束优化的超记忆梯度算法J，工程数学学报，2000, 17(2): 99-104.8. 时贞军, 改进HS 共轭梯度算法及其全局收敛性J，计算数学，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