D0I:10.13374/i.issn1001-053x.2000.06.023 第22卷第6期 北京科技大学学报 VoL22 No.6 2000年12月 Journal of University of Science and Technology Beijing Dec.2000 带有参数的Perry-Shanno无记忆 拟牛顿方法的收敛性 谢铁军》陈明文)程涛2》 1)北京科技大学应用科学学院，北京1000832)北京航空航天大学动力工程系，北京100083 摘要分析了带有可调参数的Pery-Shanno无记忆拟牛顿方法的收敛性.证明了对于非凸 目标函数，在非精确搜索条件下，参数在一定范围内，算法是收敛的 关键词非凸目标函数；非精确线搜缴：Perry-Shanno无记忆拟牛顿方法：收敛性 分类号 0221.2 文献标识码：A 1 无记忆拟牛顿方法的收敛性 函数，在Armijo线搜索或Wolfe线搜索条件下， 算法收敛；对于凸目标函数，在Wolfe线搜索条 考患无约束最优化问题 件下也是收敛的.但是对非凸目标函数，目前 minf(x) x∈R (1) 尚无统一的收敛结果 在研究迭代公式(2(4)时，我们注意到B 其中，f:R一R是R上的连续可微函数.Pery- 和H,可以表述成更一般的形式： Shanno无记忆拟牛顿方法是由Perry和Shanno (8) 首先提出的(Perry J M.Northwestern University, Ba-送 1997),以后得到进一步发展.这种方法的迭代 时云m SkSE- 公式如下： a46s+⅓s） 1 (9) x=xx+d d1=-Hg+1=-B1g1 (2) 其中，a心0为可调参数. d,=-g1 由a0及(T)式容易证明：由(8)确定的B1 其中，P0为搜索步长，4为搜索方向，g=口fx) 对称正定且满足拟牛顿方程：在精确线搜索条 为fx)在x点处的梯度， 件下，由(2)，（⑧）和(9)式所确定的d4满足共轭条 +x- B1= T5P好 (3) 件R(g+1一g0.我们称由(2)，(8)和(9)式所构 成的迭代公式为带有可调参数的无记忆拟牛顿 H1=B=I+2-（ aPy+y用 (4) 方法，本文将讨论对于非凸目标函数，在Wolfe s=x1一x=Ad,h=g+1-g,I为n×n单位阵 线搜索条件下，带有可调参数的无记忆拟牛顿 在Wolfe线搜索条件下，即满足 方法的收敛性， fx+d)≤f八x+cgd (5) gx+d)rd≥cgde (6) 2主要结果 其中，0<c<c2≤1/2.由(6)可得： 本文假设(H): ys2(1-c)(-gtd)>0 (I)fx)连续可微，7fx)满足Lipschitz条 或 ys2(1-c(-gs)>0 (7) 件：l‖ロfy)-7fz)l≤Lly-zl 对Wolfe线搜索，由(T)式可证明B,对称正 (2)水平集={fx)sfx)}有界， 定且满足拟牛顿方程，关于Pery-Shanno拟牛 由B,H对称正定性可得到 顿方法的收敛性有下列结果：对于一致凸目标 引理1 2000-01-25收稿谢铁军男，37岁，讲师 g业s(B） giHigt (10)
第 卷 第 期 年 月 北 京 科 技 大 学 学 报 介 忱 。 带有参数的 一 无记 ， 拟牛顿方法 的收敛性 谢铁军 ” 陈明文 ‘ ， 程 涛 ， 北京科技大学应用科学学院 ， 北京 北京航空航天大学动力工程系 ， 北京 摘 要 分析 了带有可 调参数 的 了一 无记忆拟 牛顿方法 的收敛性 证 明 了对于 非凸 目标 函数 ， 在非精确 搜索条件下 ， 参数在一定 范 围内 ， 算法是收敛 的 关键词 非 凸 目标 函数 非精确线搜索 一 无记忆拟牛顿方法 收敛性 分 类号 文献标识码 无记忆拟牛顿方法 的收敛性 考虑无约 束最优化 问题 运八才 其 中 ， 尸一 是 尸 上 的连续可微 函 数 一 无 记忆拟 牛 顿方法是 由 和 首先提 ， 出 的伊 叮 ， 以后得到进一 步发展 这种方法 的迭代 公式 如 下 函数 ， 在 。 线搜索或 线搜索条件下 ， 算法 收敛 对 于 凸 目标 函 数 ， 在 线搜索条 件下 也 是 收敛 的【 但是对 非 凸 目标 函数 ， 目前 尚无统一 的收敛 结果 【， 在研究迭代 公式 曰 时 ， 我们注 意到 凡 ， 和 从 十， 可 以表述成更一 般 的形 式 凡 可 几口一 从 十， 动 卜 】 一尤几减威 ‘ 一琉 争 一蹋乡 一 ， 其中汉户心 为搜索步长 ， 为搜索方向 ， 乡 甲刀成 为厂以 在 尤‘ 点处的梯度 ， 凡 月卜 ， 毗 二 区上 、 理互一业山立 。 ， 办 ‘ ’ 户 仁 咖 。 树 ‘ 却 乏 ， 试 ， ， 。 丁阮平 ’ 甲‘ 而 一石平、缈训 ， 四 孙 一丸 又威 ， 乡 ，一乳 为 单位阵 在 线搜索条件下 ，即瓜满足 厂以 孟玖诚 ‘ 厂以仍 ，又翻汉 琪时又威 之 域峨 其中 ， 勺 ‘ 由 可得 户 七 一 负 凡 一多峨 或 之 一 一沙 对 线搜索 ， 由 式可证 明 凡 ， 对称正 定 且满足拟牛顿方 程 关于 一 拟 牛 顿方法 的收敛性有 下 列 结 果 对 于 一 致 凸 目标 其 中声户心 为可调参数 由 “ 户心 及 式容 易证 明 由 确 定 的 凡 ， 对称 正 定且满足拟 牛顿方程 在 精确 线搜索条 件下 ， 由 ， 和 式所确 定 的 峨 满足共扼 条 件 呱 ，俪 ，一承 我们 称 由 ， 和 式所构 成 的迭代公式为带有可调 参数 的无记忆拟牛顿 方法 本文将 讨 论对 于 非 凸 目标 函 数 ， 在 线搜索 条件下 ， 带有 可 调 参数 的无记 忆拟 牛顿 方法 的收敛性 主要结果 本文假设 功 功 连 续 可 微 ， 甲厂以 满 足 条 件 甲厂沙一 甲尹仕 ‘ 引沙一 水平集 沙 ‘ 了卜 有 界 由凡从 对称正定性可得到 引理 一 一 收稿 谢铁军 男 ， 岁 ， 讲师 渠粤 、 试刀。 」 店 DOI ：10．13374／j ．issn1001－053x．2000．06．023
VoL22 No.6 谢铁军等：带有参数的Pery-Shanno无记忆拟牛顿方法的收敛特性 ·573· H.glsu(H） giHig: (11) w-fx】=含)- 其中，r(B)为B.的迹.下面的引理来自文献[5]. 01 引理2在假设()下，下列结论成立： aW-fI≥w-ftH )-/.)=(is' (gFd)2、o1 L (12) 点o(lol'Tral2-H 定理在假设(H价下，点列{x}由(2)，（⑧）和(9)式产 e2e业名惑2wa+ 生， 若 Ihll-→0(k→o) (13) Le三m产就W-e+ c1-c业21 且 y 。22 ,≤a,≤-cgd (14) c(1-cL龙 L 4io n(n-2)(k-ko+1)+M+o0 (23) 则 lim infllgll =0. 另一方面，由(H)假设有： 证明：用反证法，设定理结论不成立，则存 盒)1<+n (24) 在常数>0，使g>4对一切k都成立.由(8)9) 与(23)式矛盾.此矛盾说明定理是正确的. 式得B1,H1的迹 证毕， (B..)=a(n-1)+ly (15) 注：当a=yysx时，便文献[5]中的定理3的结 t()=n-2rl2s划 论. C s04a4S52 (16) 推论在(H)假设下，点列{x}由式(2)，（⑧） 由式(15)和(16)得： 和(9)式产生，且a满足式(14). a)amA=(a-1a-2a 若 x→x(k+o), (n-1)(Is lim infllgall =0. asiy) (17) 则 Siyt aiSiyt 由式(14)得： 证明：由式(15)得→0(k一∞)， 女≤资及a≤a- 2 由假设(H)得：ly≤Lls‖一0(k一∞) (18) 因此lim infllgell=0. 再由式(7)得： 1 1 s(1-c-g而 (19) 3结论 把式(18)和(19)代入(17)得： 本文提出了带有可调参数的无记忆拟牛顿 t(B)u(Hm-)n(n-2)+(id 2nyll‖dl2 方法，并分析了其收敛性.证明a了在一定范围 2nllyllllgllldll Mn-2r02e22m-24 内，在充分条件y→O或x→x下，算法是收敛 的.在的选取范围进一步扩大时算法是否收 2nlla2lg2Hg✉2 (1-c2yllga (g:Hig)(giHigA (20) 敛：以及如何寻找更弱的条件使算法收敛，还有 由引理1，把式(10)和(11)式代入(20)式得： 待于进一步研究. 2n llyell2 t(B..)t()sn(n-2)((B)r(H) 参考文献 Ma-2小2号BUW2) 1 Powell MJ D.Restart Procedures for the Conjugate Gradi- ent Method.Math Prog,1977,12:241 由(13)式，存在k>0,当k≥k时 2 Shanno D F.On the Convergence of a New Conjugate Iwls-2业. Gradient Algorithm.SIAM J,Numer Snal,1978,15:1247 2n 3 Powell,M J D.Conjugate Cradient Method with Inexace 因此得，当之k时， Searches.Mathematics of Operation Research,1978(3): tr(B)tr(H)sn(n-2)+tr(B:)tr(H:) 244 4袁亚湘，非线性规划数值方法，上海：上海科技出版 ≤…， 社，1993 sn(n-2)(k-ko+1)+tr(Bgo)tr(Ho)= 5 Han Jiue,Liu Guanghui,Yin Hongxia.Convergence of n(n-2)k-k+1)+M (22) Perry and Shanno's Memoryless Quasi-Newton Method 其中，M=t(Bo(Ho). for Nonconvex Optimization Problems.运筹学学报， 由引理1，引理2及(22)式得： 1997,1(1):22
、 乞 谢铁军等 带有参 数 的 一 无记忆拟牛 顿方法 的收敛特性 黯 ‘ 其中 ， 川田 为 的迹 下面训的引理来 自文献【 引理 在假设 功 下 ， 下列结论成立 。 加一 三助风 一厂以卜加一 三以卜。 一厂以卜加 幼一 三以卜。 一厂以卜 加‘ 三以卜 一厂以卜介 、 一 、 修丛乍旦 乡，，尚罐平 ‘ 的一 ‘ 三助风 一厂以卜介 定理 在假设 功 下 ， 点列 从 由 ， 和 式产 以卜 一厂以卜 卜 川卜 一 」全尘‘ 。 ‘ 一』园二一 户 正 ‘ 咐“ 一伪 凡侈峨 勿 一 助风 一厂以卜， 〕 旦卫业二鱼渔兰寻 一一一 互－ 、 ， 瑞 一 一瓜 ’ 一 另一方面 ， 由 功 假设有 艺以卜 一厂以卜 二 若生且则 证 明 用 反证 法 ， 设 定理 结论不成 立 ， 则存 在常数 产 ， 使 乡 冲 对一切 都成立 由 式得 凡 ， 认 ， 的迹 州田卜 试月公 由式 和 得 若 动 ‘ 呱 火 ，呱 ，一 一 ‘，‘一 卜到瓮禁蛛 与 式矛盾 此矛盾说 明定理是正确的 证毕 注 当 队 汉 时 ， 便文献 中的定理 的结 论 推论 在 功 假 设下 ， 点列 由式 ， 和 式产 生 ， 且 几 满足式 ‘产、产、 口 ‘、了 ，门二 ︶ 了、、 以 一 由式 得 ， ‘ 一 二 ， 短 日 卜 奈儡 及 石二万招些而 再 由式 得 证 明 由式 得 几一 一 二 ， 由假设 功 得 川 ‘ 卜 一 劝 因此 妙 圳 一 迎匕心一一卫二 一 ‘ 户 一 一 ‘ 林 正 一多试 把式 和 代入 得 ，呱 ，‘ · ‘一， 黔翼黔 一 一 卫 ， 业些卫二一 卫了石」邀 互 卫二、 卫 石 互邀尘、 、 ‘ 、 ‘ 占 、占 上 止 止占 、占 上 正占妙 由引理 ， 把式 和 式代入 式得 试刀卜 试从 十 ， ‘ 一 ， ， 、 ， ， ， 、 夕戈西习呢亦则 日 · 咐 一 妇裂黔‘ 叭 ， ，，， 由 式 ， 存在 冲 ， 当 七 时 二 ，， 一 负加 、 二只万二 ’ 因此得 ，当 之肠 时 ， 试刀卜 试月乍 ‘ 一 卜州万 花 试从 “ ’ ‘ ” ’ ‘ 一 一 川万 加 成编 一 一 其 中 ， 州田 加 试场 由弓 理 ， 引理 及 式得 结论 本文提 出 了带有可 调 参数 的无记忆拟牛 顿 方法 ， 并分析 了其收敛性 证 明 久 了在一 定范 围 内 ， 在充分条件 外 卜 或 从，’ 下 ， 算法是收敛 的 在 风 的选取 范 围进一步扩大 时算 法是 否 收 敛 以及如何寻 找更弱 的条件使算法收敛 ， 还有 待于进一 步研 究 参 考 文 献 吐 以 ， ， ， 切叮 ， ， ， 五 助 了 ， 袁亚湘 非线性规划数值方法 上海 上海科技 出版 社 ， ， ， ， 豹 叨 一 ，比 吻 加 运 筹 学 学 报 ，
·574· 北京科技大学学报 2000年第6期 Convergence of Perry and Shanno's Memoryless Quasi-Newton Method with Parameters XIE Tiejun,CHENG Mingwen,CHENG Tao 1)Applied Seience School,UST Beijing.Beijing 100083,China 2)4th Department,Beijing University of Aeronautics&Astronutics,Beijing 100083,China ABSTRACT The convergence of perry and Shanno's memoryless quasi-Newton method with parameteers is analyzed.It is proven that Perry and Shanno's memoryless quasi-Newton method with inexac line searches for on-convex objective function converges when parameters are in the given range. KEY WORDS non-convex objective function;inexact line search;perry and shanno's memoryless quasi- newton methoa;convergence (上接第500页) Detonation Velocity Characteristics of Emulsion Explosives Sensitized by Glass Micro-balloons SONG Jinquan2,WANG Xuguang 2,YU Yalun,CUI Anna 1)Resource Engineering School,UST Beijing,Beijing 100083,China 2)Beijing General Research Institute of Mining and Metallurgy,Beijing 100044,China ABSTRACT By means of the laboratory manufacture technology established by UST Beijing,emulsion ex- plosives(EE)test samples sensitized by glass micro-balloons(GMB)were manufacture.Influence of GMB content and density of EE on the detonation velocity are studied.The detonation velocity characteristics of the industrial explosives are analysed.With the increase of the deusity of EE,the detoration velocity first in- creases to the top point,then decreases,untill the emulsion explosiues have been dead pressed. KEYWORDS Detonation velocity Emulsion explosives Glass micro-balloons
。 北 京 科 技 大 学 学 报 年 第 期 ， 一 研沈 幻以 尤醒 月万封 ，， 月 脚召 械雌卿 ， ， ， ， 几。 印山由口印仁 匕 廿 ， 吨 ， ， 一 节沈 了 叮 ， ，八 一 卫 烧 节沈 一 了 ， 够 上 接第 页 一 口 孔 环月刀 筋岁 ’孔 ‘， ， 叨 力 ， ， ， 名， ， 奴江 ， 攻旧 仍 叭 勿 一 江 ， ， 小 ， 丫 一