边界约束优化问题一个新的投影梯度方法

Size: px

Start display at page:

Download "边界约束优化问题一个新的投影梯度方法"

报于
6 years ago
Views:

1 Pure Mathematcs 理论数学 Publshed Ole Aprl ( A New Projected Gradet Method for Boud Costraed Optmzato Shazhou Nu Y Wag Dada Cu School of Mathematcs ad Computer Scece Gaa Normal Uversty Gazhou Emal: maszu@63.com Receved: Mar. 4th ; revsed: Mar. 8th ; accepted: Apr. st. Abstract: he projected gradet method s very sutable to solve large-scale olear programmg due to the smplcty of ts terato ad mplemet. I ths paper based o the quas-cauchy equato ad dagoal updatg a ew projected gradet method s proposed for boud costraed optmzato. O the bass of omootoe le search global covergece s establshed. he umercal resulthow that the ew algorthm s promsg. Keywords: Boud Costraed Optmzato; Projected Gradet Method; Nomootoe Le Search; Global Covergece 牛善洲王义崔丹丹赣南师范学院数学与计算机科学学院赣州 Emal: maszu@63.com 收稿日期 : 年 3 月 4 日 ; 修回日期 : 年 3 月 8 日 ; 录用日期 : 年 4 月日摘要 : 投影梯度法因其算法简单易于实现非常适合求解大规模优化问题本文基于拟柯西方程和对角变换构造了一个新的投影梯度算法在非单调线搜索条件下证明该方法具有全局收敛性最后数值实验表明新方法是有效的关键词 : 边界约束优化 ; 投影梯度方法 ; 非单调线搜索 ; 全局收敛性. 引言设 f : R R 是一个连续可微的函数考虑如下的边界约束优化问题 : m f( ) () s.. t R l u l 为 g 其中 l l l l u u u u u 将 f 在点处的梯度记 g g g 定义. 设点如果满足 l g l u g () u g. 则称点为问题 () 的一个稳定点问题 () 是一类十分重要的约束优化问题许多实际的优化问题都可以转化为问题 () 的形式此外问题 () 常常是求解一般约束优化问题的增广 Lagrage 和罚函数方法的一个子问题因此近年来许多学者对问题 () 做了大量的研究提出了许多求解该问题的数值算法 [-4] 投影梯度方法具有易于实现以及适合求解大规模优化问题的优点另一方面为了保证迭代点的有效性计算迭代点的投影一般都是十分费时的此外即使投影的计算十分简便投影梯度算法也会跟无约束优化问题的梯度方法一样具有很慢的收敛速度为了提高投影梯度方法的收敛速度文献 [5] 提出了求解问题 () 的一个谱投影梯度方法此方法是无约束优化问题的谱梯度方法的推广谱梯度方法最初是在文献 Copyrght Haspub

2 牛善洲等 47 [6] 中提出的此方法提高了梯度方法的收敛速度并且大大减少了计算量因此谱梯度方法被广泛应用于求解无约束和约束优化问题 [7-9] 文献 [] 基于拟柯西方程与对角变换提出了求解无约束优化问题的一个单调的梯度方法此方法的主要思想是 : 如果对角变换得到的新的对角矩阵非正定时将前一步的正定对角矩阵作为新的正定对角矩阵文献 [] 提出了无约束优化问题的一个多元谱梯度方法并且具有二次终止性此外该方法引入非单调线搜索后具有全局收敛性基于多元谱梯度方法文献 [4] 提出了边界约束优化问题的一个多元谱投影梯度方法基于拟柯西方程与对角变换本文提出了一个新的投影梯度方法并且采用文献 [] 中的非单调线搜索技术和一些限制保证算法的全局收敛性. 新的投影梯度方法首先考虑无约束优化问题的谱梯度方法设 g 为函数 f 在点处的梯度谱梯度方法的迭代格式为 g. (3) 其中由下述方式决定 : s y. (4) 其中 s y g g 步长的选取可以减少计算量并且在很大程度上提高了梯度方法的收敛速度此外还被赋予了拟牛顿性质事实上由 (4) 式给出的可以由下式得到 : Is y m 其中近似代替函数 f 在点处的 Hessa 矩阵我们在对角变换的基础上构造了一个新的梯度方法其迭代格式如下 : H g. (5) 其中矩阵 H 为对角矩阵我们的目标是通过对角变换构造对角矩阵 H 使得矩阵 H 是 Hessa 矩阵的一个很好的近似 H 满足拟牛顿方程 : H s y. 进一步我们可以得到拟柯西方程 : s Hs s y. 设 H 是正定对角矩阵 H 是由对角变换得到的新矩阵并且使得 H 也是正定对角矩阵为了使得 H 能够更好地近似 Hessa 矩阵 H 必须满足拟柯西方程并且在变分原理下使得 H 和 H 的差量最小在计算机中对角矩阵与向量占有相同的存储空间因此我们可以得到一个存储空间为 O的算法文献 [] 给出如下定理 : 定理. [] 设 H H s y g g 设 s H 是正定对角矩阵考虑如下优化问题 : m F. (6) s.. ts s s y s H s 其中 F 表示 F 范数则 (6) 式的最优解为 : sy s Hss tr E 其中 tr 表示迹算子是对角矩阵角元素是 S 的第个坐标元素 S E dag s s s 由定理. 我们得到 H 的迭代公式为 : 的第个对 ( s ) y s H H H. tr( E ) (7) 其中 H H 分别为 H H 的第个对角元素若存在某个使得 H 则无法保证 (5) 式中的搜索方向为下降方向为了克服上述缺点我们使用下述的迭代格式 : dag g. (8) 其中由下式得到 : H s y s H s s y s y s H s. (9) 由 (8) 和 (9) 式我们可以建立问题 () 的新的投影梯度算法给定 z R 定义集合上的投影 p z : l f z l pz z fl z u () u fz u. Copyrght Haspub

3 48 牛善洲等为了保证算法的全局收敛性我们使用文献 [] 中的非单调线搜索技术和一些限制下面我们给出新的投影梯度方法新的投影梯度 (NPG) 算法给定数据 : R R 初始矩阵 H I 以及整数 Set Step:If p g stop. Step:If the Set p ( g) 跳转至 Step6 If s yshs Set H. s y Otherwse. If or Set. Step3:Set dag Step4: 计算 d p g ;Set Step5:( 非单调线搜索 ) If f d ma f g d jm j 令 M d 跳转至 Step6 Else 取 Step5 ew the Set ew 跳转至 Step6:Set ; 跳转至 Step 3. 全局收敛性分析为了讨论 NPG 算法的全局收敛性设目标函数假设 3. 水平集 f f f 满足如下的基本假设 : 是紧集引理 3. 设 d p g 则存在常数 c 使得 g d c d g 证明由 d 的定义可知 d p 下面分三种情况讨论 : g Case : l u 有 g g d p 则 g d g Case : l 有 ( d) g d p l gd l d ( d) g Case 3: u 有则 g d p u 则 g d u d ( d ) g l g u 由于取 c 则 gd c d 引理得证引理 3. 设是由 NPG 算法产生的点列则是问题 () 的稳定点 d 证明定义 L l F l u u U 设 d 由 () 式得到 g 如果 L d p p g g l l 考虑到则得到 g 则类似地如果 U 可以得到 g ; 如果 F 可以得到 g 因此是问题 () 的稳定点另一方面设是问题 () 的稳定点如果 L g g 则 l 因此当 L 得到 d 类似地当 F 可以得到 d ; U 可以得到 d 因此 d 引理得证由引理 3. 引理 3. 以及文献 [5] 中的定理. 我们可以得到下面的收敛性定理定理 3. 设是由 NPG 算法产生的点列则的任一极限点都是问题 () 的稳定点 4. 数值实验在本节我们对 NPG 算法用 MALAB 编程并在 PC( Itel Core Duo CPU.GHz Memory GB ) 上进 4 行数值实验设置参数 M 5. Copyrght Haspub

4 牛善洲等 49. f( ) ( e ); l u able 4.. 表 4.. NI/NF/NG CPU(s) p g f 7/7/ E 5 7/7/ E 9 5 7/7/ E 9 7/7/ E 8. f( ) ( e ); l u able 4.. 表 4.. NI/NF/NG CPU(s) p g f 359/55/ E /339/ E f( ) A; A l u able 4.3. 表 4.3. NI/NF/NG CPU(s) p g f // E E 8 5 // E 6.748E 4 // E E 5 // E 7.595E 7 4. f( ) A; A l u able 4.4. 表 4.4. NI/NF/NG CPU(s) p g f 69/73/ E 7.49E 3 /5/ E 7.876E 3 3 9// E E /56/ E E 3 Copyrght Haspub

5 5 牛善洲等.9 p g f p g 5 p g f p g 5 5 f p g 我们对下述四个测试函数进行数值实验迭代终止条件为 : 6 6 p g 即数值结果如表 4. 表 4. 表 4.3 表 4.4 所示其中 NI NF NG CPU 分别表示测试函数的维数算法的迭代次数函数值的计算次数梯度值的计算次数所用的 cpu 时间 5. 致谢本文第一作者感谢赣南师范学院研究生创新基金的资助作者对审稿人和编辑所提出的宝贵意见表示衷心的感谢! 参考文献 (Refereces) [] R. H. Byrd P. Lu J. Nocedal. A lmted-memory algorthm for boud costraed optmzato. SIAM J. Sc. Stat. Comput 995 6(5): 9-8. [] W. W. Hager H. Zhag. A ew actve set algorthm for bo costraed optmzato. SIAM J. Optm 6 7(): [3] J. Moré G. oraldo. O the soluto of large scale quadratc programmg problem wth boud costras. SIAM J. Optm 99 (): [4] Z. S. Yu Su J Q Y. A multvarate spectral projected gradet method for boud costraed optmzato. J. Comput. Appl. Math 35(8): [5] E. G. Brg G. M. Martez M. Rayda. Nomootoe spectral projected gradet methods o cove sets. SIAM J. Optm (4): 96-. [6] J. Barzla J. M. Borwe. wo-pot step sze gradet methods. IMA J. Numer. Aal 988 8(): [7] R. Adrea E. G. Brg J. M. Martíez et al. Spectral projected gradet ad varable metrc methods for optmzato wth lear equaltes. IMA J. Numer. Aal 5 5(): -5. [8] E. G. Brg G. M. Marttíez. Larges-scale actve-set bocostraed optmzato method wth spectral projected gradets. Comput. Optm Appl 3(): -5. [9] Y. Da R. Fletcher. Projected Barzla-Borwe method for large-scale bo-costraed quadratc programmg. Numer. Math 5 (): -47. [] W. J. Leog M. A. Hassa M. Fard. A mootoe gradet method va wea secat equato for ucostraed optmzato. awaese J. Math 4(): [] L. Ha G. Yu L. Gua. Multvarate spectral gradet method for ucostraed optmzato. Appl Math Comput 8 (-): [] L. Grppo F. Lamparello S. Lcds. A omootoe le search techque for Newtos method. SIAM Joural o Numercal Aalyss 986 3(4): Copyrght Haspub

标题

016 年 5 月重庆师范大学学报 ( 自然科学版 ) May016 第 33 卷第 3 期 JournalofChongqingNormalUniversity(NaturalScience) Vol.33 No.3 运筹学与控制论 DOI:10.1171/cqnuj016035 * Wolfe 线搜索下两种修正 DY 共轭梯度法的全局收敛性周雪琴, 卢琳璋 ( 贵州师范大学数学与计算机科学学院,