初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法.doc

初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法*
孙清滢 刘新海
石油大学应用数学系，山东，东营 257061

GENERALIZED SUPER-MEMORY GRADIENT PROJECTION METHOD WITH ARBITRARY INITIAL POINT AND CONJUGATE GRADIENT SCALAR FOR NONLINEAR PROGRAMMING WITH NONLINEAR IN-EQUALITY CONSTRAINTS

Sun Qingying，liu xinhai
Depart. of Applied Mathematics, University of petroleum, Dongying, 257061
Abstract
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 gradient 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 gradient 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
关键词: 非线性规划，广义投影, 非线性不等式约束，超记忆梯度，任意初始点, 收敛

1. 引言

梯度投影法是求解非线性约束最优化问题的基本方法之一，在最优化领域占有重要地位[1~6]. 如高自友在文[3]中建立了求解非线性不等式约束优化问题的计算量小，算法稳定的任意初始点下的广义梯度投影算法, 但算法收敛速度慢. 超记忆梯度算法是求解无约束规划的有效算法. 这类方法在迭代中较多地利用了已经得到的目标函数的某些信息，因而具有较快的收敛速度[7~8]. 若能将此法推广用于求解约束优化问题，可望改善现有算法的收敛速度. 高自友在文[9] 建立了求解非线性不等式约束优化问题的超记忆梯度算法. 时贞军[10,11]对无约束规划（p）提出了一种参数取值为区间的改进共轭梯度算法，并在水平集有界的条件下证明了算法的收敛性质. 受文献[9, 10, 11]的启发，本文利用广义投影矩阵，对求解无约束规划的超记忆梯度算法中的参数给出一种新的取值范围以保证得到目标函数的超记忆梯度广义投影下降方向，并与处理任意初始点的方法技巧结合建立求解非线性不等式约束优化问题的一个初始点任意的超记忆梯度广义投影算法，并在较弱条件下证明算法的收敛性. 同时给出具有好的收敛性质的结合FR，PR，HS共轭梯度参数的超记忆梯度广义投影算法, 从而将经典的共轭梯度法推广用于求解约束规划问题. 新算法保留梯度广义投影算法的优点，改进了广义梯度投影算法的收敛速度. 算法需要较小的存储，适合于大规模非线性不等式约束优化问题的计算. 数值例子表明算法是有效的.

* 国家自然科学基金（10171055）资助项目
2. 问题与算法

考虑问题（p）：，其中.
记，, , ;
为 维对角矩阵，其主对角元为：
本文始终假设： （H1）：
（H2）：为线性无关的向量组，其中 .
和任何方向 ，定义：，称
为 在 处关于方向 的方向导数.
引理1. 如果 则 和任意方向 ，我们有 .
由引理1知，，我们不妨记 ，显然有.
引理2. ，矩阵正定.
，令： ，
，
，
其中为阶单位矩阵，我们称为 处的广义投影矩阵。
引理3. ，矩阵 的任一特征值 满足 .
对问题 (P) 的非 K-T 点， 令： ， . 按以下条件选取参数, :
（1）
（2）
其中， 为常数.
条件（1）实质上给出了的一个取值范围， 即
（3）
（i） 当时，由（3）得
.
(ii)当时，由（3）得
.
由引理 3 知 . 因此可取 ：
(4)
其中 , (5)
. (6)
其中 是和的夹角.
引理 4. 若为问题(P)的非 K-T 点，满足（4），（5）和（6），则
.
证明. 当时, 结论显然成立. 以下分两种情况讨论:
1. .

. （7）
由 及（7）知结论成立。
2. .

. （8）
由及（8）知结论成立.
在条件下, 条件(2)实质上给出了的一个取值范围，即
. (9)
（i）当时，由（9）得
.
(ii) 当时，由（9）得
.
由引理4知可取：
, (10)
其中 , (11)
, (12)
其中 是和的夹角.
引理 5. 若为问题(P)的非 K-T点，满足（4），（5）和（6），满足（10），（11）和（12）, 则
.
证明. 当时，结论显然成立。以下分两种情况讨论：
1. .

. （13）
由 及（13）知结论成立。
2.

. （14）
由 及（14）知结论成立.
引理6 若为问题(P)的非K-T点，满足（4），（5）和（6），满足（10）,
（11）和（12）, 则 .

初始点任意的超记忆梯度广义投影算法(PSMGM):
设 为连续函数且满足 , 其中.
(1) 任取，，，, , 令 ;
(2) 计算和.若有 和 同时成立时, 为问题(p)的K-T点,停；否则,转（3）；
(3) 令, 其中， 满足 (4), (5) 和 (6), 满足 (10), (11) 和 (12)；；

（4）令，其中

（5） 令，其中是中满足下列（a）或（b）的
最大值：
(a) 若，则
(b) 若，则.
（6）令，转步（2）.
注： 算法步骤5（b）中的. 结合FR，PR，HS 共轭梯度法，给出的选取方法如下：
；
；
.
从而得到具有好的收敛性质的结合FR，PR，HS共轭梯度参数的初始点任意的超记忆梯度广义投影算法, 分别记为 PSFRM，PSPRM，PSHSM；取，，，算法退化为文献[3]中的算法. 通过数值例子发现，，, 的取法对算法收敛速度的影响很大，适当选取,, 可有效地改善算法的收敛结果.
引理7. 若和同时成立，则为问题（p）的K-T点.
引理8 （1）当，应有；
（2）若且为非K-T点，则必有，.
证明. （1）对，我们有

. （15）
又因为

.
由于时，，并注意到和的定义，应有.
（2）若，则，又若为问题（p）的非K-T点，则由引理7及（15）式可得，. 同（1）可证：.
引理9. （1）若且为问题（p）的非K-T点，则必为问题（p）在处的可行下降方向；
(2) 当，则必为的一个下降方向.
证明. 因为
（16）

（17）
（1） 因为，则, 因而 . 由引理
8及（17）知，.
（2） 当时，由（17）式知，, 有
.
再由引理1的结论易知
. （18）
注: 由引理9及步骤5（a）易知：若，则一定有，所以对算法产生的点列，若某步后，则以后由算法产生的点均为可行点.

3. 全局收敛性

定理1. 如果（H1），（H2）成立，且处由算法产生的可行点组成的无穷点列，则其任一极限点都是问题（p）的K-T点.
证明. 仿文献[4]之定理3易证.
下设是由算法产生的非可行点组成的无穷点列，设其有极限点，注意到，只有有限多种选择，故可找到子列，使其满足：
（i） （ii）与无关.
记作，，注意到此时是一连续函数，则，又，可知是有界序列，故可取出收敛的子列，，再由，及引理6知是有界序列，取其子列，是一无穷子集，这样对可定义:
，，
显然有 ，，.
再定义： . 显然应有
. （19）
这是因为，都有：. 令得
.
故由的定义知（a）式成立, 且.
引理10. 设是一个由算法产生的非可行点组成的无穷点列，其极限点为问题（p）的非K-T点，则一定有.
证明. 设，分两种性况讨论.
(i) 若，由18）式，令，并，注意到 则
. （20）
因且为问题（p）的非K-T点，故由引理8的证明易知，从而 由（20）式知此时.
(ii) 若，则由（20）式有
,
令: 得 .
定理2. 若是由算法产生的一个非可行点组成的无穷点列，则的任一极限点均是问题（p）的K-T点.
证明. 设，且假设不是问题（p）的K-T点，由于是单调下降序列，则有 .
(i) 当时，由步骤5（b）知 ,令得：, 此与引理10的结论矛盾.
(ii) 当时，由引理10知存在使得.
因为且，则当充分大时有
. （21）
由方向导数定义，有 ，从而由是连续函数且，则必存在和充分大的有
. (22)
故根据步骤5(b)中的选择规则并注意到(21), (22)式易知这种情况不出现.
这样, 由上述(i), (ii) 知必为问题(p)的K-T点.
定理3. 若(H1),(H2)成立, 则算法或者有限步终止于问题(p)的K-T点, 或者产生无穷点列, 其任一极限点都是问题 (p) 的K-T点.

4. 数值例子

本节选择了文献[5]中的几个算例，对本文算法进行数值实验，在P-III933机器上利用matlab 编制程序，计算结果表明算法是有效的. 用 IT 表示算法的迭代次数，FIT 表示算法到达可行域的迭代次数，t 表示所用时间，表示最优解， 表示最优值. 取, , , , ，,（PSCGM）. 例题给出在下三个不同初始点的计算结果.
例1 ,
s.t.

.
最优解为, 最优值为.

（PSMGM ）
FIT
IT

t
(8,8)
0

10
(0.5191,0.2405)
0.5010
0.0499s
(0,1)
1
12
(0.5239,0.2382)
0.5016
0.0499s
(-11,2)
5
14
(0.5196,0.2403)
0.5010
0.0000s

（PSFRM ）
FIT
IT

t
(8,8)
0
13
(0.4979,0.2514)
0.5007
0.2600s
(0,1)
3
23
(0.5021,0.2492)
0.5006
0.1600s
(-11,2)
6
29
(0.5143,0.2431)
0.5009
0.5999s

（PSPRM ）
FIT
IT

t
(8,8)
0
17
(0.5051,0.2475)
0.5004
0.1600s
(0,1)
1
22
(0.4902,0.2575)
0.5057
0.2600s
(-11,2)
1
17
(0.5026,0.2490)
0.5007
0.5500s

（PSHSM ）
FIT
IT

t
(8,8)
0
14
(0.50750.2464)
0.5004
0.1700s
(0,1)
3
24
(0.4979,0.2512)
0.5004
0.6000s
(-11,2)
5
22
(0.5060,0.2471)
0.5004
0.3899s

例2 ,
s.t.
.
最优解为, 最优值为.
（PSMGM ）
FIT
IT

t
(0,0)
0
4
(0.9924,0.9960)
1.0151
0.0000s
(-1,-1)
1
4
(0.9873,0.9927)
1.0255
0.0000s
(1,-1)
1
3
(0.9925,0.9971)
1.0148
0.0000s

（PSFRM ）
FIT
IT

t
(0,0)
0
6
(0.9921,1.0028)
1.0156
0.0599s
(-1,-1)
3
7
(0.9936,0.9970)
1.0127
0.0000s
(1,-1)
1
6
(0.9924,1.0021)
1.0151
0.0600s

（PSPRM ）
FIT
IT

t

(0,0)
0
6
(0.9912,1.0043)
1.0175
0.0000s
(-1,-1)
2
6
(0.9895,0.9969)
1.0209
0.0499s
(1,-1)
1
7
(0.9907,1.0024)
1.0186
0.4999s

（PSHSM ）
FIT
IT

t
(0,0)
0
6
(0.9921,1.0028)
1.0156
0.0000s
(-1,-1)
4
8
(0.9904,0.9997)
1.0191
0.0000s
(1,-1)
1
6
(09924,1.0021)
1.0151
0.0499s

例3. ;
s. t.
.
最优解为, 最优值为.
（PSMGM ）
FIT
IT

t
(0,0)
0
3
(0.8912,0)
1.0118
0.0000s
(2,0)
16
18
(0.9662,0.0030)
1.0011
0.0500s
(0,2)
4
12
(0.9318,-0.0034)
1.0046
0.0500s

（PSFRM ）

FIT
IT

t
(0,0)
0
6
(0.9138,0)
1.0074
0.0600s
(2,0)
20
20
(0.9840,0)
1.0002
0.0500s
(0,2)
23
28
(0.9453,-0.0037)
1.0029
0.2799s

（PSPRM ）
FIT
IT

t
(0,0)
0
6
(0.9118,0)
1.0077
0.1099s
(2,0)
19
19
(0.9224,0)
1.0060
0.0599s
(0,2)
20
27
(0.9841,0.0000)
1.0002
0.5000s

（PSHSM ）
FIT
IT

t
(0,0)
0
6
(0.9138,0)
1.0074
0.0599s
(1,2)
39
53
(0.9429,0.0063)
1.0032
0.5500s
(0,2)
26
33
(0.9914,0.0021)
1.0000
0.1700s

作者感谢审稿人和编辑对本文提出的宝贵意见。

参 考 文 献
[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 Programming, Part II, Nonlinear Constraints. J. SIAM, 9:4 (1960), 514-532.
[3] 高自友，于伟，任意初始点下的广义梯投影方法，科学通报，20（1992），1832-1836.
[4] 高自友，贺国平，约束优化问题的一个广义梯投影法，科学通报，36：19（1991）, 1444-1447.
[5] 陈广军，一个解带线性或非线性约束最优化问题的梯度投影算法，计算数学, 49 (1987），356-364.
[6] 高自友，贺国平，关于梯度投影类算法统一构造的探讨，科学通报，37:17(1992)，1621-1623.
[7] 孙麟平，无约束极小化的自是适应多信息下降算法。高校计算数学学报，14：2（1982），107-114.
[8] 赵庆贞，一个改进的超记忆梯度法的收敛性及敛速估计。应用数学学报，6:3 （1983）, 376-385.
[9] Gao Ziyou and He Guoping, A Super-memory Gradient Projection Algorithm for Optimization Problem with Non-linear Constraints, Acta Mathemetica Applicates Sinica, 8:4(1992), 323-332.
[10] 时贞军，无约束优化的超记忆梯度算法[J]，工程数学学报， 17:2 (2000), 99-104.
[11] 时贞军, 改进HS 共轭梯度算法及其全局收敛性[J]，计算数学，23:4 (2001), 393-406.

13