（应用数学专业论文）非单调自动确定信赖域半径的信赖域算法研究.pdf

摘要 信赖域方法是求解无约束非线性优化问题的一类有效而强适的方法 其中 信赖域半径的选取对算法的效率具有非常重要的影响 近来 李改弟1 1 提出了 个自动确定信赖域半径的新策略 该策略利用目标函数的二次信息 没有额外 增加计算量 数值结果表明该策略是有效的 本文将两种不同的非单调技术引入 文献 1 的算法中 主要研究非单调技术对算法本身的改进 并证明了新算法的 全局收敛性 数值试验表明 新算法是有效的 关键词 无约束最优化信赖域方法全局收敛性非单调技术 a b s t r a c t t r u s tr e g i o nm e t h o di sak i n do fe l i i c i e n ta n dr o b u s tm e t h o dt os o l v eu n c o n s t r a l n e dn o n l i n e a ro p t i m i z a t i o n a n dt h ec h o i c e o ft h et r u s tr e g i o nr a d i u s i sv e r yi m p o r t a n tt ot h ee f f i c i e n c yo ft h ea l g o r i t h m r e c e n t l yg a i d il i 1 p r o p 0 8 e 8as t r a t e g yf o ra u t o m a t i cd e t e r m i n i n gt h et r u s tr e g i o nr a d i u sa te v e r yi t e r a t i o n w h i c hl l s e ss e c o n do r d e ri n f o r m a t i o na v a i l a b l e a n dd o e sn o ta u g m e n t c o m p u t a t i o n n u m e r i c a lr e s u l t so i lt e s tp r o b l e m ss h o wt h a tt h es t r a t e g yi se f f e c t i v e t h i st h e s i sc o m b i n e st w ok i n d so fn o n m o n o t o n et e c h n i q u et ot h ea d a p t i v e t r u s tr e g i o na l g o r i t h mp r o p o s e di n t h em a i ng o a li st os t u d yt h ei m p r o v e m e n to ft h ea l g o r i t h n lw i t ht h en o n m o n o t o n et e c h n i q u e t h eg l o b a lc o n v e r g e n c e r e s u l t so ft h ea l g o r i t h m sa r ee s t a b l i s h e d n u m e r i c a lr e s u l t ss h o wt h a tt h en o n m o n o t o n em e t h o 1 8a r e l o r ee l l i c i e n t k e yw o r d s u n c o n s t r a i n e do p t i m i z a t i o n t r u s tr c g i o nm e t h o d g l o b a lc o n v e r g e n c e n o n m o n o t o n em e t h o d s 静 a z 0 a x 1 0 全文通用记号 第k 次迭代点 第k 次迭代的步长因子 第k 次迭代的搜索方向 函数f x 在z 处的函数值 函数f 2 7 的梯度v f 2 7 在z 处的值 函数f x 在2 7 k 处的梯度向量v f w k 函数f 2 7 的h e s s i a n 矩阵v 2 f 2 7 在z 处的值 函数f 2 7 在2 7 k 处的h e s s i a n 矩阵v 2 z k 在z k 处的信赖域半径 e u c l i d e a n 范数 基于s c h n a b e l 和e s k o w d 3 1 1 的修正c h o l c s k y 分解的一个安全 正定矩阵 b k b k 最 其中当反正定时e k 0 否则取 为对角矩阵且使保证鼠成为正定矩阵 n 维欧氏空间 矩阵g 2 7 正半定 矩阵a z 正定 毗靠 出鲰 瓯乱 反 首都师范大学学位论文原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立进行研究 工作所取得的成果 除文中已经注明引用的内容外 本论文不含任何其他个人或 集体已经发表或撰写过的作品成果 对本文的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名 纯缉 日期 宇年6 币 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留 使用学位论文的规定 学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版 有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅 有权将 学位论文的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出 版 保密的学位论文在解密后适用本规定 学位论文作者签名 忱峰 日期 略铂3 备 1 非线性优化问题简介 这一章里 我们简要介绍非线性优化问题的发展现状 在第一节中 简 要地阐述最优化问题的提出以及判断最优解常用的最优性条件 在第二节 中简要介绍了求解无约束非线性优化问题常用的迭代方法 线搜索方法和 信赖域方法 主要介绍信赖域方法 在第三节中简要阐述非单调信赖域方 法的提出 在最后一节 介绍了我们提出新算法的主要思想 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科 它研究某些数学上定义的 问题的最优解 即对于给出的实际问题 从众多的方案中选出最优方案 虽然最优化可以追溯到十分古老的极值问题 但是直到1 9 4 7 年d a n t z i g 提 出一般线性规划问题的单纯形法之后 它才成为一门独立的学科 随着现代科技 的发展和计算机的广泛应用 进一步推动了最优化理论和方法的研究 今天 最优 化理论与方法在经济规划 工程设计 生产管理 交通运输等方面得到了广泛的 应用 成为一门十分活跃的学科 最优化问题数学模型的一般形式是 r a i n y x 3 t g 幻 0 i 1 m l q z 0 i m r 1 m 1 1 1 1 1 2 1 1 3 其中y x 和岛 z i 1 m 都是定义在舒上的z 的函数 z 是目标函数 q z i 1 m 是约束函数 1 1 2 称为等式约束条件 1 1 3 称为不等式约柬 条件 满足约束条件的点称为可行点 可行点的集合 x z i q z o i 1 一 m c d x 20 i m 1 m 称为可行域 当可行域是整个实数空间 即m 7 m 0 时 问题 1 1 1 一 1 1 3 是无约束优化问题 否则是约束优化问题 当 z 和c f z i 1 m 均为线性 函数 则问题 1 1 1 一 1 1 3 称为线性规划问题 反之 当厂 z 和q z i 1 m 中至少有 个非线性函数 则称问题 1 1 1 一 l 1 3 为非线性规划问题 相关内容 可见文献 2 3 4 1 本文主要研究无约束非线性最优化问题 即 躲s c x 其中 r l r 为非线性函数 假设i x 二次连续可微 下面我们给出全局最优解和局部最优解的定义 1 1 4 定义1 1 1 若矿 舻具有性质 对一切z 舻 均有f z 2f x 则称 为问题 1 1 4 的全局最优解 定义1 1 2 若矿 r i 具有性质 存在x 的某个邻域g d x 垒 i l z 一 矿i f 0 为某个正数 使得对一切 地 矿 均有 z 矿 则称矿为问题 1 1 4 的一个局部最优解 求解非线性最优化问题 1 1 4 就是要求目标函数i x 的全局最优解 但 在一般情形下 我们往往只能求出它的一个局部最优解 在很多实际应用中 求 局部极小点已满足问题的要求 因此 在非线性优化中 我们通常认为局部最优 解即为所求的解 仅当目标函数 z 是凸函数时 局部最优解就是全局最优解 下面我们给出最优性条件 2 引理1 1 3 i 2 一阶必要条件 若矿为问题 1 1 4 的 个局部最优解 且在 的某个聿b 域内 z c 1 贝0 g x 垒 t f x 0 1 15 引理1 1 4 吼二阶必要条件 若矿为问题 1 1 4 的 个局部最优解 且在 z 的某个邻域内 x e 2 贝4 g x 0 g x 0 1 j 1 6 引理1 1 5 2 二阶充分条件 若在矿的某个邻域内 z c 2 且 g x 0 c x 0 1 1 7 则矿为问题 i i 4 的一个严格孤立局部最优解 所谓矿是f x 的严格局部最优解 是指对任何z 矿且z 眦 矿 总 有 x z 所谓矿是 x 的孤立局部最优解 是指存在矿的一个邻域 肛 矿 在其内f x 除矿外没有其它局部极小点 引理1 1 6 国设 z 在形上为凸的且 g 1 则矿为 的全局最优解 当且仅当g x 0 在实际的算法中 我们通常是找出满足局部最优解的必要条件的点 求解非线性最优化问题 1 1 4 的基本算法是迭代算法 即给定初始点x l 毋 并在褥出 k 后 按照某个规则产生一个新的点瓠 t 如此 迭代地 得到一 个点列 z k 使得某个 恰好是最优化问题的最优解 或者 瓢 或它的一个 子序列 收敛到问题的一个最优解矿 通常称 z k 为极小化序列 产生 的一个常用的准则是使得目标函数 z 在z 处的值t 厂 z 较 有一定的下降实现这一目标的方法主要包括两大类 线搜索方法和信 赖域方法 本文主要研究信赖域方法 3 1 2 线搜索方法与信赖域方法 线搜索方法的基本思想是 在当前迭代点孤 首先产生一个搜索方向如 使 得目标函数f z 的值沿该方向是下降的 然后确定沿呶方向行进的步长o t k 并 得到下一个迭代点x k l 2 9 k o t k d k 在这里 我们要确定的搜索方向应满足z v f x r d k 0 0 0 c 3 c 4 1 c i 0s 唧曼c 2 l q 0 k 1 步2 如果i e 则停止 步3 求解信籁域子问题 1 2 1 得到试探步也 步4 计算预测下降量 实际下降量 p r e d k 饥 o 一峨 矗 1 22 a r e d k z 一 乳十d k 1 23 实际下降量与预测下降量的比值c a r e d k 2 p r e d 1 24 步5 根据比值 大小 决定是否接受试探步也以及如何调节信赖域半径 z k 1 l 选取 1 满足 以 纛篡 f c 3 0 也l i c 4 a k f a k c 1 a k l i 也 谢h e r w i s e 步6 修正鼠 仁k 十1 转步2 在算法中 岛 2 o 4 是由用户选择的常数 常用的数值是c a o 5 1 2 c 2 c 3 o 2 5 q 0 5 其它选取可参阅文献 6 7 8 9 孥 5 1 3 非单调信赖域方法的提出 现在广泛用来求解无约束非线性优化问题的绝大多数信赖域方法 都是与算 法1 2 i 类似的单调的信赖域方法 也就是产生的点列要求目标函数的值在每一 步都有下降 即 z 女 1 x k 这种单调性的要求好象是很自然的 因为算法的目的就是要找到在可行域内 使得目标函数的值最小的点 但是这种要求目标函数在迭代过程中严格单调下降 的性质并不是没有它的缺点 个典型的情况就是当目标函数在可行域中存在细 长弯曲的峡谷的情形时 单调性算法就会大大丧失它的计算效率 因为这时一旦 迭代进入峡谷 它就只能沿着峡谷缓慢前进 这样就会导致很小的步长 甚至出 现锯齿现象 基于对这种现象的观察 l g r i p p o 等f 10 l 在1 9 8 6 年对于牛顿法提出了一个 最初的非单调的线搜索框架 即找到步长o l k 满足 瓢 q 如 j m s a m x 埘 钆一j 触 蠢如 岛 o 1 2 一 其中 卢 0 1 m o 0 当k2i 时 0 m k 曼m i n m k 一1 q 1 m m 为 给定非负整数 以表示搜索方向 此后 许多学者把文献 1 0 提出的非单调线搜 索技术 与截断牛顿法i l i 共轭梯度法1 1 2 及拟牛顿法 1 3 1 4 等经典无约束优 化线搜索方法相结合 都得到了不错的计算效果 注意到非单调的线搜索方法在实际计算中获得的很好的结果 邓乃扬等i 妁l 在1 9 9 3 年首次将文献f 10 1 中提及的非单凋技巧引入信赖域方法 并提出了一个 针对无约束非线性优化问题的非单调信赖域方法 此后非单调技术在倍赖域方法 中的使用得到广泛关注 如文献 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 具体而言 非单调技术在算法1 2 i 中的体现主要表现在将实际下降量的公式 1 2 3 改变 形式为 a r e d k j 女 一 钆 d k 6 对应文献 1 0 提出的非单调线搜索技术 则有 五 2 m j a x k z k j 七 o 1 2 1 3 1 其中 m o 0 当k 1 时 0sm k sm i n m k 一1 1 m m 为给定非负 整数 1 4 本文的创新点 由于初始信赖域半径的大小会影响算法的效率 但并没有一般的规则来指导 我们如何选取它 传统信赖域半径的确定方式没有利用目标函数在当前迭代点的 梯度和h e s s i a n 矩阵的信息 自动确定信赖域半径的自适应信赖域算法开始得到 关注 如文献 1 1 6 1 7 2 5 2 6 2 7 等 数值试验表明该类算法是有效的 本文研究将非单调技术引入自适应信赖域算法得到新的信赖域算法的全局 收敛性 并用数值试验来验证该算法的有效性 在第二章中 针对无约束非线性最优化问题 1 1 4 将李改弟 1 1 提出的自动 确定信赖域半径的信赖域算法采用张菊亮等f 16 提出的非单调线搜索技术 得到 个新的非单调自动确定信赖域半径的信赖域算法 研究了该算法的全局收敛性 在第三章中 将文献 1 中自适应技术与张洪超等 18 1 提出的非单调线搜索 技术相结合 在莫降涛等 1 9 1 给出的非单凋信赖域算法的基础上提出另一种新的 非单调自动确定信赖域半径的信赖域算法 并研究了新算法的全局收敛性 在第二章和第三章中 我们都做了适量的数值试验 其中的测试函数均出自 文献 28 7 2 非单调自动确定信赖域半径的信赖域算法之一 本章针对无约束非线性最优化问题 1 1 4 将李改弟 1 l 提出的自动确 定信赖域半径的信赖域算法 采用张菊亮等1 1 6 提出的非单调线搜索技术 得到一个新的非单调自动确定信赖域半径的信赖域算法 研究了该算法的 全局收敛性 2 1 引言 考虑无约束非线性最优化问题 m i n z z f 矿 其中f 舻一r 1 为非线性函数 二次连续可微 2 1 1 在传统信赖域算法的实现过程中 信赖域半径 的选取与m b k 无关 因 此 在每一个迭代点x 当它离最优点较远时 我们不知道拟牛顿步一巧1 9 k 是 否可行 此时 尽管检验条件满足 我们却不能接受它 这种情况会影响算法的效 率由此 章祥荪等 2 5 l 提出了一个新的信赖域子问题 d m 舻i n 吼 d 露d 展d 8 t 1 i d l i 儿 2 1 2 此处a c l l g k i i 丽 其中0 c l 丽 l 露1 i i p 为一非负整数 这里用凋节 p 来代替传统信赖域方法中对信赖域半径a k 的调节 数值试验表明文献 2 5 中利 用这个信赖域子问题构造的自适应信赖域算法是有效的 李改弟l l l 借鉴文献 2 5 的思路 考虑到i 弧一1 i i l l d k 1 0 包含目标函数的二次信息 其中y k 一1 g k 一鲰一1 8 每次迭代 取a k i i d k t 一t 蚓i 从而提出了另一个自动确定信赖域半 径的信赖域算法 数值试验表明文献 1 中技术改进了文献 2 5 1 中自适应技术的 不足 提高了算法的效率 文献 1 2 5 考虑的都仅仅是单调下降情形的信赖域算法 即 x k x k 1 能否将非单调线搜索技术引入自适应类型信赖域算法以提高算法的效率呢 这一 想法得到关注 最近 张菊亮等1 1 6 在文献 2 5 1 中引入非单调技术 令 硒2 当要砷 一j o 1 2 2 1 3 其中 n k m i n n 硌 n 0 是一整常数 几乎同时 傅锦华等1 1 7 1 在文献1 2 5 中引入文献 1 0 提出的非单调技术 令 细2 g m 螂a x 肛一小后 o 1 2 2 1 4 其中 m o 0 当k 1 时 0sm k m i n m k 一1 1 m m 为给定非负 整数 文献 1 6 l7 中数值试验结果都表明将非单调技术引入自适应信赖域算法是 有效的 本章将文献 16 中提出的非单调技术引入文献 1 得到 个新的非单调 自动确定信赖域半径的信赖域算法 并研究其全局收敛性 数值结果显示该算法 是有效的 此外 本文与文献 1 6 1 7 的区别还在于求解信赖域子问题时方法不同 2 2 算法 算法2 2 1 步1 给定 1 舻 b 1 j p 对称 0 0 c o c 1 0 2 2 1 步4 计算 驴垃篙掣 耐2 s 嚣焉一l 叫 n 2m 伽 1 舛 p r e d k c k o 一吼 d k 步5 如果仇 c o 则 0 2 言c 2 a k c 2 i i 吼0 转步3 否则转步6 步6 z 1 x k d k c 2 i i d k l l l l l y k l l 其中鲰 g k 1 一鲰 a k l t 三淼 1 4 也 hn i fr 矧k c 训l 步7 修正风 1 步8 k k 1 转步2 说明 1 当n 0 时 算法2 2 1 即退化为单调情形的自动确定信赖域半径的信 赖域算法 2 算法2 2 1 中 步3 步5 步3 称为内循环 3 鼠为对h e s s i a n 近似的拟牛顿矩阵 由拟牛顿方程校正 2 3 全局收敛性 首先给出讨论算法2 2 1 所需的假设条件 1 0 假设h i a 对任意的x l 船 水甲 集l x 1 z 形l y x z 有界且目标 函数f x 在水平集l x t 上连续可微 b 矩阵序列 鼠 一致有界 即存在m 0 使得对v k 有i i 风i m 引理2 3 1 如果假设h 1 成立 则当k 2 时 在当前迭代点x k 有 p r c d k 赢 1 2 其中慨 0 鼠 i p k 是当前迭代点x k 到下一次迭代之间信赖域子问题被计算的 次数减去1 证明 当k 2 时 在当前迭代点乳处信赖域半径满足以下关系 乱 引 驯 d k l l l l i 蚓i 龆 因此 d k 一而1 丽玑是信赖域子问题 1 2 1 的一个可行解 从而 一p r e 如 蠢以 d b k d 女s9 孺女 毒b 矗 一志怕t i l 2 高舭t 一一去 1 2 而 2 一面巧1 面 1 2 引理2 3 1 获证 口 引理2 3 2 如果假设h 1 成立 则算法2 2 1 是适定的 即算法2 2 1 不会在 内循环内无限次循环 证明 反证法 假设算法2 2 1 在迭代点z k 处于步3 至步5 之间无限次循环 记七 i 是当前迭代点 处的循环指标 不妨令i 2 则有r k i 兰c o i 2 3 即 垆垃掣 s 从而 丝止盐喇曼地 堕型盟 白 江2m 2 31 pr e d k 一p r e d k 一1 7 1 1 另一万回 由 2 2 1 碉 i 钆 一f x k 毗 1l 一 1 以 坚2 c o 这与 2 3 1 矛盾 故假设不成立 引理2 3 2 获证 口 引理2 3 3 如果假设h 1 成立 k 为由算法2 2 1 产生序列 则 z c l x z v k 证明 当k 1 时 由l x 1 定义知 z 1 l x 1 显然成立 假设当ksm m 为任一正整数时 有x k l x 即f x k f x 1 k 1 2 m 则当k m 1 时 根据算法2 2 1 定义 厶 1 f 2 3 2 而z m m 从而有 f 结合 2 3 2 有 m 1 l 故 件l l x z 成 立 由数学归纳法可知 巩 cl x 1 v k 引理2 3 3 获证 口 引理2 3 4 如果假设h 1 成立 则 五 k 非增且收敛 证明 由算法2 2 1 定义 我们有 五 女 1 v k 2 3 3 分情况讨论如下 1 当 n 1 时 显然有 v 1 1 故n k m i n n 1 n 1 n k 1 m i n n 1 k 1 n 1 由五 定义可知 五 1 2 g m a x 1 卜 l j 婴 丘 一j 2m n l 1 一 的 墨蕊一 一j 踌 一j m n z 一 一 结合 2 3 3 有 f m 8 l j l 一j 1 2 当k a i c o p r e d k a i 面a c 石 即 风 f 一蓑 因此 五 伽 一器 2 3 6 由 2 3 6 及引理2 3 4 有p l k 一 o o k 一 o o 不妨假设p t k 2 1 又 l 一 o o k 一 o o 不妨假定l k 2 根据算法2 2 1 的定义 我们知道d l k 相应于下列子问题的解不可接受 枷m i n d 靠 d 6 l d t b t 的d 圳h d ls 黔制黜瑙舢 1 4 否则不会在内循环内进一步修正以得到a l k 也就是说 血 粤掣 白 2 3 7 一垂z k d f k 一 7 另一方面 根据算法2 2 1 的定义及 2 2 1 有 1 f 一c o j l b k l l m n a k f 纨i i 川6 训 从而 五 女 i 一铆 m k 这与 2 3 7 矛盾 定理2 2 5 获证 口 1 5 2 4 数值试验 本文对算法2 2 1 进行了数值试验 试验问题来自于m o r e g a r b o w 与h i l l s t r o m 2 8 1 中无约束优化的检验函数 我们采用了与文献 2 8 相同的编号顺序 信赖域子问题 1 2 1 采用n o c e d a l 与y u a n 2 9 1 中算法2 6 非精确求解 由此产 生的试探步d 满足 2 2 1 f 2 6 取b 为单位矩阵 鼠 由b f g s 公式来修正 即 b k 1 b k 甏一鬻 2 a 1 8 f k8 i d k 乳 这里8 k d k x k 1 一 y k g k 1 一鲰 此外 仅当醒 8 k 0 时利用公式 2 4 1 得到b k 1 当醒 8 k 0 时玩 l 鼠 这种处理方式同文献 2 6 算法2 2 1 的停机条件是i i g k l i 1 0 一 其它参数取值分别为c o 0 5 c l o 7 5 在采用文献 2 9 中算法2 6 求解信赖域子问题时取1 2 在算法2 2 1 中 单调情形即n 0 非单调情形取n n 其中n 为文献 2 8 中相应问题的维 数 具体数值结果详见表2 1 其中 1 与 n o n z l x 分别代表算法2 2 1 单调情 形与非单诃情形 n g n f 及 i t e r 分别对应目标函数的梯度函数被计算次数 目标函数被计算次数及迭代次数 编程采用m a t l a b 7 0 4 版本 从表2 1 中可以看到 本文的算法2 2 1 是有效的 特别是针对问题8 9 1 7 时 非单调技术的采用比较见效 说明 文献 1 中算法与算法2 2 1 的单调情形 即n 0 时 略有区别 根 据文献 1 中算法定义 当 k c o 时 令o 1 x k 缩小信赖域半径 同时记 k k 1 进入下一轮迭代 而在算法2 2 1 单调情形中 当 c o 时 缩小 信赖域半径 转步3 重解信赖域子问题 1 2 1 直到条件r k c o 满足且寸 才令 k k 1 很明显 两种情况分别对应的 n g n f 值虽然完全相同 但由于后 者在迭代过程中去掉了重复点列的计数 其得到的迭代次数必然少于前者对应的 迭代次数 因此 本章用算法2 2 1 的单调情形取代文献 1 1 中算法 在相同参数 取值的条件下与算法2 2 1 的非单调情形进行数值结果的比较是有意义的 1 6 1 阻b l e2 1 测试函数维数1 n g n f i t e r n o n z l x n g n f i t c r l3 2 9 3 9 2 9 2 8 3 5 2 8 26 5 3 5 9 5 35 3 5 7 5 3 33 8 9 8 8 9 8 42 2 6 2 3 0 9 2 6 22 2 8 2 5 0 2 2 8 53 4 3 5 3 4 33 9 4 3 3 9 66 2 1 3 1 2 12 0 2 9 2 0 79 6 9 8 0 6 98 1 8 8 8 i 85 9 2 1 1 3 9 23 5 3 9 3 5 93 1 2 4 1 4 3 1 2 49 3 1 0 0 9 3 1 02 3 1 5 4 3 13 0 4 2 3 0 l l4 4 1 5 8 4 13 2 4 5 3 2 1 41 4 1 3 3 1 5 9 1 3 31 5 3 1 7 6 1 5 3 1 54 5 4 6 4 5 44 1 4 8 4 1 1 62 1 7 2 0 1 71 7 2 0 1 7 1 74 1 3 0 1 6 1 1 3 06 9 8 0 6 9 3 非单调自动确定信赖域半径的信赖域算法之二 本章将文献f 1 j 中自适应技术与张洪超等 1 8 1 提出的非单凋线搜索技 术相结合 在莫降涛等1 19 l 的基础上提出另一种新的非单调自动确定信赖 域半径的信赖域算法 并研究了新算法的全局收敛性 3 1 引言 考虑无约束非线性最优化问题 m i n y x z 彤 其中 p r 1 为非线性函数 二次连续可镜 3 1 1 目前 被广泛扩展和应用的非单调策略都是来自g r i p p o 等i m 即找到步 长o l t 满足 k a k d s m a x z k 一 矽n k g d k e o 1 2 其中 口 0 1 m 0 0 当 21 时 0sm k m i n m k 一1 4 1 m m 为 给定非负整数 以表示搜索方向 数值结果表明这种非单调技术增加了找到全局最优解的可能性 并在坡度陡 的地方提高了收敛速度 但是 随着对该类非单调技术研究的不断深入和完善 该 类算法的不足逐渐明显 某些数值结果对预先给定的参数m 的依赖性很强 而 m 既没有明确规则确定 也有可能因其固定性造成计算的大量浪费并影响计算 效率 为增加非单调线搜索的灵活性 更合理地选取参考值的迭代序列 张洪超 1 8 等 1 8 i 提出了一种新的非单调线搜索技术 用一特殊的加权甲均值代替最大值 仅要求目标函数的连续平均值充分下降 即 其中 x 女 a k d k s x 卢a 吼t d k 1 2 g 戮 帆 葛 3 抛 q t 一 q 一 薹 仉 q 町一d q m i f 0 1 1 q 耳 1 1 数值结果显示该技术在某种程度 上优于上述提及的传统非单调技术 并开始得到关注 如文献 1 9 3 0 1 等 最近 莫降涛等 l 跏将此技术引入信赖域方法 得到一个新的非单凋信赖 域算法 数值结果表明基于文献 1 8 1 的非单调信赖域算法是有效的 本文将文献 1 8 中非单调技术引入文献 l 1 中 在文献 l9 的基础上提出一种新的非单凋自 动确定信赖域半径的信赖域算法 并证明了新算法的全局收敛性 数值结果显示 该算法是有效的 3 2 算法 算法3 2 1 步1 给定z 1 舻 b l 舻 对称 e20 0 c o c l 0 3 21 丝p r e d k 镓等等 3 z 2 5 西 o 一西 比 7 1 9 步5 如果 s 匈 则 o z c 2 a k c 2 恢0 转步3 否则转步6 步6 x k 1 2 k d k c 2 i i d k l l l l y k l l 其中玑 g k 1 一玑 fm a x c 2 1 1 9 k 1 4 d k l l i 仉 c l a k l3 c 2 l l m l i i t r k c o c 1 步7 修正风 1 选择玑 q 饥 l t i k q k 1 g 1 7 1 q k c k z k 1 q k 1 步8 k k 1 转步2 说明 1 当啦 0 对一切k 成立时 该算法3 2 1 即退化为单调情形的自动确定 信赖域半径的信赖域算法 当讯 0 对某个 成立时 则伉 l z k 1 那么 在第 1 步就是 个单调下降 2 算法3 2 1 中 步3 步5 步3 称为内循环 3 取由拟牛顿方程校正 3 3 全局收敛性 首先给出讨论算法3 2 1 所需的假设条件 假设h 2 a 对任意的巩 形 水甲 集l x 1 z j p i z f x 1 有界 b 在水甲集l x 1 扛 t v l f z f x 1 内 目标函数的梯度函数g x 满足l i p s c h i t z 条件 即存在常数l 0 满足 i i g x 一9 l l l l l x 一 0 vz l x 1 c 矩阵序列 玩 一致有界 即存在m 0 使得对讥 有f l 取1 1 m 引理3 3 1 设 k 为由算法3 2 1 产生序列 则对一切 有 k 1s c k 1s e k 2 0 3 3 1 证明 由算法3 2 1 对一切k 有 c k f z k 1 两 五而 印 从而 由 3 2 1 可知 以一f z k 1 c o s h g k l l m i n a k 玑 i 风盼 即 z 1 sg c o g k m i n a k i j 玑 i 凤盼 3 3 2 由 3 1 2 3 1 3 3 3 2 有 从而有 k l y k q k c k 1 l q k l 印pr e d k 这显然与 3 3 7 矛盾 故假设不成立 引理3 3 2 获证 口 引理3 3 3 如果假设h 2 成立 z 女 为由算法3 2 1 产生序列 则 c l z 1 v k 证明 由引理3 3 1 及c 1 x 可知 对任意k 有 x k g 仉一1 c 1 z 1 从而引理3 3 3 获证 口 引理3 3 4 如果假设h 2 成立 钆 为由算法3 2 1 产生序列 则 g 收敛 证明 由假设h 2 a 引理3 3 3 及 连续可知 有下界 再由引理3 3 1 1 g l 冬g k 对一切k 成立 可知 g 收筑口 定理3 3 5 如果假设h 2 成立 则当 0 时算法3 2 1 有限终止或者产生一 个无限序列 鲰 满足 i l i r a i n f l l g k l 0 3 3 8 证明 不妨设算法3 2 1 不能有限终止 则当 3 3 8 不成立时 存在一个正常 数e o 有 乳0 e 0 v k 3 3 9 由 3 3 3 3 3 9 有 瓯 l g 一 c o s g k l l m i n 了a k i l g k h 一l l b l l t o k l 由引理3 3 4 知 q 收敛 从而有 g 一 c o g o j m i 飞n a i k g o l l b l l l i 墨堕垮剑耻 o 3 洲 一 q k l 2 3 由 3 1 3 及 k f 胁 町 1 7 h m 0 1 1 哺 7 m 1 1 q 女 1 1 4 l l k q k 1 o k 1 i 啦一l q 一1 1 仉 讯讯一1 q k 一1 1 仉 仉吼一1 1 讯一2 q k 一2 1 仉 仉讯一l 啦辄一l 讯一2 q k 一2 矗一lj 一1o o 1 t k i 1 j o 磁s j o f 1 j o i 0 磊 n 结合 3 3 1 0 及假设h 2 c 可知 扣l i m 阻5o 另一方面 3 3 i i 敏 呶 一f x k 1 9 x k t d k 一鲰 7 比出 露如 3 3 r 1 2 j o 根据假设h 2 b c 3 3 1 1 3 3 1 2 及f i d k l i a k 有 l 八z 一 z k a k 一 9 u j 一伞后 d k l l 一 z 一 巩 蠢矗 耀瓯磊i i2 1 b e d t 一 0 1 9 z t 以 一9 t t d k d ti s l a r k b k d k i 0 1 b 吼 媳 一鲰j 7 噍以 1 1 s m i l d k i l 2 ib z k d 女 一9 k 7 d k d t 1 1 1 d 洲2 z 1i i g x k t d k 一9 洲1 1 d e i i 出 2 1 1 2 l t l l d 女1 1 2 出 胁1 1 2 结合 3 2 1 3 3 9 3 3 1 1 及假设h 2 c 可知 l 笔黼刈s 丽 叫 一删 2 4 r d d i i e 讹 弛吣 一 c o 由算法3 2 1 定义及假设 h 2 c 此时 m 丽i l d k l lj 吼 z 怆i 丽l g k l l l 面6 0 这显然与f 3 3 1 1 矛盾 定理3 3 5 获证 口 3 4 数值试验 本文对算法3 2 1 进行了数值试验 比较了算法3 2 1 对应的单凋情形 即 取讯i0 时 与非单调情形的数值结果 同时与文献 1 9 中非单凋一般信赖域 算法进行了比较 试验问题来自于m o r e g a r b o w 与h i l l s t r o m 弱 中无约束优化 的检验函数 我们采用了与文献 2 8 相同的编号顺序 信赖域子问题 1 2 1 均 采用n o c e d a l 与y u a ni 删中算法2 6 非精确求解 由此产生的试探步以满足 3 2 1 1 2 6 取b 1 为单位矩阵 b k 由b f g s 公式来修正 即 b k l 玩 鞣一鬻 协蚰 这里8 d k z 1 x 女 y k g k l g k 此外 仅当靠8 k 0 时利用公式 3 4 1 得多j 鼠 1 当壤 8 k 0 时b k l b k 这种处理方式同文献f 2 6 算法的停机条件均为i 肌i i 1 0 算法3 2 1 与文献 1 9 1 中算法的非单调 情形均取讯 o 8 5 在采用文献 2 9 i 中算法2 6 求解信赖域予问题时 取7 2 算法3 2 1 中其它参数取值分别为c o 0 5 c 1 o 7 5 文献 1 9 中确定信赖域半 径的其它参数取常用数值 参见文献 5 具体数值结果详见表3 1 其中 l x n o n m x 与 l l o i i i l l l x 分别代表算 法3 2 1 中单调情形 文献 1 9 中非单调一般信赖域算法及算法3 2 1 非单调情 形 n g n p 及 i t e r 分别对应目标函数的梯度函数被计算次数 目标函数 被计算次数及迭代次数 一 表示迭代次数超过1 0 0 0 次仍未有结果 编程采用 m a t l a b 7 0 4 版本 从表3 1 中可以看到 算法3 2 1 是有效的 特别是针对问题8 9 1 7 时 非单 调技术与自适应技术的同时采用比较见效 1 陆b k3 1 测试函数维数 i n g n f i t 盯 n o n n x n g n f i t e r n o n m l x n g n f i t c r 13 2 9 3 9 2 94 6 5 2 5 23 3 3 9 3 3 26 5 3 5 9 5 31 8 9 1 9 2 1 9 25 3 5 6 5 3 33 8 9 8 5 7 78 9 8 42 2 6 2 3 0 9 2 6 2 2 3 3 2 4 8 2 3 3 53 4 3 5 3 4 33 8 4 1 4 13 9 4 3 3 9 6 6 2 1 3 1 2 11 9 2 9 2 92 0 2 9 2 0 7 9 6 9 8 0 6 9 1 1 5 1 2 1 1 2 1 8 1 8 8 8 1 85 9 2 1 1 3 9 22 3 1 2 4 1 2 4 13 5 3 9 3 5 9 4 3 8 3 4 4 3 3 8 33 1 4 3 2 3 3 2 32 4 6 2 5 1 2 4 6 l o2 3 1 5 4 3 1一 一 一3 0 4 2 3 0 1 l4 4 1 5 8 4 13 0 4 1 4 13 5 4 9 3 5 1 42 5 6 7 5 7 9 6 2 7 5 78 4 5 8 5 7 8 5 76 9 1 8 8 7 6 9 1 1 52 5 6 5 4 6 7 2 3 5 4 68 5 6 8 6 9 8 6 95 1 9 6 2 8 5 1 9 1 62 1 7 2 0 1 71 6 1 9 1 91 7 2 0 1 7 1 74 1 3 0 1 6 1 1 3 01 3 2 1 4 2 1 4 26 6 7 4 6 6 说明 1 出于第二章最后说明部分的同样原因 本章用算法3 2 1 的单调情形取代 文献 1 中算法 进行了数值结果的比较 这种处理方式是有意义的 2 为了更客观的将本文算法3 2 1 与文献f 1 9 1 中算法进行比较 我们进 行了另一组试验 将两种算法的各项参数取值尽可能与文献 1 9 保持一致 即 y 1 1 0 初始矩阵b l i i i j 其中j 为单位矩阵 初始信赖域半径 l 0 5 两种算法的停机条件都取定为i i 1 0 一 仉io 8 5 算法3 2 1 中其 它参数仍取为c o 0 5 c 1 0 7 5 文献 1 9 中确定信赖域半径的其它参数仍取常 用数值 参见文献 5 具体数值结果见表3 2 从表3 2 各项数据可以很明显的 看到 自适应技术的引入对文献 1 9 中算法的改进效果确实比较明显 t a b l e3 2 测试函数维数 n o n m x n g n f i t c r n o n m l x n g n f i t e r l 3 3 6 3 6 3 6 3 6 3 6 3 6 26 8 9 9 0 9 03 4 3 7 3 4 33 1 4 2 1 2 11 7 2 2 1 7 4 2 一 一 一 2 5 7 2 8 4 2 5 7 5 3 9 5 9 5 9 5 7 0 7 3 7 0 6 6 1 8 1 8 1 81 8 1 8 1 8 79 1 6 9 1 7 1 1 7 19 3 9 9 9 3 8 5 1 5 8 1 6 1 1 6 11 0 2 1 0 2 1 0 2 94 4 7 2 4 7 9 4 7 93 8 6 4 1 6 3 8 6 l o2 一 一 一1 4 1 4 1 4 1 14 i 1 7 1 1 7 i 1 74 9 4 9 4 9 1 45 1 2 1 1 2 1 1 2 1 1 25 9 6 0 5 9 1 51 2 8 1 0 1 1 0 1 1 0 16 9 6 9 6 9 1 62 1 8 1 8 1 81 7 1 7 1 7 1 74 4 4 4 4 4 4 4 3 4 3 4 3 4 参考文献 李改弟 一个自动确定信赖域半径的信赖域方法闭 工程数学学报 2 0 0 6 2 3 5 8 4 3 8 4 8 f 2 席少霖 非线性最优化方法f 田 高等教育出版社 1 9 9 2 f 3 袁亚湘 孙文瑜 最优化理论与方法f 田 科学出版社 1 9 9 7 4 袁亚湘 非线性规划数值方法 m j 上海科技出版社 1 9 9 3 f 5 j 袁亚湘 信赖域方法的收敛性 j 计算数学 1 9 9 4 3 3 3 3 3 4 6 f 6 jm j d p o w e r o nt h eg l o b a lc o n v e r g e n c eo ft r u s tr e g i o na l g o r i t h m sf 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 m a t h p r o g 1 9 8 4 2 9 2 9 7 3 0 3 7 jr f l e t c h e r am o d e la l g o r i t h mf o rc o m p o s i t en d o p r o b l c m m a t h p r o p s t u d y 1 9 8 2 a 1 7 6 7 7 6 8 r f l e t c h e r p r a c t i c mm e t h o d so fo p t i m i z a t i o n s c c o n de d i t i o n j o h nw i l e va n d s o n s c h i c h e s t e r 1 9 8 7 9 j j m o t 6 r e c e a td e v e l o p m e n t si na l g o r i t h m sa n ds o f t w a r ef o rt r u s tr e g i o nm c t h o d s i n a b a c h e m m g r 6 t s c h e la n db k o r t e e d s m a t h p r o g t h es t a t eo f t h ea r t s p z i n g e r v e r l a g b e r l i n 1 9 8 3 2 5 8 2 8 7 1 0 l l g r i p p f l a m p a r i e u o s l u c i d i an o n m o n t o n el i n e s e a r c ht e 出n i q u ef o fn c w t o n sm e t h o d j j s i a m j o nn u m e r i c a l a n a l y s i s 1 9 8 6 2 3 7 0 7 7 1 6 1 l j l g r i p p o f l a m p a r i e u o s l u c i d i at r u n c a t e dn e w t o nm c t h o dw i t hn o n m o n 0 t o n el i n es e a r c hf 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 j o p t i m t h e o 彤a