RMS算法的收敛性

D0I:10.13374/j.issn1001-053x.1984.04.011 北京钢铁半院学报 1984年第4期 RMS算法的收敛性 数学第二教研宣李宗元 摘要 RMS算法是K.S.Chandras等人1982年提出的一种可用于非光滑函数的线搜索优化算法['门它具有调用函数次数 少，CPU时间短等突出优点。 本文补充了文献[]中未讨论的退化情况，并对RMS算法加以修改，使其理论上趋于完善。本文还论证了在一 定条件下RMS算法的收敏性。 线搜索(Linear Search)是最优化算法的基本组成部分。它不仅可以直接求解一维 优化问题，更重要的是，在多维优化问题： minf(x)x∈E 的求解过程中，往往采用搜索选代策略，搜紫点列{x()}为： x(2)=x()+ad) 其中的d()为在x()点处的搜索方向，a:为最优步长。由x)出发沿d)搜索时，最优 步长的确定就是一个一维优化问题： f(x(k)+ad(k))=minf(x(k)+ad(k)) 由此可见，线搜索在最优化程序中占有很大的比重，对程序的效率，稳定性，甚至成败 都有重大影响。所以，线搜索算法是一个研究很多的领域。 线搜索优化算法中常用的有黄金分割法，抛物线拟和法和立方插值法，都比较有效。 1982年，M.V.C.Rao和K.S.Chandra提出了一种可用于非光滑函数的新的线搜索 算法，称为RMS算法C1]。引起了广泛的注意。本文在简要介绍该算法的基础上指出该 文所未讨论的，但在理论上不能忽视的退化情况。并论证了在一定条件下RMS算法的收 敛性。 一、RMS算法 1算法的构成： 设目标函数f(x)为f:E'→E的单峰连续函数（实为单谷函数），其最小点xot唯 f(xopt)=minf(x) 搜索xt分为两个阶段： stage I, 118

能 京 桐 铁 攀 院 学 报 恤幼一年 如一期 算法的收敛性 数学第二教研 室 李 宗元 摘 要 算法是 五 等人 年提 出的 一种可用于非光滑函数的线搜索优化算法 ‘ 〕 少 ， 时间短等突出优点 。 本文补充了 文献 〔 ’ 〕 中未讨论的退化情况 ， 并对 算法加以 修改 ， 使其理论上趋于完善 。 定条件下 算法的收敛性 。 它具有调用 函数次数 本文还论证 了在 一 线搜索 是 最优化算法 的基本组 成部分 。 它不仅可 以直接求解一 维 优化问题 ， 更重要的是 ， 在多维优化问题 任 的求解过程 中 ， 往往采用搜索选代策略 ， 搜索点列 为 立 七 、 七 其中的 ” 为在 幻 点处的搜索方向 ， 傲为最优步长 。 由 出发沿 幻 搜索 时 ， 最 优 步长兔的确定就是一个一 维优化间题 七 、 由此可见 ， 线搜索在最优化程序 中占有很大 的比重 ， 对程序 的效率 ， 稳定性 ， 甚至 成 败 都有重大影响 。 所 以 ， 线搜索算法是一个研究很多的领域 。 线搜索优化算法 中常用的有黄金分割 法 ， 抛物线拟和法和 立方擂值法 ， 都 比较有效 。 年 ， 。 和 提 出了一种可用于非光滑 函数的新的线 搜索 算法 ， 称为 算法 〔 ‘ 〕 。 引起 了 广泛 的注意 。 本文在简要介绍该算法 的基础上指 出该 文所未讨论 的 ， 但在理论上不 能忽视 的退化情况 。 并论证 了在一定条件下 算 法 的 收 敛性 。 一 、 算法 算法 的构成 设 目标函数 为 ‘， 二的单峰连续函数 实为单谷 函 数 ， 其 最 小 点 唯 一 吕 搜索 分为两个阶段 DOI ：10．13374／j ．issn1001－053x．1984．04．011

step1令x1=a「1=f(x:)n:=1a适当选定， step2 n:=n+1 fa:=f(x)x=F To+a (T0为初始步长：02? 若是，则进行step5 x 若否，则T:=) 3 -n:=1,转向step2, step5,R=xn-x1 《 计算 x0:= 1=1 (x称为RMS点) n fo:=f(xo) 置f,:=fo step6 fa:=min(f f2.fafo) B:={xi|f(x)=fBi=0,1,2,…n} 取x0x1…x.中B的相邻点，记作A,C。 使得：A<B<C及fA≥fB≤fc,即单峰区间为[AC]。 stage I step7,计算xu: x:=[A++C] fo:=f(xo)置fp:=fo step8检验lfs-fpl≤e|fl?(e为精度) 若满足，则停机，xo=Xa 若否，则令f:=fp fma=min(fA,fB,fc,fo) A fB:=fmia B:{xIf(x)=fB=fmia 取B的相邻点A,C,使得 A<B<C及fA≥fB≤fc 返回step7。 2,RMS算法的性能研究： 对表I中所列的五个检验函数，在计算机上分别用黄金分割法(GOLDEN)抛物线 拟合法(QDRA)，立方插值法(CUBIC)和RMS算法进行迭代搜索，其结果见表2，表 118

令 ， 适 当选定， 。 。 、 为 初始步长 。 成 。 为 数列 的第 项 ， 。 卜 一 若 》 ， 则转向 ， 检验不 等式 。 若满足 ， 则进行 ， 若否 ， 则返回 ， ， 若是 ， 则进行 一 。 二 、 、 、 。 有 卜仁了，纵妞 。 二 一 二 ， 朽 叫 匕 ‘ ， ， 。 一 艺 计算 。 【卫井 一 于 。 称为 点 。 置 。 。 … ， 二 ， ， ， … 取 。 … 。 中 的相邻点 ， 记作 ， 使得 及 》 。 簇 ， 即单峰区间为 〔 〕 。 卫 ， 计 算 。 、 。 、 二兰上旦土 生 一 去 ‘ 。 置 检验 一 ， 《 。 ， 。 为精度 若满足 ， 则停机 ， 。 若否 ， 则令 ， 二 。 ， 。 ， ， 二 。 。 二 ，。 取 的相邻点 ， ， 使得 及 。 《 返 回 。 ， 算法的性能研究 对表 工中所 列 的五个检验 函数 ， 在计算机上分别用黄金分割法 抛物线 拟食法 ， 立方插值法 和 算法进行迭代搜索 ， 其结果见表 ，表

。由表2，表3可见：一般说来RMS算法调用函数次数及CPU时间较其它三种方法要少， 显示了其优越性。 表1 检验函数f(x) Xopt f(xopt) 例1.f(x)=x5-5x3-20x+5 2.0 -43.0 例2.f(x)=x-8.5x3-31.0625x2-7.5x+5 8.278 -2271.573 30-{100.82+1.0当x308 5(x-0.8)2+1.0当x0.1 0.1 1.0 、1.0 当x=0.1 例5f(x)=(x+4)(x+2)2(x+5)(x+3)(x-16) 12.679 -4363340.0 表2 (Tg=0.5) 检验 CPU时间（微秒） 函数调用次数 Xopt 搜索算法 函数 e=10-3 e=106 e=10-3e=10-6 e=10-3 e=10-8 例1 RMS 4836 7254 11 15 1.993172 1.998137 GOLDEN 7592 13052 21 91 1.999223 1.999985 QDRA 8684 9022 13 13 1.999307 1.999307 CUBIC 6344 6422 21 21 2.000000 2.000000 例2 RMS 6266 10166 15 22 8.244565 8.280174 GOLDEN 8484 12298 24 34 8.279961 8.278446 QDRA 13806 13806 20 20 8.267171 8.267171 CUBIC 8970 8970 30 30 8.278462 8.278462 例3 RMS 5434 8216 12 19 0.795402 0.800048 GOLDEN 4654 8658 16 30 0.799907 0.799997 QDRA 25480 25480 33 33 0.767427 0.767427 CUBIC 29380 29380 99 99 0.794011 0.794011 120

。 由表 ， 表 可见 一 般说来 算法调 用函数 次数及 时间较 其它三 种方法要 少 ， 显示 了其优越 性 。 表 检 验 函 数 ， 。 。 例 “ 一 “ 一 。 一 。 例 ‘ 一 。 “ 一 。 一 。 。 一 。 例 “ ， 一 。 。 当 。 一 。 当 妻 。 工 。 。 ‘ 一 “ · ‘ ” ‘ · 。 当 · ‘ 例 “ ‘ ，“ ‘ 一 。 · ‘ ， “ ‘ · 。 当 ” · ‘ 气 。 当 。 。 例 “ 一 。 一 。 表 。 。 检验 函数 时 间 微秒 函数调 用次数 搜索算法 一 已 一 一 一 一 一 。 。 。 。 。 。 。 。 例 一 一 例 。 。 。 。 。 。 。 。 口，通 口以自丹几 口心巧，立 曰口︸ 例 。 。 。 。 。 。 。

续表2 检羚 CPU时间（微秒） 函数调用次数 Xopt 搜索算法 函数 e=10~3 E=10-B e=10-3 e=10~9 e=10-3 e=10-6 例4 RMS 11882 16536 30 39 0.0995080.100000 GOLDEN 8112 10790 31 39 0.099939 0.099997 QDRA 24154 24154 33 33 0.307071 0.307071 CUBIC 29224 29224 96 96 0.103645 0.103645 例5 RMS 6318 9724 16 23 12.591170 12.678000 GOLDEN 7540 12038 23 36 12.68896012.679120 QDRA 11856 11856 18 18 :12.66708012.667080 CUBIC 9776 10993 33 36 12.679120'12.679120 表3 (e=104) 检验 CPU时间（微秒） 函数调用次数 Xopt 搜索算法 函数 T。=0.3 T。=0.5 T。=0.3 T。=0.5 T。=0.3:T。=0.5 例1 RMS 6422 6370 15 14 1,995189 1.999347 GOLDEN 8710 8892 25 25 2.000228 2,000226 QDRA 8996 8684 14 13 1.999080 1.999307 CUBIC 7488 6422 24 21 2,000000 2.000000 例2 RMS 8242 6812 19 16 8.293157 8.292285 GOLDEN 9854 9698 28 28 8.2789778.278977 QDRA 8918 13806 15 20 8.275093 8.267161 CUBIC 8918 8970 30 30 8.277846 8.278462 例3 RMS 4940 5616 12 13 0.7991910.797831 GOLDEN 6058 6058 21 21 0.799958:0,799958 QDRA 25662 25400 34 33 0.7531240.767427 CUBIC 29822 29380 102 99 0.788248 0.794011 例4 RMS 9906 13780 27 33 0.100474:0.099944 GOLDEN 9672 9672 35 35 0.09999810.099998 QDRA 25246 24154 33 33 0.289115:0.307071 CUBIC 28080 29224 96 96 0.1050360.103645 例5 RMS 7930 7332 19 18 12.63506012.653180 GOLDEN 9126 9126 27 27 12.67933012.679330 QDRA 19500 11850 28 18 12.66488012.667080 CUBIC 11752 10993 42 36 12.67912012.679120 121

续表 检验 函数 时 间 微秒 七 搜索算法 函数调用 次 数 一 二 一 一 。 ￡ 一 ‘ 例 。 。 。 。 。 。 。 。 代曰口 ，丹 。 甘八曰八 丹 ，﹄口，一 ‘ ，，孟人 匕丹 、例 、 ， 。 。 。 。 。 。 。 。 。 一一一一‘ 一一一一一一一 ‘ 一一 表 一 ‘ 检脸 函数 时向 微秒 搜索算法 一 一 函数调 用次数 即 。 。 。 。 。 例 二 。 。 。 。 。 。 。 。 。 。 。 曰，自，，二勺 氏口任任︸月浦 心自，上几 任尸内‘ 自，内 口匕八“︶﹄ 乙‘」八 八”七甘几 例 ‘ … 。 。 。 。 。 。 。 。 曰人 邪﹁ ，，︼ 例 。 。 。 。 。 。 。 。 自八 月勺，口户了 例 例 ， … 人 ， … 吟‘ 谙占，口 匕八才 。 。 。 。 。 。 。 ， 。 。 。 。 。 。 一 ‘ 。 。 自今性月 拭自︸︹

二、修改的RMS算法 RMS算法属于区间收缩法。在迭代的过程中，应该形成一个包含xom的区间套，因 此，收敛性的关键在于这个区间套是否能够形成。 在RMS算法的step7中，=[A++C:±，如果x0=B,则算法终止， 3 若此时的xo牛xo,我们称这种情况为退化情形。 RMS算法在理论上存在着退化的可能，构造反例如下： 反例： 取T0=1a=0.1,则有： x1=0.1x:=1.1xg=2.1x1=F1+a=F1+0.1 【 其中：F1=F-1+F-2(i≥4)即{F:}为 Fibonacci数列（但F:=0) 当n=6时 6 是F: (）+2×a+a) =(（283+1g9+o.1）÷ 3 =√/17.81=4.2202 而x4=F.T0+a=3.1 A B x6=FgT0+a=5.1 (X)(Xg)(X) X4fB<fc 但（A++C-）+=（3.1+17:81+5.1)产=y17.8=B 3 3 而x0=B+xt即产生了退化，尚未达到KoPt RMS算法已终止。 RMS算法存在着退化的可能，并将影响其收敛性。为消除这种情况，需将算法修改， 今增加一个△一精度检验以及对称对比策略。则可得修改的RMS算法。 修改的RMS算法： stage I: stepl-~step6,同RMS算法 stage I: d 1绍

二 、 修改的 算法 算法属于 区 间收缩法 。 在迭代 的过程中 ， 应该形成一个包含 、 的 区 间 套 ， 因 此 ， 收敛性的关键在于这个区 间套是否能够形成 。 在 算法的 中 ， 。 忿 去 ， 如果二 。 ， 则算 法 终 止 ， 若此时的 。 今 ， 我们称这种情况为退化情形 。 算法在理论上存在着退化的可能 ， 构造反例如下 反例 取 。 二 ， 则有 。 。 。 一 一 。 其中 卜 卜 》 即 为 数列 但 当 时 袭 ， 于 「‘ 一 人 “ “ “一 后一 喧 乏 气 艺 于 誉 等 。 于 亿丁兀丽 二 而 ‘ ‘ 。 。 二 。 ’ 一 。 令 ‘ 。 。 由图 知 义 。 图 但 止竺土少土全上、 于 」卫竺 丛旦丝 工八于 不厂石 一 、 ， 、 ， 一 而 。 二 斗 。 。 即产生 了退化 ， 尚未达到 。 。 算法已终止 。 算法存在着退化的可能 ， 并将影 响其收敛性 。 为 消除这种情况 ， 需将算法修 改 ， 今增加一个△ － 精度检验 以及对称对 比策略 。 则可 得修改的 算法 。 修改的 算法 ， 同 算法 五

p计算x,x1-[A“+B+C]十 若xa+B,则fo:=f(xo)置fp:=fo 进行step9 若x0=B,则检验△=C-A≤Ea?(ea事先给定) 若满足，则停机，x0=x。 若否，则进行step8 step8,计算B'=A+(C-B) fg=f(Bi) 检验f'≤f? 若满足，且B'B,则A:=BB:=B',转向step7, 2 若否，且B'B,则C:=B'转向step7. step9,检验Ifs-fpl≤|ipl?(e,事先给定) 若满足，则停机xo=x0 若否，则令fs:=p fmin=min(fA,fB,fc,fo) fB:=fmin B:={xIf(x)=fB=fmin 取B的相邻点A,C,使得： AF2F1+FL>F1 X。 2 2 A+C2>B:式A+B+C2>B X X。d) 2 3 即不产生退化情况。 图2 (b)A=x0B=x+1C=x+2(图2-b) 反证法，若不然，即设A+B+C2=B:或A3十C:=B: 3 2 则：X02=2x21+1-X21+2 123

， 计算 。 ， 【 “ 】 去 若 。 钾 ， 则 。 置 ， ， 。 进 行 若 。 ， 则检验 △ 一 凡 勺事先给定 若满足 ， 则停机 ， 。 ，。 。 若否 ， 则进行 ， 计算 ， 一 ， ’ 检脸 ， 《 若满足 ， 且， ， 则 二 ， 转向 若满足 ， 且 ‘ ， 则 ， ， 转向 若否 ， 且 ‘ ， 则 ， 转向 若否 ， 且 ， ， 则 ， 转向 ， 检验 一 《 引 ， 事先给定 若满足 ， 则停机 。 若否 ， 则令 ， 。 ， ， 二 。 。 。 。 取 的相邻点 ， ， 使得 且 》 转向 。 三 、 算法 的收敛性 〔引理 〕 ， 修改的 算法 ， 在初始单峰区 间上不会发生退化 。 证明 初始单峰 区 间有下述 四种可能 图 一 ’ 卜 ， 十 图 一 “ “ 。 告 〔 ‘ 卜 。 ， “ ‘ ， 。 ，“ “ 卜 一， 名 早 ，军一 。 一 罕 十 一十 一 ， 么 ，卫 、 。 ， － 奋 奋一 名 一 军 。 ， 恶 名 式 念 打尸，打一一 了 即不产生退化情况 。 图 。 不 二 ，罕 图 一 反证法 ， 则 若不然 ， 即设 名 或 名 “ 一 “ 早

=2(F4:T。+a2)-(F4zT。+a) =(2F2F1-F24z)T。2+2(2F+1-F+2)Ta+a2 <F2-1T。2+2Fi-1Toa+a2 即x0<x2:-1或x0<x1-1与x<x0<x+1矛盾 (c)A=x;B=x0C=xi+,(图2一c) 由修改的RMS算法step7,step8可得出非退化结论。 (d)A=x1-1B=x1C=x0(图2-d) 也可由修改的RMS算法step7,step8得出非退化结论。 证毕 [定理]若f(x)为f:E'→E'的单峰连续函数，由修改的RMS算法产生的搜索点列 {x2。(K)},(xa(K)表示第k次搜案区间上的RMS点x) i,或在有限步终止于最优点xo ii,或limx0(K)=xoP即{x0(K)}收敛于敏优点xot, 上中钟 证明，只需证明i*。施行数学归纳法： 当k=1时，由引理知不产生遐化， 设第k次迭代不产生退化，今证在定理条件下 第k+1次迭代也不发生退化。分四种情况讨论 (图3)： (a)B<xa<CfB≥fo≤fe =【A++c-] B X. C 第k+1次迭代时，A:=BB:=x0 图8-a 此时无退化可能，因为退化，则有： B2+C2+A2+B2+C2 3 A2+B:+C2 3 3 i可得，B2+C2=2A2与A<B<C矛盾 .k+1次迭代时不发生退化。 (b)A<B<x0fa≥fB≤fc 在第k+1次迭代时，需C:=x0 X1= A2+B2+C21± 3 A2+B2+A2+B2+C2 若退化，即 3 3 一一=B2时 B Xa C 则由修改的RMS算法step7,step8可以消除 图8-b (c)A<xo<Bfa≥f。≤fB 在第k+1次迭代时，B:=x。C:=B ·i仅发生在e3=0的情形，对i的论证可包舍i。 124

念 李 。 名 一 幸 。 二 ’ 一罕 一 ’ 二 军一 宋 忍 卜 卜 ， 即 。 名 或 。 ，一 与 ， 矛盾 二 。 不 图 一 由修改的 算法 ， 可 得出非退化结论 。 二 卜 图 一 也可 由修改的 算法 ， 得出非退化结论 。 证毕 〔定理 〕 若 为 尹， 尹 的单峰连续 函数 ， 由修改的 算法产生的搜索点列 毛 “ 。 ， 。 表示第 次搜索区 间上 的 点 。 ， 或在有限步终止于 最优点 叭 ， ， 或 ‘ ， 即 。 ‘ 收敛于最优点 。 ， ， 证 明 只 需证 明 。 施行数学归纳法 当 时 ， 由引理知 不产生退化， 设 第 次迭 代不产生退化 ， 今证在定理条件 下 第 次迭 代也不 发生退化 。 分 四 种情况讨论 图 。 》 《 又 。 卜鑫竺土里土旦七 士 」 第 次迭 代 时 ， 二 ， 翔 此时无 退化 可 能 ， 因为退化 ， 则有 扩一丈一一右一 图 一 ， 一 一丁一 一 月 ， 忍 可得 ， ， 与 矛盾 了 次迭代 时不 发生退化 。 《 在第 次迭代 时 ， 需 二 。 兰〕 寺 若退化 ， 即 － 二 时 天 则 由修改 的 算法 ， 可 以消除 《 。 在第 次迭代时 ， 。 二 ‘ “ 仅发生 在 八 二 。 的 情形 ， 对行的 论证 可 包含 几 图

x,=[A++:] A2+B2+A2+B2+C2 此时无退化可能，因若退化，则有 3 3 —=A2+B2+C2 3 即C2=A2+B2 2 与Af时，则A:=B'。由f(x)的单峰性知，在[A,B门上f(x)单调减小，故保留区 间[A,C门1+1仍是单峰区间。 综上讨论知：修改的RMS算法总能产生一个包含xwt的区间套，且区间套的唯一公共 点x0=xoP,即1imxo(K)=xOp, 证毕。 k*0 周汉良同志对本文提出过许多有益的意见，作者仅表示衷心感谢。 参考文献 [1]M.V,C.Rao and K.S.Chandra:A New Unidimensional Search Method for Optimization.戟：Engineering Optimization 1982.Vol6P39一50. [2]华罗庚：优选学1981. 125

。 专 － 一一－－ 一 必 千 一 万 － 一 一 时 不 之目 才卜 衬 如 国 业 卜 欣 右 乞 笋仁 场 ‘ 王玉 山 玛 匕 ， 目 们 七盏 山 ， 男幼 月 一 一 。 一 一 一 一 一 一 一 。 吕 即 与 矛盾 。 。 》 。 在第 次迭 代时 二 。 ， 专 。 二 一一一 一 一 －」 、 巳 ‘ 贻 曰叫 尸 孟 若退化 ， 即 。 图 呜 则 由 ， 可 以 消除 ’ 第 次迭代 时不 发生退化 。 于是 ， 修改的 算法产生 了一个 区 间套 ， 记作 ， 〕 〕 ， 」 … 。 〔 ， 〕 。 。 … 且 其区 间长△ 二 一 有 △ “ 今 盆 则 山区 间套定理 知 必存在唯 一 的 · 个 点 。 ， 满 足 。 任 ， 〕 ， ， … 山修改 的 算法 知 ， 若不 发生退化 ， 则 每 一个 区 间 〔 ， 〕 都是 单峰 区 间 ， 即每一 个 区 间 〔 ， 〕 都包含唯一的极小点， 而 当在 〔 ， 〕 ，上发 生退化时 ， 由 ， 知 。 图 犷 》 若 。 ， 时 ， 则 ， ， 。 由 的单峰性知在 〔 ， ，上 单调 增力 故保留区 间 〔 ， 〕 十 仍为单峰区 间， 若几 尹 时 ，则 ， 。 由 的单峰性知 ，在 〔 ，， 」上 单调 减小 ， 故保 留 区 间 〔 ， 〕 ， 仍是单峰区 间 。 综上讨论知 修改的 算法总能产生一个 包含 。 。的区 间套 ， 且 区 间套的唯 一公共 点 。 ， 即 证毕 周汉 良同志对本文提 出过 许多有益 的意见 ， 作者仅表示衷心 感谢 。 参 考 文 献 〕 载 〔 〕 华罗庚 优 选学 。 。 一

convergence of RMS Algorithm Li Zongyuan Abstract The RMS algorithm was initiated by K.S.Chandra and M.V.Rao in [1]. But in [1]the possiblity of degeneration was neglected.In our paper,we con- struct a counterexample showing that degeneration may infer the non-conver- gence of the algorithm and we make some corrections to the algorithm so th- at we can prove the convergence of the correeted algorithm. S 1 126

李攀 。 。 。 〕 。 ， 主 恤 一 丫 。 址 至门兮甲