（计算数学专业论文）解简单界约束优化问题的投影修正两点步长梯度法.pdf

摘要 摘要 受戴或虹等人提出的解大规模盒式约束二次规划问题的投影 两点步长梯度法( p b b ) 的启发，本文把投影梯度法的思想和一些 在解无约束优化问题的梯度型方法中有效的非单调步长技术结合 在一起，提出了一种求解简单界约束优化问题的投影修正两点步 长梯度法。文章给出了算法，并在算法中讨论了几种潜在下降方 向镪七的作用和影响，并做了收敛性分析，数值结果表明本文所 提出的算法是有效的。 关键词i投影梯度法；修正两点步长；盒式约束；潜在下降方 向；收敛性 a b s t r a c t i n s p i r e db y t h ep b bm e t h o dp r o p o s e db y y h d a if o rs o l v i n gb o x c o n s t r a i n e dq u a d r a t i cp r o g r a m m i n g ，i n t h i sd i s s e r t a t i o n ，w ec o m b i n e t h e i d e ao fp r o je c t e dg r a d i e n tm e t h o dw i t hn o n m o n o t o n el i n es e a r c ht e c n 。 n i q u ea n ds o m ee f f i c i e n c ys t e ps i z e si nu n c o n s t r a i n e do p t i m i z a t l o n t o r s o l v i l l gs i m p l eb o u n dc o n s t r a i n e do p t i m i z a t i o n t h ea l g o r i t h mo f t h e m e t h o di sp r e s e n t e d ，m e a n w h i l es o m ep o t e n t i a ld e s c e n t d i r e c t i o n 乱后l s p r e s e n t e d t h ec o n v e r g e n c ea n a l y s i si sg i v e n ，a n dt h en u m e r i c a l r e s u l t s h o wt h ee f f i c i e n c yo ft h i sm e t h o d k e y w o r d s ：p r o j e c t e dg r a d i e n tm e t h o d ，m o d i f i e dt w o p o i n ts t e p s i z e ， b o xc o n s t r a i n ，p o t e n t i a ld e s c e n td i r e c t i o n ，c o n v e r g e n c ea n a l y s i s 一l v 前言 前言 在研究无约束最优化算法的时候已经知道，负梯度方向是一个局部的 最速下降方向，然而当约束存在时，沿着最速下降方向可能导致非可行 解。1 9 6 0 年，r o s e n 提出了梯度投影方法，把负梯度在某个子空间内投影， 使得沿着这样一个投影方向目标函数值可以得到改善，同时也保持可行性， 所以梯度投影方法本质上也是属于可行方向法的一大类。 梯度投影法的基本思想仍然是从可行点出发，沿着可行方向进行搜索， 当迭代出发点在可行域内部时，沿着负梯度方向搜索，当迭代出发点在某些 约束的边界条件上时，将该点的负梯度投影到m 的零空间， ( 其中m 是积极 约束或者部分积极约束为行构造成的矩阵) ，再沿此投影方向进行搜索，可 以证明，这样的投影是下降可行方向，因此，r o s e n 梯度投影法也是可行方 向法。 梯度投影法较多的应用于线性等式约束的情况，也有推广应用到非线性 等式约束和线性不等式约束的情况。 一般情况下，积极集法一般是解决中小规模问题最有效的办法，经典的 积极集法可以处理正半定问题，但是积极集和工作集改变的速度确实很慢 的，在一次迭代中只能改变一个指标。这样的话，对于大规模问题，用这样 的方法就需要很多次迭代才能达到收敛。比如，如果在初始迭代点x o 处没有 积极约束，但是在解点处有1 0 0 0 0 个积极约束，所以想用积极集法获得极小 点，就必须要迭代1 0 0 0 0 次，所以如何恰当的选择初始迭代点，存在很大的 技巧。 和经典的积极集法相比较，梯度投影法的好处就是可以快速改变约束的 积极集，特别是在约束比较简单时是最有效的，比如只有一些简单的界约束 或者简单的球式约束等等，它的好处也在于编程时是比较简单的，而且由于 约束简单，不需要像经典的投影梯度法那样要计算投影矩阵，要进行矩阵分 解等繁杂的工作，所以比较适合解决较大规模的问题，然而，早期的梯度投 影法是以一种试探的方式来选择步长的，所以就带来了类似于经典的最速下 降法那样的坏的性质，比如收敛速度慢，还有锯齿现象，在那以后的几十 年，大量的学者对这种方法进行了修正和改进。 一般来讲，梯度投影迭代由两部分构成：第一部分是从当前点z 出发， 前言 沿着最速下降方向一鲰搜索，当遇到边界时，为了保持可行性，就要使搜索 方向改变。第二部分是求解一个子问题。 最近，对于这方面的研究已经有了很多的好的结果。最有影响力的发展 是由戴或虹和f l e t c h e r 提出来的投影b a r z i l a i b o r w e i n 方法( p b b ) ，还有张 洪朝和h a n g e r 提出的投影自适应循环b a r z i l a i b o r w e i n 方法( a c b b ) ，在 此之后，周斌、高立等人提出了一种针对于盒式约束二次规划问题的单调投 影梯度法。 原始的b a r z i a l i b o r w e i n 方法是由的b a r z i l a i 和b o r w e i n 提出来的，后 来r a y d a n 做了进一步的研究，d a i 和l i a o 也做了很多这方面的工作，这种两 点步长梯度法的主要特点是拥有拟牛顿的性质，低存储，但是却是非单调 的。b b 法在处理二次问题时是明显超越最速下降法的，在处理一般的无约 束优化问题时，如果结合使用了非单调线搜索技术，它的性能会超越一般的 共轭梯度法。由于b b 法具有如此吸引人的性质，r a y d a n 首先提出把b b 法 和非单调线搜索技术相结合，得到一个解大规模无约束优化问题的全局收敛 的算法g b b ，因为投影梯度法是梯度法在约束优化问题上的推广，在此之 后，b i r g i n ，m a r t i n e z ，r a y d a n 等人提出把投影梯度法和b b 法，还有非单 调线搜索结合在一起，这样得到了两个著名的解决凸约束优化问题的投影算 法s p g l ，s p g 2 ，大量的数值试验显示这两个算法和软件包l a c e l d t 比 较起来还要更胜一筹。 d a i 和f l e t c h e r 4 提出了解决盒式约束二次规划问题的投影b b 算法，但 是数值试验显示，非单调线搜索技术会明显的减低未修正的投影b b 算法的 性能，但是从理论上来讲，为了保证全局收敛性，某种非单调线搜索的技术 是完全有必要的。 因为对于简单界约束优化问题，投影梯度法是有效的，并且b b 法在解 决无约束优化问题时又是很有效的，受到成功的p b b 法的影响，所以本文 针对简单约束优化问题提出了一种投影梯度类型的算法，因为算法当中的步 长在解决无约束优化问题时是超越在无约束优化当中的b b 法的，我们在本 文的开始给出投影b a r z i a l i b o r w e i n 算法的一个简单回顾，并且给出两个修 正两点梯度法的步长公式。在算法当中也会结合使用g l l 非单调线搜索技术 以确保算法的全局收敛性，以前的文献当中也显示，大量的数值试验表明， 由于沿负梯度方向计算步长不是一个明智的选择，它严重影响算法的收敛速 度，鉴于此，本文中提出了潜在下降方向的概念，还有比例投影梯度，然后 沿潜在下降方向计算步长。给出的数值试验表明，这种算法要优于未修正的 一2 一 嗣舌 投影b b 算法。 本文的框架如下：第一部分是引言介绍该方法的背景和一些已有的工 作；第二部分给出简单界约束优化问题的一种新的投影修正两点步长梯度算 法；第三部分给出本算法的收敛性讨论；第四部分给出数值结果并且把提出 的新算法和经典的算法s p g 2 做了数值比较；第五部分给出了结论评述和后 继有待进一步需要研究的工作。 第l 章投影修正两点步长梯度法 第1 章投影修正两点步长梯度法 1 1 引言 在这一部分将给出原始投影b b 算法的框架，并给出将在投影修正两点 步长梯度算法中会用到的两个有用的修正两点步长。 本文研究简单约束优化问题的投影梯度型算法，将分别研究两种简单的 约束，一种是简单盒式约束，另一种是简单的球式约束，如下 r a i n ，( z ) s t 1 z t 这里的目标函数，( z ) 不仅包含一些二次函数，更包括一般的非线性函 数，这里假设函数，扛) 是二次连续可微的，且f ，乱是r n 中的向量。我们把这 种约束优化问题叫做盒式约束优化问题，在文章中我们把这种约束记做q 。 工程问题中会出现很多凸约束优化问题，事实上可以把一般的凸约束优化问 题通过对偶的方式转化为盒式约束优化问题，所以盒式约束优化问题在工程 中有很大的实际价值值得去深入地研究。 另一种界约束优化问题是所谓的球式约束问题 m i n ，( z ) s t 1 1 2 1 1 2 r ( 1 1 2 ) 这里的r 代表约束可行域的半径，在信赖域方法中把它叫做信赖域半 径，z 代表目标函数中的变量。特别地，如果目标函数是二维的，约束条件 如下所示： 4 z i + z l 7 2 这种模型问题在周斌的大规模盒式约束二次规划问题的单调投影梯度法 的文章中也有提及，但是没有做出深入的研究。 记q = z z u ) 是目标函数的可行集，把投影到可行集q 上的z 的第i 个 分量定义如下： ( z ) 产m a x l i ，m i n x i ，让i ( 1 1 3 ) 这种定义方式和下面的方式是完全等价的： 酬m t = 雕麴， ， 这种简单投影适合于盒式约束问题，但是如果约束是球式约束，则投影被定 f 戤，若慨i i n 忍( z ，7 ) i - ( 1 1 5 ) 【衙，若蚓l n 这种投影算子用在求解球式约束二次规划问题，或者是信赖域子问题。 投影b b 算法1 4 1 ： 步1 取z l 舻和入1 0 若z l gq ，用p n ( x 1 ) 代替x 1 令k = 1 步2 若i i p n ( z k g k ) 1 1 2 = 0 ，则停止迭代 步3 计算z 七+ 1 = p a ( x k a k g k ) 步4 计算s 七：z 七+ l 一钆，y k = 鲰+ 1 一g k 和a 七+ 1 = f f s , l f f v , 步5 令k = k + 1 ，转步1 注意到，在算法的第二步投影之后没有利用到线搜索，但是在b i r g i n 等 人提出的s p g 2 算法当中需要去计算方向毗= p n ( x k a k g k ) 一x k ，且这 第l 章投影修正两点步长梯度法 里口詹1 使得如下非单调线搜索条件被满足： m 七+ 1 ) 一 ：。 0 ，一个较大的参 数q m 口口棚n 和一个充分下降参数，y ( 0 ，1 ) ，及两个安全参数0 0 1 c r 2 1 ，初始步长q o 【q m 讥，q 竹m 】 步1 若| | p ( z 七一g ( x k ) ) 一z 愚i i = 0 ，停止迭代，x k 是一个约束稳定点 步2 用后退型线搜索产生q 七 步2 1 计算d k = p ( x k a k g ( x k ) ) 一z 七，取风= 1 步2 2 取z + = 钆+ 凤d k 步2 3 若 他+ ) 冬m 点跏一1 孤。) + 低( 咖( z 知) ) ， ( 1 1 7 ) 令z 七+ l = z + ，魂= x k + 1 一z 七，y k = g ( x k + 1 ) 一夕( z 七) ，转步3 若( 1 1 7 ) 不成 立，则令p 矗伽【盯1 凤，眈凤】，令纨= 风删，转步2 2 步3 计算b 七= ( 乱，y k ) ，若6 七0 ，取o l k + 1 = a m 一否则，计算a k = ( 8 k ，8 k ) 和o l k + 1 = m i n a m ，m n z 口m 溉器) ) 文【7 中从对二次模型和对锥模型插值的角度得到了下面两个非常有效的 解决无约束优化问题的步长公式，本文中将会使用投影梯度法结合如下的两 个修正两点步长公式来求解简单界约束优化问题： 和 a 七= s 乏1 8 七一l 2 ( f k 一1 一f k + g t s k 一1 ) 】( 1 1 8 ) 一6 一 第1 章投影修正两点步长梯度法 k = s 己1 8 k 一1 6 ( 七一l 一厶) + 4 9 蚕s k 一1 - i - 2 9 乏1 & 一l 】， ( 1 1 9 ) 这里8 k 一1 = x k x k 一1 ，y k 一1 = 鲰一9 k 一1 然而，在原始p b b 算法当中，使用的 步长是如下的原始b b 步长： 入知= s 乏1 8 k 一1 s l l 鲰一1 ( 1 1 1 0 ) 很容易发现在目标函数，( z ) 是一个二次函数时，这三个公式在线 段z 七一l 和z 凫之间是相互等价的，这表明了如果目标函数，( z ) 是二维凸二次 函数，利用新步长的梯度法仍然是保持局匿线性收敛的。 利用原始步长的投影梯度法被称为谱方法，这种方法首先是 由m a r t i n e z 提出的，原因是原始b b 法的逆是如下平均海赛矩阵的r a y l e i g h q u o t i e n t ： ( v 2 ，( z 七+ t s k ) d t ) s k ( 1 1 1 1 ) - ，0 原始b b 步长的逆是在上述平均海赛矩阵的极小特征值i n 和极大特征 值口z 之间，所以才把这样的方法叫做谱投影梯度法。 对于一般的非线性函数，因为在推导公式( 1 1 8 ) 和( 1 1 9 ) 时，同时 利用了函数在点z 知一1 和点x k 这两点处的函数值信息和梯度信息，可以预料这 两个公式要优于公式( 1 1 1 0 ) ，袁亚湘指出，对于一维函数而言，前两个 公式要明显的优于后一个公式的，特别地，对于一维函数而言，前两个公式 的局部收敛速度要明显快于后一个公式，并且对于一类非线性函数而言，利 用前面两个公式的算法也是具有r 超线性收敛速度的。 第l 章投影修正两点步长梯度法 1 2 投影修正两点步长梯度算法 投影修正两点步长梯度算法的框架： 考虑到把求解无约束优化问题的高效算法推广到简单的界约束问题上也 会得到较好的效果，本文把用来求解无约束优化问题的高效的梯度型方法的 步长和投影梯度法相结合，提出对于求解一般的简单界约束优化问题的投影 修正两点步长梯度算法，该算法的提出是建立在p b b 算法和s p g 2 算法的基 础之上的。 算法2 1 ： 步1 取z 1 r n ，0 入m 讯 o ) 来计算步长丸 步5 取k = m a x a m 伽，m i n a m 簖，k 】并且计算d k = p n ( x k k 吼) 一 利用b b 法在方向如上计算步长q 七，使得如下非单调线搜索条件满足 他知+ 口知d 奄) - - - - - 。 j 蛳m a x ( m 他七一j ) + 盯q 七夕 ( 1 2 1 ) 这里每一次迭代的初始步长都设定为1 ，a p a k = 1 步6 令z 七+ l = 孤+ o 七也，k ：= k + l ，转步1 对于算法2 1 中的主要步骤第3 步，我们讨论了如下几种潜在下降方 向： i u k = - - g k ( 负梯度方向) 也就是说，第一种情况下，潜在下降方向是负梯度方向，就像在p b b 算 法当中，使用了这样的方向。但是在周斌的单调投影梯度法的论文当中指 出，用负梯度方向作为一个潜在的下降方向，数值效果会很差，为了找到问 题的原因，测试了很多盒式约束优化问题，输出如下的量的值： c o s 巩( 如) 2 丽u t d k ( 1 2 2 ) 一8 一 第1 章投影修正两点步长梯度法 在每一步的迭代当中，发现这个余弦值是一个相当小的量，这说明了，潜在 下降方向u 凫和精确下降方向毗是趋于垂真的，由该式就可以解释为什么把潜 在下降方向选择为最速下降方向会导致算法的性态变坏。 2 u 知= p n 仕膏一g k ) 一x , k ( 连续投影梯度方向) 注意到精确下降方向丸= 玮( x k a k g k ) 一x k 其实本质上是一种规模投影 梯度，对于规模投影梯度的定义将在文章后面给予定义。为了获得该方向的 一个好的估计，很自然的想到去也把u 七取为某种投影梯度，所以u 七可以取为 一些连续的投影梯度，如： 让知= 忍( x k 一鲰) 一 ( 1 2 3 ) 很明显，因为表达式的右端向量在停机准则中被计算过，所以这种方法产生 的“七不会再产生多余的投影计算量，所以这是选择这种潜在下降方向的一种 优势，本文中也把它和非单调步长相结合使用。 3 让k = r 女) ( 不连续投影梯度方向) 这里瓦( z 七) 的第i 个分量的形式如下： f 一( 9 知) ， 若( z 南) i ( 如，蛳) ， 瓦( z 七) 严 m a x 一) t ，o ) ，若( z 七) 产f t ， ( 1 2 4 ) 【m 讥 一) t ，o ) ，若( 矾) = u i 容易发现f n ( z k ) 在可行集q 的边界上是不连续的，所以把q ( 钆) 叫做不连续 投影梯度。周斌在单调投影梯度法的文章中发现，这种不连续的投影梯度是 最适合做投影自适应最速下降法p a s d 和投影d a i y u a n 方法p d y 的潜在下 降方向的，把结合不连续投影梯度的p a s d 和p d y 叫做p a s d 2 和p d y 2 4 札南= p n 0 一幻( ) ) 一z 知( 比例投影梯度方向) 从比例投影梯度的表达形式上非常容易可以看出来，连续投影梯度是这 种比例投影梯度的一般形式，但是具体的哪一种比例投影梯度方向是最佳 的，或者说怎样的比例投影梯度最适合某一种测试函数，这还是一个值得研 究的话题，在本文中我们选取参数芒= 0 9 算法评注： 1 在步4 当中的表达式入= m a x a m 溉仇讥 a m ，k ) ) 的作用是为了防止 步长太大或太小。 第l 章投影修正两点步长梯度法 2 在算法的第五步，非单调线搜索表达式( 1 2 1 ) 可以用如下的一些修正的 非单调线搜索公式来代替。 加权非单调线搜索技术公式1 2 2 1 ： m 一1 ) f ( x k + a k d k ) m a x f ( x k ，a k ，f ( x k 一，) ) 】+ 盯乜七靠如 ( 1 2 5 ) r = o 其中： a 打= 1 ， r = o 这里m 七= m i n k + 1 ，m 】。 平均值非单调线搜索技术公式1 2 2 1 这里： ，( z k + a k d k ) 丢妻m 丹慨概 ( 1 2 6 ) 0 0 ，使得对于 任意q 【丁，k 】，都有 9 a 【虿) 1 1 2 专 因为z 七一虿和。七7 ，则对于充分大的七，有 i l g o 川1 1 2 丢 由引理和( 1 3 o b ) 得到 f ( x k + 1 ) 洲训一掣 ( 1 3 4 ) ( 1 3 5 ) ( 1 3 6 ) 第l 章投影修正两点步长梯度法 取忌一o o ，n f ( x k ) _ 一。，这和函数，( z ) 在sl = 是下有界相矛盾。所 以，虿是一个约束稳定点。口 1 4 数值试验 整个算法的运行环境是m a t l a b 7 0 1 ，机器类型是t 胁n 尸口d s f 4 0 02 7 4 3 7 m c ，英特尔酷睿二双核处理器，主频是2 0 g h z 。 第一组数值试验是要说明潜在下降方向的重要性，说明了选择负梯度方 向作为潜在下降方向是不可行的。 第二组数值试验是将本文提出的算法与s p g 2 算法进行比较。 第三组数值试验是对于投影修正两点步长梯度算法在经典非单调线搜索 选择不同的m 值时对迭代次数的影响进行比较。 在所有的测试当中，所用到的停机准则是 i i r a ( x k 一鲰) 一z 蠡i f e 同时，如果问题的迭代次数超过5 0 0 0 次也强迫退出循环，退出迭代。 本文所使用的测试函数如下： 测试问题1 日s 3 8 u ，( z ) = 1 0 0 ( x ；一z 2 ) 2 + ( z l 一1 ) 2 + ( x 3 1 ) 2 + 9 0 ( z 一x 4 ) 2 + 1 0 1 【( z 2 1 ) 2 + ( z 4 1 ) 2 】+ 1 9 8 ( z 2 一1 ) ( z 4 一1 ) 约束： - 1 0 玩1 0 ，i = 1 ，2 ，3 ，4 初始迭代点： z o = ( 一3 ，一l ，一3 ，一1 ) t 测试问题2 j e 7 r d y d e u 约束： 一5 z i 5 初始点： 一1 3 2 + z一 一 z zz2 3 n ：l + l = z ，j 第1 章投影修正两点步长梯度法 跏= ( 1 ，一1 ，1 ，一1 ，1 ，- 1 ) t 测试问题3 p e n a l t u m h + p + 1 0 0 0 ( 卜一1 ) 2 + 1 0 0 0 ( 1 。萎 约束： 0 0 1 x i 1 0 0 0 0 初始点：z o = ( 1 0 ，1 0 ，1 0 ，1 0 ) t 测试问题4 c r a g g l e y y 纱 m ) = 舻一铒1 ) 4 + 1 0 0 ( x i + x x i + 2 ) 6 + i e j t a n 4 ( z 件2 一z 件3 ) + z ；+ ( x i + 3 1 ) 2 】 这里，j = 1 ，5 ，9 ，几一3 ) 且n 是4 的倍数。 约束： - 5 观5 初始点： 跏= ( 1 ，2 ，1 ，2 ，1 ，2 ) t 以上的四个测试函数来自【1 9 】下面的第五个测试函数来射2 0 1 测试问题5 1 0 1 0 m ) = ( 甄一2 ) ) 2 + ( 岬o - - x t ) ) 2 一( 戤) 2 | i = i i - - - - i 约束： 2 0 0 1 x i 9 9 9 9 ，i = 1 ，2 ，9 ，1 0 初始点：x o = ( 9 ，9 ，9 ，9 ) 第一组实验对于这五个函数，取变量个数全为4 ，非单调依然采用经典 的非单调线搜索，其中参数m 取为3 ，研究当潜在下降方向分别为最速下降 方向和连续投影梯度这两种情况下投影修正两点步长梯度算法在解决上述问 第1 章投影修正两点步长梯度法 题时潜在下降方向u 七和真实下降方向以之间夹角的余弦值的大小，即表达式 ( 1 2 2 ) 的值的大小。数值结果如下： 测试问题 使用一跏 使用连续投影梯度 测试问题1 0 1 0 2 80 9 9 8 3 测试问题2 0 0 6 9 30 9 9 8 8 测试问题30 0 4 2 50 9 9 9 l 测试问题4 0 0 1 7 0 0 9 9 8 8 测试问题5 0 1 0 6 60 9 9 7 2 比较表格中的左右两列的计算结果很明显可以看出，在使用连续投 影梯度的情况下( 1 2 2 ) 式的值要比在使用负梯度方向作为潜在下降方 向时要更加趋近于l ，如果c o s ( u 七，d k ) 的值越靠近1 ，说明预测的潜在下降方 向乱七和算法的真实下降方向毗靠得越近，这是想要得到的结果，同时也说明 了， i t 七和如的夹角越小，越有利于算法的快速收敛，取连续投影梯度作为潜 在下降方向正是达到了这样的目的。可以发现当取潜在下降方向为负梯度方 向时，潜在下降方向和算法的精确下降方向接近于垂直，这严重阻碍了算法 的收敛。所以在算法中选择连续投影梯度作为潜在下降方向是个好的选择。 第二组试验给出了对于前面四个测试函数在使用算法s p g 2 和投影修正 两点步长梯度算法来求解时所需要的迭代次数和c p u 时间上的比较，这里两 个算法中的非单调线搜索中m 都选取为5 ，在s p g 2 算法中的参数选取如下： ，y = 1 0 4 ，o f r a i n = 1 0 一硼，o l m a x = 1 0 a o ，o 120 1 ，0 220 9 ， 第l 章投影修正两点步长梯度法 塞2 ：堡墅堡正盟盛垄量搓廑笺造塑2 堡至复鎏丝出筮 测试问题( 维数) i t e r - at i m e ai t e r - bt i m e b 测试问题1 ( 4 ) 8 70 0 7 88 70 0 7 8 测试问题2 ( 1 0 ) 7 30 7 1 88 10 5 6 3 测试问题2 ( 1 0 0 ) 3 7 12 5 3 l7 2 04 9 2 2 测试问题2 ( 5 0 0 )7 0 95 5 6 32 2 2 3 1 7 5 8 1 测试问题3 ( 1 0 )2 30 0 3 l2 10 4 0 6 测试问题3 ( 1 0 0 ) 4 10 0 6 33 7o 。1 8 8 测试问题3 ( 5 0 0 ) 4 4 l0 9 3 84 8 8 02 1 6 5 6 测试问题4 ( 1 0 )1 8 93 3 1 31 8 9 3 1 5 6 测试问题4 ( 1 0 0 )3 0 34 5 5 03 9 74 9 6 9 测试问题4 ( 5 0 0 ) 7 6 36 0 9 8 44 5 46 0 7 3 4 这里“i t e r o 表示使用新算法时问题的迭代次数；“i t e r b 表示使 用s p g 2 算法时问题的迭代次数；“t i m e n 表示使用新算法时问题的迭代 时间；“t i m e 一6 表示使用s p g 2 算法时问题的迭代时间。 从表2 中可以看出，在处理测试问题l ，3 ，4 时，投影修正两点步长梯度 算法的性能( 算法的迭代次数和c p u 时间) 和s p g 2 是不相上下的，在处理 测试问题2 时，新算法要明显优于s p g 2 算法。 第三组试验是在投影修正两点步长梯度算法中，取经典的非单调线搜索 中的参数m 分别为2 ，3 ，6 时问题的迭代次数和计算时间的比较，从这组试 验中容易看出，对于这四个测试函数分别应该如何选择恰当的参数m 的值。 表3 投髭堡正堕壶垄基搓廑篡鎏垄进篡间壁! 盟造量丕旦鳆丝时的比较 测试问题1 的维数( m 的值)迭代次数计算时间 4 ( 2 )2 3 3o 1 2 5 4 ( 3 )1 2 90 1 0 9 4 ( 6 )1 9 3o 1 5 6 从这组试验中可以看出当m 选择为3 时，迭代次数和计算时间都是最少 的，所以用投影修正两点步长梯度算法解决问题1 时，非单调参数m 取3 是合 适的。 第l 章投影修正两点步长梯度法 表4 投影堡垂匦盛生量鲎廑篡鎏垄盐篁间壁2 堕造堡丕回鳆丝时的比较 测试问题2 的维数( m 的值)迭代次数计算时间 1 0 ( 2 ) 8 5 1 3 6 0 1 0 ( 3 )8 40 9 3 7 1 0 ( 6 )6 30 5 7 8 5 0 ( 2 )6 9 35 6 7 2 5 0 ( 3 )4 2 92 9 6 9 5 0 ( 6 )5 4 83 8 4 4 从表4 中不难看出，当测试问题2 的维数是1 0 时，选择m = 6 是最好的， 而当维数是5 0 的时候，选择m = 3 是最合适的。 表5 投影修正两点步长梯度算法在计算问题3 时选择不同的m 时的比较 测试问题3 的维数( m 的值)迭代次数计算时间 1 0 ( 2 )5 0 08 6 4 0 1 0 ( 3 )1 7 10 6 5 6 1 0 ( 6 )9 60 3 7 5 5 0 ( 2 )5 3 24 2 0 0 5 0 ( 3 )1 5 50 4 6 8 5 0 ( 6 )8 90 2 8 1 从这组数值测试中很容易看出，当问题3 的维数为1 0 的时候，选择参 数m = 3 是合适的，当问题3 的维数是5 0 的时候，选择参数m = 6 是合适的。 ： 表6 投髭堡正盟盛塑量搓廑篡选查迁复间壁垒堕造登丕回笪丝时的比较 测试问题4 的维数( m 的值)迭代次数计算时间 1 0 ( 2 )4 1 79 】6 4 1 0 ( 3 )1 5 02 2 3 4 1 0 ( 6 )3 4 15 2 0 3 5 0 ( 2 )1 8 7 21 0 6 7 1 8 5 0 ( 3 )9 7 98 6 5 9 4 5 0 ( 6 )1 7 7 21 0 6 7 1 8 从这组数据中很容易看出来，当问题4 的维数是1 0 的时候，选择参 数m = 3 是合适的，当问题4 的维数是5 0 的时候，选择参数m = 3 是合适 的。 第1 章投影修正两点步长梯度法 这样，总的来说，从上面的测试结果来看，对于新算法而言，非单调参 数取3 是合适的。 第1 章投影修正两点步长梯度法 1 5 结束语 本文结合了非单调线搜索技术，无约束情况下高效的修正两点步长，和 投影b b 法，建立了求解简单约束优化问题情况下的投影修正两点步长梯度 法，本文的算法是建立在p b b 算法和s p g 2 的算法基础上的，为了加快算法 的收敛速度，引进了比例投影梯度的概念，它其实可以称为是一种猜测下 降方向，数值结果表明，这种选择加快了算法的收敛速度。我们进一步的 工作是在选择比例投影梯度作为算法的潜在下降方向的时候，建立起选择 参数t 的合理的机制。这个问题类似于在非单调线搜索技术中恰当的选择参 数m 。另外，如何利用该方法来求解一般凸约束情况下的优化问题，如球式 约束优化问题，以及利用修正的非单调技术来代替新算法中经典的非单调技 术来求解凸约束问题都是值得进一步研究的课题。 参考文献 参考文献 【1 】1j b a r z i l a i ，j b o r w e i n ，t w o - p o i n ts t e ps i z eg r a d i e n tm e t h o d ，m aj o u r n a lo f n u m e r i c a la n a l y s i s , 8 ( 1 9 8 8 ) ，1 4 1 1 4 8 【2 e g b i ：r g m ，j m m a r t i n e z ，m r a y d a n ，n o n m o n o t o n es p e c t r a lp r o j e c t e dg r a d i - e n tm e t h o d so nc o n v e xs e t s ，s a mj o p t mv o l l o n 0 4 ，( 2 0 0 0 ) ，1 1 9 6 - 1 2 11 【3 3e g b i ：r g i n ，j m m a r t i n e z ，m r a y d a n ，s p e c t r a lp r o j e c t e dg r a d i e n tm e t h o d s ， t e c h n i q u er e p o r t , j a n u a r y17 ( 2 0 0 7 ) 【4 】y h d a i ，r f l e t c h e r , p r o j e c t e db a r z i l a i b o r w e i nm e t h o d s f o rl a 唱e 。s c a l eb o x 。 c o n s t r a i n e dq u a d r a t i cp r o g r a m m i n g ，n u m e r i s c h em a t h e m a t i k , 10 0 ( 2 0 0 5 ) ， 2 1 4 7 【5 】5y h d a i ，w h a g e r , k s c h i t t k o w s k i ，h c z h a n g ，t h ec y c l i cb a r z i a l i b o r w e i n m e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o n ，a c a d e m i cr e p o r t , m a y31 ，( 2 0 0 5 ) 1 - 2 7 6 】y h d a i ，l z l i a o ，r - l i n e a rc o n v e r g e n c eo fb a r z i l a ia n db o r w e i ng r a m e n t m e t h o d , m aj o u r n a lo f n u m e r i c a l a n a l y s i sl - 1 0 ，( 2 0 0 2 ) 【7 】y h d a i ，j y y u a n ，y x y u a n ，m o d i f i e dt w o - p o i n ts t e ps i z eg r a d i e n tm e t h o d s f o ru n s t r a i n e do p t i m i z a t i o n ，c o m p u t a t i o n a lo p t i m i z a t i o na n da p p l i c a t i o n s ， 2 2 ( 2 0 0 2 ) ，1 0 3 1 0 9 8 】y h d a i ，h c z h a n g ，a d a p t i v et w o - p o i n ts t e p s i z eg r a d i e n ta l g o r i t h m ，n u m e r - i c a la l g o r i t h m s , 2 7 ( 2 0 0 1 ) ，3 7 7 3 8 5 9 】9 r f l e t c h e r , o nt h eb a r z i a l i b o r w e i nm e t h o d ，a c a d e m i cr e p o r t , 2 3 5 - 2 5 5 【1 0 】l g r i p p o ，e l a m p a r i e l l o ，s l u c i d i ，an o n m o n o t o n el i n es e a r c ht e c h n i q u ef o r n e w t o n sm e t h o d ，s i a mj n u m e r a n a lv 0 1 2 3 ，n o 4 , a u g u s t ，( 1 9 8 6 ) ，7 0 7 - 7 1 5 11 】l o r i p p o ，m s c i a n d r o n e ，n o n m o n o t o n eg l o b a l i z a t i o nt e c h n i q u e sf o r t h e b a r z i a l i - b o r w e i ng r a d i e n tm e t h o d ，c o m p u t i o n a lo p t i m i z a t i o na n da p p l i c a - 一2 0 参考文献 t i o n s , 2 3 ( 2 0 0 2 ) ，1 4 3 1 6 9 12 】b m o l i n a ，m r a y d a n ，p r e c o n d i t i o n e db a r z i l a i - b o r w e i nm e t h o df o rt h en u m e r i c a ls o l u t i o no fp a r t i a ld i f f e r e n t i a le q u a t i o n s ，n u m e r i c a la l g o r i t h m s , 1 3 ( 19 9 6 ) ，4 5 6 0 【13 】y n a r u s h i m a ，t w a k a m a t s ua n dh y a b e ，e x t e n d e db a r z i l a i - b o r w e i nm e t h o d f o ru n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m s ，a c a d e m i cr e p o r t , a u g u s t1 7 ( 2 0 0 7 ) ( r e v i s e dm a y2 0 ，2 0 0 8 ) ，l - 2 9 【1 4 】j n o c e d a l ，s j w r i g h t ，n u m e r i c a lo p t i m i z a t i o n ，科学出版社，2 0 0 6 年 【l5 】m r a y d a n ，c o n v e r g e n c ep r o p e r t i e so ft h eb a r z i l a ia n db o r w e i nm e t h o d ， ( 1 9 9 1 ) ，t r 9 1 - 1 7 【l6 】m r a y d a n ，o nt h eb a r z i a l ia n db o r w e i n c h o i c eo fs t e p l e n g t hf o rt h eg r a d i e n t m e t h o d , a c a d e m i cr e p o r t , o c t o b e r ( 1 9 9 1 ) 【l7 】m r a y d a n ，b f s v a i t e r , r e l a x e ds t e e p e s td e s c e n ta n dc a u c h y b a r z i l a i - b o r w e i nm e t h o d , c o m p u t a t i o n a lo p t i m i z a t i o na n da p p l i c a t i o n s , k l u w e r a c a d e m i cp u b l i s h e r s m a n u f a c t u r e di nt h en e t h e r l a n d s ，( 2 0 0 2 ) 【l8 】m r a y d a n ，t h eb a r z i l a ia n db o r w e i ng r a d i e n tm e t h o df o rt h el a r g es c a l e u n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m ，s a mj o p t mv o l7 , n o 1 ，f e b r u a r