Pure Mathematics 理论数学, 2011, 1, 46-50 http://dx.doi.org/10.12677/pm.2011.11010 Published Online April 2011 (http://www.hanspub.org/journal/pm/) Copyright © 2011 Hanspub PM A New Projected Gradient Method for Bound Constrained Optimization Shanzhou Niu, Yi Wang, Dandan Cui School of Mathematics and Computer Science, Gannan Normal University, Ganzhou Email: maszniu@163.com Received: Mar. 14th, 2011; revised: Mar. 28th, 2011; accepted: Apr. 1st, 2011. Abstract: The projected gradient method is very suitable to solve large-scale nonlinear programming due to the simplicity of its iteration and implement. In this paper, based on the quasi-Cauchy equation and diagonal updating, a new projected gradient method is proposed for bound constrained optimization. On the basis of nonmonotone line search, global convergence is established. The numerical results show that the new algo- rithm is promising. Keywords: Bound Constrained Optimization; Projected Gradient Method; Nonmonotone Line Search; Global Convergence 边界约束优化问题一个新的投影梯度方法 牛善洲,王 义,崔丹丹 赣南师范学院数学与计算机科学学院,赣州 Email: maszniu@163.com 收稿日期:2011年3月14日;修回日期:2011年3月28日;录用日期:2011 年4月1日 摘 要:投影梯度法因其算法简单、易于实现,非常适合求解大规模优化问题。本文基于拟柯西方程和 对角变换,构造了一个新的投影梯度算法。在非单调线搜索条件下,证明该方法具有全局收敛性。最后 数值实验表明新方法是有效的。 关键词:边界约束优化;投影梯度方法;非单调线搜索;全局收敛性 1. 引言 设:n f RR是一个连续可微的函数。考虑如下 的边界约束优化问题: min( ) .. | n fx s txxR lx u T (1) 其中, , , 。将 f在点 x处的梯度记 为 12 ,, , n lll l ,1,2,,i n 12 ,,, n 12 ,,, T n uuu u T ii lu g xgxgx gx。 定义 1.1 设点x,如果 x 满足 0, 0, 0. ii i iii i ii i xl g lxu g xu g (2) 则称点 x 为问题(1)的一个稳定点。 问题(1)是一类十分重要的约束优化问题,许多实 际的优化问题都可以转化为问题(1)的形式。此外,问 题(1)常常是求解一般约束优化问题的增广Lagrange 和罚函数方法的一个子问题。因此,近年来许多学者 对问题(1)做了大量的研究,提出了许多求解该问题的 数值算法[1-4]。 投影梯度方法具有易于实现,以及适合求解大规 模优化问题的优点。另一方面,为了保证迭代点的有 效性,计算迭代点的投影一般都是十分费时的。此外, 即使投影的计算十分简便,投影梯度算法也会跟无约 束优化问题的梯度方法一样具有很慢的收敛速度。为 了提高投影梯度方法的收敛速度,文献[5]提出了求解 问题(1)的一个谱投影梯度方法,此方法是无约束优化 问题的谱梯度方法的推广。谱梯度方法最初是在文献 牛善洲等 边界约束优化问题一个新的投影梯度方法47 | [6]中提出的,此方法提高了梯度方法的收敛速度并且 大大减少了计算量。因此,谱梯度方法被广泛应用于 求解无约束和约束优化问题[7-9]。 文献[10]基于拟柯西方程与对角变换提出了求解 无约束优化问题的一个单调的梯度方法,此方法的主 要思想是:如果对角变换得到的新的对角矩阵非正定 时,将前一步的正定对角矩阵作为新的正定对角矩阵。 文献[11]提出了无约束优化问题的一个多元谱梯度方 法,并且具有二次终止性。此外,该方法引入非单调 线搜索后具有全局收敛性。基于多元谱梯度方法,文 献[4]提出了边界约束优化问题的一个多元谱投影梯 度方法。基于拟柯西方程与对角变换,本文提出了一 个新的投影梯度方法,并且采用文献[12]中的非单调 线搜索技术和一些限制保证算法的全局收敛性。 2. 新的投影梯度方法 首先,考虑无约束优化问题的谱梯度方法。设 gk 为函数 f在点xk处的梯度,谱梯度方法的迭代格式为 1 1 kk k k x x g . (3) 其中, k 由下述方式决定: 1 1 1 1 k k T k kT k s y s s . (4) 其中, 111 , kkkk kk1 s xxy gg 。步长 k 的 选取可以减少计算量并且在很大程度上提高了梯度方 法的收敛速度。此外,k 还被赋予了拟牛顿性质。事 实上,由(4)式给出的 k 可以由下式得到: 11 2 min kk Is y , 其中, k 近似代替函数f在点 xk处的Hessian 矩 阵。 我们在对角变换的基础上构造了一个新的梯度方 法,其迭代格式如下: 1 1 kkkk x xHg . (5) 其中,矩阵Hk为对角矩阵。我们的目标是通过对 角变换构造对角矩阵 Hk,使得矩阵Hk是Hessian 矩阵 的一个很好的近似。Hk满足拟牛顿方程: 11kk k H sy . 进一步,我们可以得到拟柯西方程: 111 TT kkkkk 设 是正定对角矩阵,Hk是由对角变换得 到的新矩阵并且使得 Hk也是正定对角矩阵。为了使得 Hk能够更好地近似 Hessian 矩阵,Hk必须满足拟柯西 方程,并且在变分原理下使得Hk和Hk − 1 的差量最小。 在计算机中对角矩阵与向量占有相同的存储空间,因 此我们可以得到一个存储空间为 的算法。文献 [10]给出如下定理: 10 k H On 定理 2.1[10] 设11kkk H H ,11kkk s xx , 11kkk ygg 。设 10 k s ,Hk − 1是正定对角矩阵。 考虑如下优化问题: 1 111111 11 min .. kF TTT kkkkkk kk s tsssys Hs . (6) 其中, F 表示 F范数。则(6)式的最优解为: 2 111 11 12,1,2,, i TT i kk kkk k k sysHss in tr E 其中,tr 表示迹算子, i k 是对角矩阵的第 i个对 角元素,是 Sk的第 i个坐标元素, k i k S 22 12 11 1 diag,, , n kk k Ess s 2 。 由定理 2.1,我们得到Hk的迭代公式为: 2 111 111 12 () ,1,2,, () TT i kkk kkk ii kk sysHs s H Hi tr E n . (7) 其中, i k H ,1 i k H 分别为Hk,1k H 的第 i个对角元素。 若存在某个i使得 0 i k H ,则无法保证(5)式中的搜索 方向为下降方向。为了克服上述缺点,我们使用下述 的迭代格式: 112 11 1 diag,, , kk n kk k k x xg . (8) 其中, i k 由下式得到: 1 1 11111 1 111 11 1 ,0,1,2 ,0, k k iT T kkkkkk iT kkTT kkkkk T k Hsys Hsin sy ,, 1,2,, s ysHs i ss n . (9) 由(8) 和(9)式,我们可以建立问题(1)的新的投影 梯度算法。给定 n zR ,定义集合 上的投影 pz: ,, , ,. iii iiii iii lifz l pzziflzu uifz u , (10) 1 s Hss y . Copyright © 2011 Hanspub PM 牛善洲等 边界约束优化问题一个新的投影梯度方法 48 | 为了保证算法的全局收敛性,我们使用文献[12] 中的非单调线搜索技术和一些限制。下面我们给出新 的投影梯度方法。 新的投影梯度(NPG)算法 给定数据: 0 n x R,0R ,初始矩阵 0 H I , , 0,1 0 ,12 01 ,0 ,10 以及 整数 。Set 。 1 0k Step1:If 1kkk px gx , stop. Step2:If then 0k Set 100 ( 0 ) x px g ,跳转至 Step6。 If ,Set 111 11 0 TT kkk kk sy sHs ii kk H , . 1, 2,,in Otherwise 1 1 1 1 ,1,2,, k k T k i kT k sy in ss . If 1 or ii kk ,Set . i k Step3:Set 12 11 1 diag,, , kn kk k 。 Step4:计算 ;Set kkkk dpxg x k1 。 Step5:(非单调线搜索) If 0min,1 max T kkkj k jkM k f xdfx gd k then 令 1 , kkkk x xd ,跳转至 Step6。 Else 取 12 , new ,Set new ,跳转至 Step5。 Step6:Set ;跳转至 Step1。 1kk 3. 全局收敛性分析 为了讨论 NPG 算法的全局收敛性,设目标函数 f x满足如下的基本假设: 假设 3.1 水平集 0 | x fx fx 是紧集。 引理 3.1 设 ,。则 存在常数 ,使得 k x kkkk dpxg x k 10c2 1 T kk k g dcd 。 证明 由的定义可知 k d i ii k kk i k g dpx x i k 。下 面分三种情况讨论: Case 1: , i ii k ki k g i x lu ,有 ii ii i kk kk k ii kk g g dpx x ,则 2 () iii i kkk k g dd 。 Case 2: i ii k ki k g x l ,有 0 i ii iii k kkk k i k g dpxxlx , iiii kk k g lx 则 2 () iii iiiii kkkkkkk g dlxdd 。 Case 3: i g ii k ki k x u ,有 0 i ii iii k kkkk i k g dpx xux , iii kk k i g ux 则 2 () iii iiiii kkkkkk k g duxdd 。 由于 i k ,取1 c ,则 2 1 T kk k g dcd ,引理 得证。 引理 3.2 设 k x 是由 NPG 算法产生的点列。则 0 k dk x 是问题(1)的稳定点。 证明 定义 | ki k Lixl ii , | kii k F il x u, i u| ki k Uix。 设0 k d ,如果ik L ,0 i ii k kk i k g dpx x i k 则 i ii k kk i k gi p xx l , 由(10)式得到 i ii k ki k g x l 。 考虑到 ,则得到。 0 i k 0 i k g 类似地,如果 ,可以得到 ;如果 ,可以得 到 k iU 0 i k 0 i k g k iFg 。因此, k x 是问题(1)的稳定 点。 另一方面,设 k x 是问题(1)的稳定点,如果 k iL , 0 i k g,则 i i k ki k gi x l 。因此,当 i,得 到 k L0 i k d 。 类似地,当可以得到;可以得到 k iF0 i k dk iU 0 i k d 。因此, 0 k d 。引理得证。 由引理 3.1,引理 3.2 以及文献[5]中的定理2.2, 我们可以得到下面的收敛性定理。 定理 3.2 设 k x 是由 NPG 算法产生的点列,则 k x 的任一极限点都是问题(1)的稳定点。 4. 数值实验 在本节,我们对NPG算法用MATLAB 编程,并在 PC( Intel Core 2 Duo CPU 2.2GHz Memory 2GB )上进 数值实验。设置参数 ,, 行5M4 10 10.1 , Copyright © 2011 Hanspub PM 牛善洲等 | 边界约束优化问题一个新的投影梯度方法 Copyright © 2011 Hanspub PM 49 0 1 12 1.()();,,,,100,100,,100,100,100,,100 i T nTT x i i n fxe xxlu nn n Table 4.1. 表4.1. n NI/NF/NG CPU(s) kk k px gx k f x 100 7/7/7 0.156 2.066143E–010 100 500 7/7/7 0.063 1.828211E–009 500 1000 7/7/7 0.125 3.526545E–009 1000 10000 7/7/7 11.297 1.838901E–008 10000 0 1 2.()();1,1,,1,1000, 1000,, 1000,1000,1000,,1000 10 i nTT x i i i fxe xxlu T Table 4.2. 表4.2. n NI/NF/NG CPU(s) kk k px gx k f x 100 359/525/359 0.25 9.409498E–007 505 1000 268/339/268 4.25 9.717239E–007 50 050 0 1 3.();1,1, ,1,10,10,,10,10,10,,10 2 TT T nn n fxxAx Axlu n T Table 4.3. 表4.3. n NI/NF/NG CPU(s) kk k px gx k f x 100 2/2/2 0.015 2.359224E–013 2.782969E–028 500 2/2/2 0.031 8.192363E–011 6.711481E–024 1000 2/2/2 0.094 1.025163E–009 5.254800E–022 5000 2/2/2 2.171 3.240671E–007 1.050195E–017 0 1 1 4.();1,1,,1,10, 10,, 10,10,10,,10 2 TT T nn fxxAx Axlu n T Table 4.4. 表4.4. n NI/NF/NG CPU(s) kk k px gx k f x 100 69/73/69 0.11 7.468630E–007 1.100490E–013 200 120/151/120 0.157 9.889196E–007 1.871602E–013 300 90/100/90 0.312 7.179043E–007 8.276060E–014 500 361/516/361 3.641 9.324383E–007 1.409143E–013 牛善洲等 边界约束优化问题一个新的投影梯度方法 50 | 20.9 10 , ,10 0 00 0 1 px gx , 15 5 1if if101 10 if10 kk k kk kkk k kk k px gx px gxpx gx px gx 5 1 。 我们对下述四个测试函数进行数值实验,迭代终 止条件为: 6 10 kk k px gx ,即 。 6 110 数值结果如表4.1、表 4.2、表 4.3、表4.4 所示。 其中,n, NI, NF, NG, CPU 分别表示测试函数的维数, 算法的迭代次数,函数值的计算次数,梯度值的计算 次数,所用的cpu 时间。 5. 致谢 本文第一作者感谢赣南师范学院研究生创新基金 的资助。作者对审稿人和编辑所提出的宝贵意见表示 衷心的感谢! 参考文献 (References) [1] R. H. Byrd, P. Lu, J. Nocedal. A limited-memory algorithm for bound constrained optimization. SIAM J. Sci. Stat. Comput, 1995, 16(5): 1190-1208. [2] W. W. Hager, H. Zhang. A new active set algorithm for box constrained optimization. SIAM J. Optim, 2006, 17(2): 526- 557. [3] J. Moré, G. Toraldo. On the solution of large scale quadratic programming problem with bound constrains. SIAM J. Optim, 1991, 1(1): 93-113. [4] Z. S. Yu, Sun J, Qin Y. A multivariate spectral projected gradient method for bound constrained optimization. J. Comput. Appl. Math, 2011, 235(8): 2263-2269. [5] E. G. Birgin, G. M. Martinez, M. Raydan. Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim, 2000, 10(4): 1196-1211. [6] J. Barzilai, J. M. Borwein. Two-point step size gradient methods. IMA J. Numer. Anal, 1988, 8(1): 141-148. [7] R. Andreani, E. G. Birgin, J. M. Martínez, et al. Spectral pro- jected gradient and variable metric methods for optimization with linear inequalities. IMA J. Numer. Anal, 2005, 25(2): 221-252. [8] E. G. Birgin, G. M. Marttínez. Larges-scale active-set box- constrained optimization method with spectral projected gra- dients. Comput. Optim Appl, 2002, 23(1): 101-125. [9] Y. Dai, R. Fletcher. Projected Barzilai-Borwein method for large-scale box-constrained quadratic programming. Numer. Math, 2005, 100(1): 21-47. [10] W. J. Leong, M. A. Hassan, M. Farid. A monotone gradient method via weak secant equation for unconstrained optimi- zation. Taiwanese J. Math, 2010, 14(2): 413- 423. [11] L. Han, G. Yu, L. Guan. Multivariate spectral gradient method for unconstrained optimization. Appl Math Comput, 2008, 201(1-2): 621-630. [12] L. Grippo, F. Lampariello, S. Licidis. A nonmonotone line search technique for Newtons method. SIAM Journal on Numerical Analysis, 1986, 23(4): 26-33. Copyright © 2011 Hanspub PM |