（应用数学专业论文）非线性优化问题的一类非拟牛顿算法研究.pdf

摘要 对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方 向之一 文 2 8 基于校正的非拟牛顿方程 给出了无约束优化的一类非拟牛顿算 法 本文结合文 2 8 中的非拟牛顿法 给出了求解无约束非线性优化问题的一类 具有超线性收敛的非拟牛顿算法 在第一章我们首先简要的介绍了最优化问题的提出以及判断最优解常用的 最优性条件 回顾了无约束优化问题常用的几类导数下降类算法 在第二章中 就非拟牛顿族在无约束最优化问题上 采用非单调线搜索下是 否具有全局收敛性进行了研究 在目标函数满足一致凸的条件下 证明了非拟牛 顿族是全局收敛的 在第三章中 就非拟n e w t o n 族在无约束最优化问题上 采用非精确线搜索 下是否具有全局收敛性进行了研究 文中提出了一种非拟n e w t o n 族校正 并证 明在目标函数满足梯度l i p s c h i t z 连续的条件下 此校正在w o l f e 或a r m i j o 线 搜索下具有全局收敛性 关键词 非拟n e w t o n 族 非精确线性搜索 无约束最优化 全局收敛 超线性 收敛 a b s t r a c t s e e k i n g f a s tt h e o r e t i c a lc o n v e r g e n c ea n de f f e c t i v ea l g o r i t h m si nu n c o n s t r a i n e d o p t i m i z a t i o ni s av e r yi n t e r e s t e dr e s e a r c ht o p i cf o rt h eo p t i m i z a t i o ns p e c i a l i s t s a n de n g i n e e r s p a p e r 2 8 g i v e sac l a s so fn o n q u a s i n e w t o na l g o r i t h m sa b o u t u n c o n s t r a i n e dp r o g r a m m i n gp r o b l e m sb a s e do nt h em o d i f i e dn o n q u a s i n e w t o n e q u a t i o n i nt h i sp a p e r w eg i v eac l a s so fs u p e r l i n e a r l yc o n v e n g e n ta l g o r i t h m s f o rn o n l i n e a r p r o g r a m m i n gp r o b l e m s w i t hu n c o n s t r a i n e db yc o m b i n i n gn o n q u a s i n e w t o nm e t h o d s 2 8 1w i t hs o m ei n e x a c tl i n es e a r c h e s i nc h a p t e r1 w ef i r s ti n t r o d u c et h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m e e x t e n s i v eo p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u m s o l u t i o n w er e v i e w s e v e r a le x t e n s i v ed e r i v a t i v ed e s c e n tm e t h o d so fu n c o n s t r a i n e dp r o g r a m m i n g i nc h a p t e r2 t h en o n q u a s i n e w t o n sf a m i l yi sc o n c e r n e dw i t ht h ep r o b l e m o fw h e t h e rt h em e t h o dw i t hi n e x a c tl i n es e a r c hc o n v e r g e sg l o b a l l yw h e na p p l i e d t ou n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s w ep r o p o s e au p d a t ea n dp r o v et h a tt h e m e t h o dw i t he i t h e raw o l f e t y p eo ra na r m i j o t y p e l i n es e a r c hc o n v e r g e sg l o b a l l y i ft h ef u n c t i o nt ob em i n i m i z e dh a sl i p s c h i t zc o n t i n u o u sg r a d i e n t s i nc h a p t e r3 t h en o n q u a s i n e w t o nm e t h o d s f 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 i si n v e s t i g a t e d n o n m o n o t o n el i n es e a r c hp r o c e d u r ei si n t r o d u c e d w h i c hi sc o m b i n e dw i t ht h en o n q u a s i n e w t o nf a m i l y u n d e rt h eu n i f o r m l yc o n v e x i t ya s s u m p t i o no no b j e c t i v ef u n c t i o n t h eg l o b a lc o n v e r g e n c eo ft h eq u a s i n e w t o nf a m i l yi s p r o v e d k e yw o r d s n o n q u a s i n e w t o n sf a m i l y i n e x a c t l i n es e a r c h u n c o n s t r a i n e do p t i m i z a t i o n g l o b a lc o n v e r g e n c e s u p e r l i n e a rc o n v e r g e n c e 1 1 1 非线性优化问题简介 这一章里 我们简要介绍最优化问题的提出以及判断最优解常用的最 优性条件 在第二节总结了无约束优化问题常用的线搜索和几类导数下降 类算法 重点是拟牛顿算法及文 2 8 提出的非拟牛顿算法 在最后一节 介绍了我们提出新算法的主要思想 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科 虽然最优化可以追溯到十 分古老的极值阅题 但壹到1 9 4 7 年d a m t z i g 提出 般线性规划问题的单纯形法 之后 它才成为 r l 独立的学科 随着现代科技的发展和计算机的广泛应用 进 一步推动了最优化理论和算法的研究 今天 最优化理论与方法在经济规划 政 府决策 生产管理 交通运输和军事国防等方面得到了广泛的应用 成为一门十 分活跃的学科 一般来说 最优化问题可归结为求解如下的极小值问题 m 锄i n 他 1 1 1 其中 z d 是决策变量 f x 为目标函数 d j p 为可行域 根据变量的类型 最优化问题可分为连续型最优亿和离散型最优化 也称组 合优化 连续型最优化问题又可分为目标函数和约束函数均为线性时的线性规 划问题 以及目标函数和约束函数中至少有一个为非线性时的非线性优化问题 又根据可行域d 的类型 非线性优化问题可分为约束优化和无约束优化问题 首都师范大学硕士学位论文t 非线性优化问题的一类非拟牛顿算法研究 一般优化约束优化问题通常可描述为 m i n z z 舻 7 s t c f 扛 0 i 1 2 一 m q 茁 0 i m 1 m 2 一 n 本文主要研究无约束最优化问题 即 1 砌m i n z 其中f r r 为非线性连续函数 下面我们给出全局最优解和局部最优解的定义 1 1 2 1 1 3 1 1 4 115 定义1 1 若 冗n 具有性质 v x r n 均有f x z 则称z 为问 题 1 1 1 的全局最优解 定义1 2 若矿 r 具有性质 存在矿的某个邻域批 z zil i x 一茁 0 为某个正数 使得v x 肌 z 均有f x f x 则称 为问 题 1 1 1 的一个局部最优解 当目标函数 z 是凸函数时 局部最优解就是全局最优解 但在一般情形 下找出全局最优解非常困难 通常在非线性优化中我们认为局部最优解即为所求 的解 在实际的算法中 我们通常是找出满足局部最优解的必要条件的点 若记 9 x v f x 表示f x 的梯度 c x v 2 f x 表示f x 的h e s s i a n 矩阵 下面我们给出这些必要条件 则 引理1 1 3 6 无约束优化一阶必要条件 若矿为问题 1 1 5 的一个局部最优解 且在矿的某个邻域内f x c 1 g x 0 引理1 2 3 6 1 无约束优化二阶必要条件 2 1 1 6 第1 章非线性优化问题简介 则 若z 为问题 1 1 5 的一个局部最优解 且在z 的某个邻域内f z c 2 g x 0 a x 0 1 2 无约束优化的导数下降类算法 导数下降类算法是求解无约束问题 1 1 7 础r a i n m 1 2 1 常用的一类算法 它的基本思想是t 对于已有的迭代点x 首先确定一个搜索方 向如 使得目标函数f x 的值沿该方向是下降的 然后确定沿呶方向行进的 步长h 并得到下一个迭代点x k 1 x a k d t 在这里 我们要确定的搜索方向应满足 v f x k t d k 0 1 2 2 以使 扛 在x k 点沿靠方向下降 为了行文的方便 在介绍线搜索和导数下降类算法之前 约定记号如下 z i g k g x k v 0 七 y k g k 1 9 七 8 k x k 1 一z 七 a 七d l 下面我们介绍线搜索 确定k 的过程就是线搜索 也称一维搜索 精确的线搜索就是在出方向 上寻求 最优 的行进距离 使得 z k 九血 2 咖 z k a d k 1 2 3 非精确线搜索不要求上式成立 而仅要求找到的h 能使目标函数在某种意义上 达到令人满意的下降 常用的非精确线搜索如w o l f e 线搜索和a r m i j o 线搜索 本文正是采用这两种线搜索 现介绍如下 3 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 w o l f e 线性搜索 1 j z 女 a k d k f x k a a k g z k v d k d 0 g k a k 毗 r d k 三p 9 z t d p o i 记 a a 以 则 7 o 0 且w o l f e 条件可化为 1 a f o a x f o 口 0 i a l 一卢 7 o 卢 盯 f 1 2 4 1 2 5 设直线 a 仃总o o 与f 7 的交点为 x 7 其中7 为一下界使 m 脚例页 锵 于是 w o l f e 算法 l 叫 a 戈 界算法 i n i t i a l 令a o 0 给定a l o f o k 口 o 或 似女 一1 则令 k 一1 b k 儿 划界过程终止 否则作3 3 计算 k 若i f k i 一卢 o 则接受k 定步长过程结束 否则作 4 4 若f k 0 则令鲰 k 圾 a 女 i i 魁界过程结束 否则作5 5 若is2 k h l 则令a 女 l i 否则令 t l 2 k a k l m i n x a n k h 一1 并令k k 1 转1 b 分割算法 i n i t i a l 给出屯与乃 令j 毛 1 选取 a j 记 一 b 一乃 b q 1 2 计算 若 f o a j a f o 或f a j f a j 则令 升l 幻 l 转5 否则作3 3 计算 若1 i 茎一口 o 则接受 迭代过程结束 否则作4 4 令a j 1 如 若 b a j f 0 因而不能保证校正矩阵风是正定的 因此 本文提 出一种阈值的方法 从而证明陈兰平提出的非拟牛顿算法是可以应用在a r m i j o 线搜索情况上的 另外 应用导数下降类算法处理无约束最优化问题时 采用非 单调线搜索所得到的效果也颇具意义 因此 本文将非拟牛顿算法与非单调线搜 索相结合 进行研究 在第二章中 就非拟牛顿族在无约束最优化问题上 采用非单调线搜索下是 否具有全局收敛性进行了研究 在目标函数满足一致凸的条件下 证明了非拟牛 顿族是全局收敛的 在第三章中 就非拟n e w t o n 族在无约束最优化问题上 采用非精确线搜索 下是否具有全局收敛性进行了研究 文中提出了一种非拟n e w t o n 族校正 并证 明在目标函数满足梯度l i p s e h i t z 连续的条件下 此校正在w o l f e 或a r m i j o 线 搜索下具有全局收敛性 在第二章和第三章中 我们都做了适量的数值实验 其中的测试函数均出 自 1 0 为了引用的方便 我们按测试函数在文献中出现的次序编号 并为每一 个测试函数重新命名 这样也是为了行文的方便 其命名如t a b l e1 所示 对于 每一个函数 我们都用c 语言编写了代码 为后文的第二 三章的数值实验做 了准备 9 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 i n d e xp r o b l e mt h en a m eo ft e s tf u n c t i o n 0 1r d s er o s e n b r o k ef u n c t i o n 0 2n o t hf r e u d e n s t e i na n dr o t hf u n c t i o n 0 3 b a d s c p p o w e l lb a d l ys c a l e df u a c t i o n 0 4b a d s c bb r o w nb a d l ys c a l e df u n c t i o n 0 5b e a l eb e a l ef u n c t i o n 0 6j e n s a mj e n n r i c ha n ds a m p s o nf u n c t i o n 0 7h e l i xh e l i c a lv a l l e yf u a c t i o n 0 8b a r db a x df u n c t i o n 0 9g a u s sg a u s s i a nf u n c t i o n 1 0m e y e r m e y e rf u n c t i o n l lg u l fg u l fr e s e a r c ha n dd e v e l o p m e n tf u n c t i o n 1 2b o xb o xt h r e e d i m e n s i o n a lf u a c t i o n 1 3 s i n g p o w e l ls i n g u l a rf u a c t i o n 1 4 b o d b o df u n c t i o n 1 5k o w o s bk o w a l i ka n do s b o r n ef u n c t i o n 1 6b db t o w na n dd e n n i sf u n c t i o n 1 7o s b lo s b o r n e1f u n c t i o n 1 8 b i g g sb i g g se x p 6 f u n c t i o n 1 9o s b 2o s b o r n e2f u n c t i o n 2 0w t o nw t o nf u n c t i o n 2 1r o s e x e x t e n d e dr o s e n b r o c k 2 2 s i n g x e x t e n d e dp o w e l ls i n g u l a rf u n c t i o n 2 3p e n l p e n a l t yf u n c t i o n1 2 4p e n 2p e n a l t vf u n c t i o n2 2 5v a r d i mv 打i a b l ed i m e n s i o n e df u n c t i o n 2 6 n i gt r i g o n o m e t r i cf u n c t i o n 2 7l i n ab r o w na l m o s t f i n e a rf u n c t i o n 2 8b vd i s c r e t eb o u n d a r yv a l u ef u n c t i o n 2 9i ed i s c r e t ei n t e g r a le q u a t i o nf u n c t i o n 3 0t r i d b r o y d e nt r i d i a g o n a lf u n c t i o n 3 1b a n d b r o y d e nb a n d e df u n c t i o n 3 2l i nl i n e a rf u n c t i o n f u i ir a n k 3 3l i n ll i n e a rf u n c t i o n r a n k1 3 4l i n 0l i n e a rf u n c t i o n r a n k1w i t hz e r oc o l u m n sa n dr o w s 3 6r o t h xe x t e n d e df r e u d e n s t e i na n dr o t h 3 7w j o d xe x t e n d e dw o o df u n c t i o n 1 0 2 基于非单调线搜索非拟牛顿法的全局收敛性 在这一章中 就非拟牛顿族在无约束最优化问题上 在采用非单调线 搜索的情况下是否具有全局收敛性进行了研究 在目标函数满足一致凸的 条件下 证明了非拟牛顿族是全局收敛的 2 1 引言 考虑下列非线性规划问题 r a i n z 其中 r r 1 c 2 一般解决 2 1 1 线性方法具有如下格式 z 女 l x k a 女如 k 0 1 2 2 1 1 其中黝是任意给定的初始点 k 是一步长 也是一搜索方向 我们已经知道 拟牛顿法是非常有效的迭代方法 有许多文章已经从事b r o y d e n 类算法特征的 研究工作 3 5 8 1 4 1 5 t1 6 1 7 2o 2 5 与此同时 对非拟牛顿族特征的研究也 有所进展 2 1 2 8 t3 0 1 本章正是对这一研究领域的继续 非拟牛顿法的搜索方向 由下列方程组决定 d k 一风玑 鲰 v f x k 其中凰是任意给定的扎 n 对称正定矩阵 上如 露1 h e s s i a n 矩阵的近似矩 阵b 的校正公式如下 3 0 j 驯 t b k 一鬻 器瓣协k 曙 2 m 1 1 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 其中 是一个数值 f x k y k g k 1 一g k 8 k z 1 一z a k d 和 s 吾g 女乳z t a g 吾s 垒r 女 s g 胁 吾s k q k t t y t s k 2 1 一t r k t 0 1 k s 跏t 旦y s k 一霉b 砜k s k 当对所有 怕 l 0 时 由于参数的选择大大地影响该类算法的实施 因此参数的选择是非常重要的 由 2 1 2 当t l 或0 时 我们可得b r o y d e n 类 算法或伪n e w t o n b 算法 众所周知 若初始近似矩阵b o 是对称正定的 及对于所有的k 满足 暑乳 0 及 妒 三去胁 s t b 丽k s k i y 矿t h k y k 2 13 则对所有的b k 均保持对称正定 1 3 1 p o w e l l 3 1 已经证明b f g s 方法对于凸函数是全局收敛的 b y r d n o c e d a l 和 y u a n 1 5 1 将其结果推广到 o 1 对于凸函数 z h a n g 和t e w a r s o n 1 4 1 证 明当帆 1 一y 嫒 0 时b r o y d e n 族具有全局收敛性 其中 是一个 0 i 的 数值 对于一致凸函数 b y r d l i u 和n o c e d a l 1 7 1 证明当b r o y d e n 族满足 妒 1 一p 妒 1 一叫 5 l 0 1 2 1 4 时具有全局收敛性 对菲拟牛顿族 也进行了与以上类似的研究工作 参见f 2 8 3 0 1 近些年来 基于非单调算法的b r o y d e n 类校正也有所研究 2 4 2 7 3 2 1 事 实上 许多数值实验已经证明了在某些情况 非单调类算法要比单调类算法更加 有效 1 1 2 3 1 2 7 1 因此 在 2 1 4 条 牛 v 我们引进基于非单调线搜索的非拟牛 顿族并分析其收敛性 我们将用到如下非单调线搜索 我们称其为n m 线搜索 1 2 第2 章基于非单调线搜索非拟牛顿法的全局收敛性 n m 一线搜索 选择步长并满足 m 川 s 蛳m a x f z t 一 e l 儿豇血 2 l5 g x i 1 t d k m a x e 2 1 一 a e i i d k ll 9 9 t d 女 2 1 6 其中e o e 2 1 1 p 一 1 及 是一个非负整数 这个线性搜索 框架最初援引g r i p p o 于1 9 8 6 发表的文章 1 基于此想法的步长的选择应该 尽可能的宽松 它是由线性搜索 2 1 6 推广出来的曲率条件 算法1 1 1 给定初始值0 e 1 e 2 1 p l k 1 m o 是一个非负整数 t z k f 9 吾也 1 i p l 3 一九露以 2 1 8 o m 七 t e r 叫i s e 及 纵 型毫赫型 z 1 9 和集合 p k m o o c p 1 k 融 t 2 1 1 0 若觎2e 1 则转到4 3 利用f s 和 进行严格二次内插计算爻 并设k 爻 并转到2 4 计算g 9 z 札d k 和 g t d 如果 g x k a e 血 t 呔2m i k x 2 1 一 扎j j 呔j l 蠢呶 2 1 1 1 则停止 否则 利用f l 一和f 进行严格二次外插计算天 并设 f 爿 f 及k 支 并转到2 1 3 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 注 我们定义 危 7 7 2 i f p p k 以p 1 k 2 11 2 我们称迭代 为第尼次迭代的参考迭代 上述非单调线搜索的框架是基于 1 1 和 3 2 修改而来的 很显然 当i o 0 p 0 时 这一特殊情况下的线搜索 就是对应于在理论和应用上常用的w o l f e 线搜索 在下一节里 我们将证明一些引理 它们将进一步证明第三节中的定理3 1 定理3 1 表明基于非单调线搜索非拟牛顿法具有全局收敛性 在第四节里 我们 将进一步给出一些数值结果 以说明该算法的可实施性 2 2 预备引理 首先我们先给出本章的条件假设 h 1 设水平集d x l f a z 是有界的 并且存在正常数m 和m 对 于所有的z r 及所有的z d 其中记g 为 的h e s s i a n 矩阵 满足 m l l zr 1 2 z r a x zsm l i z l l 2 2 2 1 和 2 靠8 k 0 k 1 2 从 h 我们可以很容易推到出存在两个正数m 和m 满足 m i l s k i l 2 瞻鼽 m i i s 女1 1 2 2 2 2 刊l s k i i q k t m 1 1 8 k 1 1 2 2 2 3 引理2 1 假设 h 保证成立 则存在一个正数m 满足 骅s m 是 1 2 i 2 t 2 4 蚝8 k 证明 我们若定义缸 g 乱 其中g i l i 1 g 则由 2 2 1 我们就有 孥 警 挚 v d e t 鼠 s q 凤k t 五 1 其中d e t b k 记为鼠的 行列式 证明 如果0 1 一d 从陈f 2 s l 我们就很容易得到 d e 邶 蚓剐 嘉器 2 2 脚 当m 0 时 式 2 2 6 就可写为 d e t b k l 0 d e 慨 0 嘉髌 2 2 7 下面我们再看 1 一 蝶 o l 0 1 的情况 由式 2 1 2 我们可得 b k l b k 1 o k 昭 2 2 8 因此我们就可得到 耋蒜d e t b k 徽t o i 耋麟瓣 删2 29 风 l o k 昭1 d e t 8 l o d e t j 妒k 日 l o k i 其中 0 即 繁警 器 2 加 由式 2 1 4 2 2 6 2 2 9 2 2 1 0 并注意到d e t i x y r 1 x r y 我们就 d e t b 1 雠 1 胁一1 如t 最 篡 娄1 d e t b k 攀 1 妒 p 一 l 础删箍 1 5 i o 2 2 1 1 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 这就完成了证明 引理2 4 如果f x k 1 h 女 0 1 当 t k d 对于所有的 0 则函数序列 z k 是单调下降的 证明 由 k z m l 我们可以得到 m 州 叫 一m a x 鲥 巧 s 觚 t m a x 臃k m j 1 m k 2 2 1 2 m a x f x h k 1 z k 2 z 女 1 女 1 2 即函数序列 扛 女 是单调下降的 既然f x h o f x o 我们就可以推导出 z 女 f x h 一 f x h 0 f x o x k d 引理2 5 假设步长k 是由算法1 1 确定的 则 o o 一方勺 一 z j z 第2 章 基于非单调线搜索非拟牛顿法的全局收敛性 利用递推 我们可以得到 z 女 cd 由假设 h 可知 z k 在d 是下方有界 的 再结合式 2 2 1 7 这就意味着 2 21 3 是正确的 引理2 6 假设序列 z 是由基于非单调线搜索且 满足 2 1 3 非拟牛顿 法的点列 其中步长k 是由算法1 1 给出的 则 l i m 蜂望 o陋1 8 y s k 一 1 m 卜a x e 2 e 2 恻1 嗍 a k 靠i l d k s k i m m t 9 腻s 2 舢 一 j e 2 i l l s l i 尸 9 i s k 7 兰群享面等而一t 鲁 淼 眨 抛 m a x 手里哮 一9 融 一 c o o 2 3 全局收敛性 这一节里 我们给出我们的主要结果 这一结果为基于非单调线搜索且妒女 满足 2 1 3 的非拟牛顿法建立了全局收敛性 1 7 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 定理3 1 假设 h 成立 并假设z o 是任意给定的初始点 玩是任意给定 的初始对称正定矩阵 若点列x k 是由基于非单调线搜索的 满足 2 1 3 的 非拟牛顿法的点列 其中步长a 是由算法1 1 给出的 则 打 b e t 妒一 打 日t 一i i b 且 k l l 2 里焉挚尝笋罡 妒圳k 酽 刮侧邓咱 糕 糍磐懒警糕啦 訾 筹 s i b k i i b 耶 k l 1 2 m 器 m 黠 2 s t 4 i 醛b k s k 川鼠 ij 2 j l y k l l s b 凳磊兰絮 皿3 5 河 塞星监 一何 量墼 卜 7 一 怕吾 i 风s t 怕手s 翮弧0 由引理2 1 引理2 2 引理2 5 及式 2 1 4 2 3 2 2 3 3 一 2 3 5 我们就可以 打 b k 9 剐一6 糕 m 2 3 6 对所有充分大七 k l 成立 不失一般性 我们可以假设 2 3 6 对所有的k k i 1 8 第2 章基于非单调线搜索非拟牛顿法的全局收敛性 2 七 2 由 2 33 的第一个不等式和引理22 我们可以得到 州驯妨 驴糕堋 2 3 7 这就意味着式 2 3 6 在此种情况也成立 因此 关系式 2 3 6 在以上两种情况下均成立 从而可以得到 紧芈 帆 七尬 i 两十8 1 2 其中尬 m 1 t r b o 式 2 3 6 意味着 d e t b k 1 曼 下t r b k o 和 妻糕 丁k m 2 懿坞 j 由几何一算术平均不等式 我们可以得到 垂鬻 埘 引理2 3 说明 措f i 磊q a t 裂 由式 2 3 2 2 3 9 一 2 3 1 2 我们可以得到 鱼斋 垂学 番 j 血 l 黔k j 燎j j 鱼精器 耥 丽y t s j 豁 m c 2 筹v k 0 是一个常数 以上的关系式与引理2 6 相矛盾 于是证明完毕 瓣 纠 6 础 c 0一 j c o打 0 且y 手s k o 则 由 3 2 4 式确定的矩阵风 正定的充要条件是 帆 妒 去 这表明 若 院 由b k 正定可保证b k 1 正定 下面引入一个重要的工具函数 定义1 1 6 设正定矩阵a 的特征根为a l a m a 函数定义为 皿 a t r a 一i n d e t a 一i n a j j l 第3 章无约束最优化同题的校正非拟牛顿算法及其收自 壁 其中t r a 记为a 的迹 d e t a 记为a 的行列式 本丈采用w o l f e 线性搜索 口 o j 1 3 2 5 p 1 与a r m i j o 线性搜索 其主要是找一个儿 使a k 为集合 睁 0 1 p 0 1 满足如下不等式 z t a k d k 盯a k g k 于d k o j 1 32 6 的最大值 对w o l f e 线性搜索显然满足掣 靠 0 而a r m i j o 线性搜索不能保证 谵8 k 0 为了保证 风 正定遗传性 我们定义 b k l t o k 瞰一鬻 器棘协k 昭 若m 面 b k 其它 7 1 瓦邓j 器到蚶i i 3 2 8 其中e 和口是正常数 算法1 给定任意初始点x 0 舻及n 阶初始对称正定矩阵岛 选择常数 a 0 e 0 e 0 令k 0 1 若l l se 终止 否则转2 2 解方程 3 2 2 求得以 3 由w o l f e 型或a r m i j o 型线性搜索确定步长k 0 4 令z k 1 z k 畋 5 b 1 由 3 2 7 确定 6 令k 1 转到1 以 严 麓 扣魏琏m也出加h 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 注1 从 32 7 不难看出矩阵最对v 后来说都是对称正定矩阵 若用 线性搜索 3 2 5 或 3 2 6 则产生的函数列 是下降列 若 有下界 由 3 25 3 2 6 可得一eo t s k 0 使得对v z r vz d m l f z f f 2 z r g 0 z s m f l z l r 2 a 2 函数 在集合d 上是连续可微的 且存在这样的一个l 0 满足 o x 一g y l l l l l x y i iv z y d 3 3 1 第3 章无约束最优化问题的校正非拟牛顿算法及其收敛性 既然 f x k 是一单调下降列 由算法i 产生的序列 x k 包含在d 中 由 a 1 易得 m m 一赢1 m 1 1 2 割 一z 雌m m s 等l l x x 1 1 2 首先给出下面的收敛性定理 3 3 2 3 3 3 定理3 1 设 z k 由算法1 产生的序列 若存在三个正数p 恳 风 0 满 足如下关系 1 i b k l s 历l 旧t 仍i l 乳1 1 2 s b a s t 卢3 l i s t i l 2 3 3 4 对无穷多个女均成立 则有 k l i m i n fl l g x k l l 0 3 35 证明 由于8 k k d k 若用呶代替 5 k 则 3 3 4 很显然成立 令k 为使 得 3 3 4 成立的所有指标七的集合 对于vk k 从 3 2 2 和 3 3 4 不难 推出 岛 d 七 i i i g z k l l 尻l l 出l l 3 3 6 考虑到用a r m i j o 型带参数p 的 回追搜索 情况 若k 1 贝日有 f x k p 1 a k d k 一f x k p 1 a a k g x k t d t 3 3 7 由中值定理 存在一个讯 0 1 满足 0 为g 的l i p s c h i t z 常数 将 3 3 8 代入 3 3 7 对vk k 有 a t 一生二二铲 史 铲 l 1 仍 一盯 p 2 7 嘲础嘞 凝 瑙托 澄 一 mm脚 钆n 叭 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 这就说明对vk k 有 a 女 r a i n 1 1 一c r p 2 l 1 p 0 3 3 9 考虑到用w o l f e 型线性搜索 3 2 5 的情况 由 3 2 5 的第二个不等式和g 的l i p s c h i t z 连续 有 l a k l l d k l l 2 k z a k d k 一乎 z t t d k 一 1 一p 岔 女 t d k 这就意味着 a 一 1 一卢 9 z k t 以 了瓜旷一一 1 矿f1 d暑kb k d k l 1 阮 1 口 3 3 1 0 3 3 9 和 3 3 1 0 说明 无论用到线性搜索 3 2 5 或 3 2 6 儿 耳均是不以 零为有界的 从 3 2 2 和 3 2 9 可得 d k b k d k 一蠢血 0 南 0 k k 3 31 1 由 3 3 1 1 3 3 4 及 3 3 6 可知 3 3 5 成立 本定理说明为证明算法1 具有全局收敛性 只需证明存在三个正数岛 岛 尻 满足对无穷多个k 使得 3 3 4 成立即可 引理3 2 3 0 1 假设a 1 a 2 成立 设 鼠 由迭代公式 3 2 7 产生 其中 b 1 对称正定 仇满足 1 一 妒 帆 o h 0 1 则对任意p 0 1 存 在正常数p l 岛 风使得对任意k l 在f 1 叫中至少有挑 个i 满足 吼 所 所岛sy i 兰风 岛 裂 譬 3 3 1 2 o l i lp l 下面用引理3 2 和定理3 1 为算法建立全局收敛性 定理3 3 女 由算法1 生成的点列 则 3 3 5 成立 证明 由定理3 1 可知 只需证明存在无限多个指标k 使 3 3 4 成立即可 若耳是有限集合 则 风 经过有限次迭代后是一个常矩阵 由于风是对 称正定矩阵的 很显然存在常数 反 岛 风 0 满足对充分大的k 满足 3 3 4 成立 2 8 第3 章无约柬最优化问趣的校正非拟牛顿算法及其收敛性 若霄是无限集 用反证法证明 假设 3 3 5 式不成立 也就是对v 七 k 存在一个常数6 0 使得1 1 9 k l 6 成立 由 3 2 7 有对v k k 满足 g k2e d s 1 1 2 由 3 1 意味着对vk k 有 i l y l 1 2 l 2 磊i 万 对矩阵序列应用引理3 2 很显然存在三个常数 卢1 阮 风 0 满足对无穷多个 k 使得 3 34 成立 定理3 3 说明存在一个序列f 收敛于 3 2 1 中的一个稳定点矿 若 是 一致凸的 则矿是 的全局最小点 既然函数列 是收敛的 很显然 女 的每一个聚点都是 3 2 1 的全局最优解 也就不难得 出如下结论 推论3 4 z 是由算法1 生成的点列 若 是一致凸 则 0 满足醒8 k 训 孵这就意味着当k 充分大时 条件 慧 l i g q l g k l l n 晒驴 是可以被满足的 即当女充分大时 由算法1 可以推导出一般的b r o y d e n 类算 法 首都师范大学硕士学位论文 非线性优化问题的一类非拟牛顿算法研究 为了讨论算法l 的超线性收敛性 我们给出如下补充假设 a 3 设 z 的h e s s i a n 矩阵g x 在x 处是l i p s c h i t z 连续的 即存在正 常数l 使得 1 1 g z 一g l l l l i x z 对z 的某邻域内所有x 成立 5i 埋3 6 t z 女 是由 鼻藏1 群决b 2 1 j 町生厩阳j 予夕u 则 到扩 i i 满足k 一 a 黼 9 吾以 一9 吾b i l 肌 击怕t i l 2 以i i i i b f l i i i l g k l l 墨圭 出l 考虑步长 3 2 5 第一式和 3 2 6 m m 一f x k a k g d 一a 札一k 恢l l l l d k l l 一警恢1 1 2 3 3 1 4 由 3 3 2 式可知 f x k 1 一 z 一 2 m a i a k 尤 z 一f x 3 3 1 5 一 z 一 一 z 一 3 3 1 5 两边同时加 z k 一 z 得 z k 1 一 1 一挚 茹女 一 茹 3 3 1 6 既然 k 是一单调下降列 o 叩全1 一 2 m a j a k g 一 1 于是由 3 3 1 6 和 3 3 3 可得 缸l 州i 熹新嘲 娑杀铲 0 于是可得 筹 1w 糕 3 s 烈 既然七一 o o 0 及 3 3 2 3 存在c 3 o o 和k o 对k k o 糕 辫1 k 0 当k k l 有既 1 2 一l n 1 一c k s 2 c c k 从而 b k l 差 b 女 3 既 l n k l 1 一悉 l 毳 3 3 2 7 i 1 三皿 b o e l 瞻 l n k 2 1 一时q i l n 虿q i 由a 3 可知 耋2 l 裂 i x 理扑觚玛i 3 3 2 8 m a x i z l i i i z i l z j 由 3 3 1 3 可知 k o o o 一1 0 4 我们选用最速下降方向为下降方 向 对于 3 2 8 中的参数口取法如下 若l 协 1 则n o 0 1 若i i g 1 则o 3 算法中我们令t 0 7 5 目 0 7 5 t a b l e3 所列数据是算法数值计算的统计 其中各列所代表的意义如下 p r o b l e m 在c 程序设计中问题的名称 d i m 问题的维数 s d 迭代中所用最速下降方向的次数 o f f 迭代中不满足 手s 川s k i 2 l l g k l t o 的次数 从数值计算结果可以看出 非拟n e w t o n 校正条件经常可以得到满足 因此 很少导致计算非正常终止 从此也可以看出b r o y d e n 族是非拟n e w t o n 的特例 这一结果也充分说明了对参数 恰当选取的重要性 结束语t 本文提出了基于w o l f e 型和a r m i j o 型线性搜索下非拟n e w t o n 校 正算法并证明了其全局收敛性 从数值结果也可以看出本文所提到的非拟n e w t o n 校正算法与b r o y d e n 族算法大体相当 各有所长 而且校正条件经常可以得到满 足 这样必然能导出最一般的校正情况 第3 章无约束最优化问题的校正非拟牛顿算法及其收敛性 t a b l e3 t e s tr e s u l t sf o rq b f g s b r o y d e nm e t h o d sw i t h n u m e r i c a i a r m i j o s e a r c h w b l f o s e a r c h e x d e r i m e n t sq b f g sb r o y d e nq b f g s b r o v d e n p r o b l e md i mi t e ro f fs di t e ro f rs di t e ro f fs di t e r o f fs d r o s e23 6003 3001 2o01 1 oo n o t h2l l001 4008008 oo b a d s c p 2 2 7 991 0 72 8 12 41 0 81 1 22 l01 2 62 9 0 b a d s c b 1 22 l081 40 01 0001 000 b e a e21 5o0 1 60o1 00090 0 b a x d32 200 2 000900l o 00 g a u s s34004002 00200 m e y e r 33 4 620 3 5 212 g u l f31o01 00l001 o0 b o x 33 1002 7001 5001 4 00 s i n g 43 8005 20 02 3o02 3 o0 w o o d42 8003 1004 1014 1 00 k o w o s b43 2o04 3o01 50 01 500 o s b l54 9005 00o4 10 04 400 b i g g s 64 4008 00 02 3002 1o0 o s b 21 15 9oo 6 7004 5004 500 w a t s o n1 26 2001 2 63 03 9003 81o 跳f s o n2 07 l0o7 l003 3 003 60o r o s e x2 01 4 200 1 6 0002 5002 600 s i n 磐x 2 04 7001 2 20 03 4003 4 00 p e n l41 5 700 1 5 2008 6002 8 00 p e n l1 01 5 2001 3 90 06 8006 80 0 v a r d i m1 05006 00600700 t r i g 1 03 50o 2 5002 lo02 1 00 l i n a1 01 l00 1 1oo7007 00 b y1 0 1 6001 6001 2 001 200 i e1 0 ooo l ooo5005oo i h dl o3 9o0 3 9oo1 60 01 6o0 j i i i d1 0 01 3 7001 3 40 07 3o07 300 l i nl o