（运筹学与控制论专业论文）应用新拟牛顿方程的信赖域方法.pdf

ab s t f a c t inth e c l as s i c a l t ru s t re gi o n m etho d fo r u n c o n s tr ai n e d o pt i m i zati o n ， th e c h o i c e o f the q ua d r at i c m o d e l a l1 d the s i zeo f the trustre g i o nar e cruc i altothe e ffec ti v enes s o f th e al g o ri t ll m . f o rexa n 1 p l e ， th et r l l s t re gi o nn e ， 八 o nmethodw ll i c hb as e don s e tt i n g b * = v ， f ( x * ) h asth e l o c alq 一 明 “ rati c c o nv e 笔 ence rate. b utif th e h e s s iani s to o c o mpu tati o nal e x p e n s s i ve to g et ， mos t p e o p l ec h o o s ethe q u a s i 一 n e 朋 八 o ne q u atio nto ge n er at e b 、 。 on the o l h e r h and ， if the trustre gi oni s l arge eno u ghtoge n er ate a l ar g ers tep ine a c hi t e r at e ， the c o nvetge n c e rate wil l n a t u r al l yincre as ed m anyp e o p l eaddedl i ne s e ar c h s t r a t e g y t o a dj u s t the trust re gi o n whe n th e t ri alstep s * o f th e s ubp r o b l e mi s fail e d . s i n c e t h e n e wq aus i 一e wto n e q u a t i o n c ang eta h i ghe r app ro x i m atio n t o the h e s si an mat ri x ， w e i nth i s p ap erc h o o s e m b f g supd at e toge n e r a t e b * . w h e nth es u b p r o l e m s o l ut i o n s * i s c o mputed ， w e u sethe l i nes e a r c h st at e g y tofi nd a p o i nt a 、 5 、 th ats at i s fi e s wol fe c o ndi t i o n . s othe m atrix 凡c an l l a t u r a l l ym ai l l t a l np o s i t i v e 一 d e fi ll i t eandthe s ubp r o l e mi s c o nve n i ent toc o rn p ute. w e al s og i v e a c o n dtio n whi chc ani n c o rp o n a t e 1 i n e s e a r c hmeth o dw i 1 ht ru s t r e g i o n m e th o dandu s e a 、 toadju stth e s i z e o f th e ne wtrust re g i onw h e n the s u b p r o b l em， s s o l ut i o n s * i s n o t ac c e p tabl e ， th ati s p * 叮 ， i t s atifi s e s the wol fec o n d it i o n a n d i s a c ce p tabl e fo r th e l ines e a r c h s t rate 舒 the n it ， s re as o n abl e tos etth e s i z e o f the 比 t re g i o n ac c o rd in g to a * 5 * ， s o t h e l i n e s e ar c h stra t e g y not o n l y 即ar ante e s th e re d u c t i o n o f th e al g o ri t hi n ， but al s o i m p ro v e s the adju s t n 1 e nto f the trustre g i o n s i z e .从 乞c o n s t r u c t a new al g o ri t l加 b as e d on th eabo v ea l、 a ly s i s ， wesh o wth atth eal g o 约 l h mpr e s e rv e sth efi rst or der gl obal c o nve r g e n c e o f the c l as s i c al1 n i s t re g i o n al g o r i 1 h m ， a n d th e l o c als u p e ri i nearc o nve rgen c e rate . n 姗e rc i a l r e s u l tsare p re s e ntedtos h o wt h eal g o ri 1 hi ni s e ffic i e nifo r s n 1 a 1 1 s i ze p r o bl e m k ey w o r d s : u n co n s 俪n e d o pt i m i zatio n ， t ru st e q u a t l o n ， l i n e s e a r c h m e t h o d s . 托9 1 0 11 n ew q uas i 一 n e ， 改 o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外， 不包含其他人已 经发表或 公布过的 研究成果， 也不包含我为获得任何教育机构的学 位或学历而使 用过的 材料。与我一同工作的同 事对本学位论文做出的贡献均已 在论文 中作了明确的说明。 研 究 生 签 名 :三 岩 二 。 。 7 年7 月占 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以 借阅或 上网公 布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、 借阅 或上网公布本学位论文的部分或全部内容。 对于保密 论文，按保密的 有关规定和程序处理。 研 究 生 签 名 : 鑫盈劫 刃年 7 月 若 日 硕士论文应用新拟牛顿方程的信赖域方法 第一章绪论 l l 信赖域方法早期背景 线性搜索方法和信赖域方法都是借助于目 标函数的二次模型来产生新的迭代点， 但他们对模型的 使用方式却有所不同。 线性搜索方 法用它来产生迭代方向， 之后借助 线性搜索策略来确定一个沿搜索方向的适当步长。 而信赖域方法是围绕当前迭代点定 义一个区域， 使二次模型在此区域内能充分代替目 标函数， 之后求解二次模型在此区 域内的近似最小值作为新迭代点， 即同时产生了 方向 和步长。 如果这个步长不可接受， 则减小信赖域半径并重新计算新的迭代点。当信赖域大小改变时迭代方向也是改变 的。一般而言，线性搜索先确定方向再求步长，信赖域先确定步长再求方向。 信赖域大小选择是影响每一步迭代效率的关键. 如果这个区域太小， 则算法就可 能错过了求解使函数下降量最大的点的机会， 会使迭代速度缓慢; 相反如果太大， 则 二次模型的最小值点将和目 标函数最小值点相差甚远， 因而不得不减少区域并重新计 算。 在实际计算中， 我们通过前一迭代点的表现情况来决定当前区域的大小。 如果模 型精确的逼近了目 标函数，并产生较好迭代点， 则信赖域大小将稳步增大; 否则一个 不可接受迭代点表明模型则此区域内己不能充分代表目 标函数，则需减小信赖域大 小。 与线性搜索方法相比， 信赖域方法有其优势。 即当目 标函数的非线性程度较高时， 增加信赖区域限 制的信赖域方法通常会得到比 线性搜索方法更好的迭代方向， 这是由 于此时， 在信赖域外二次模型对目 标函数的 逼近精度已 经大大失 真， 故以 它的 全局 最 优解作为迭代方向 往往已不是目 标函数的最佳下降方向。 下 面 给出 在点x * 处的 二次 模型 和目 标函 数 二 阶 泰 勒 展开 式 ， m * ( 5 ) = 人+ 夕 厅 5 + 专 s t bk s( 1 . 1 ) f ( 孔+ 5 ) = fk+ w 了 5 + 合 s t v ， f ( + ts ) 5( 1 2 ) 其 中fk= f ( x ， )， 袱 = vf( x * )， bk 为对称矩 阵，t 。 ( 0 ，1 )，由于 m 。 ( 5 ) = 人+ v fkrs + 0 ( ， 11， ) ， ， ， ( 5 ) 与 f ( x * + 5 ) 之 差 为 。 ( 115 1】， ) ， 故 当 5 较 小 时 近 似 误 差 减 小 。 当 bk 取 为 函 数 的 海 森 矩 阵 v 2 f( x * ) 时 近 似 误 差 为 o( llsll ， ) ， 当 ， 较 小 时 近 似 误 差更小 . 基 于bk= v z f ( 乓 ) 的 算法 称为 牛 顿 信 赖 域 方 法。 在迭代的每一步，我们需要求解下面信赖域子问题 硕士论文应用新拟牛顿方程的信赖域方法 瞥m (5 ) = 人 + 可5 + 告 5 了 b * 51!5 1 氏 ( 1 3 ) 其 中 么 0 为 信 赖 域 半 径 。 在 此 我 们 定 义 1111 为 欧 式 范 数 。 因 此 可 以 通 过 控 制 入 的 大 小 变化， 使得二次模型总是达到对目 标函数的较好逼近。 这是信赖域方法较线性搜索方 法的的 一个优点。 使得算法具有稳定性和鲁棒性， 可用于求解病态问 题， 并且具有较 强的收敛性质。 信 赖 域 方 法 最 早 可以 追 溯 到 求 解非 线 性 方 程f ( x)= 0 的 经典 莱 温 伯 格 一 马 奎 特方 法仁 3，选择的步长如下 叭二 一 (j (xt)j (x*) 了 十 凡 1) 一 ， j( 介 )f(x*) ( 14 ) 其 中 j( x)为f ( x)的 雅 克 比 矩 阵 ， 参 数人之 。 在 迭 代 的 每 一 步 更 新。 莱 温 伯 格 一 马 奎 特 方 法 的 本 意 是 通 过 引 入 参 数 凡 来 克 服 j( x * ) 的 病 态 情 况 ， 即 防 止 llu 、 1 2 太 大 。 由(1 4) 式 给出 的d 、 也 是 下面问 题的 一 个 解 望 势 1f (x * ) + ， (x * ) r d l:( . 5 ) s. t ikljz 、 氏 . ( 1 . 6 ) 由于约束条件 (1. 6)， 我们将经典莱温伯格一 马奎特方法看作是信赖域算法。 事实上， 非 线 性 最 小 二 乘 的 信 赖 域 算 法 就 类 似于 莱 温 伯 格 一 马 奎 特 方 法， 只是 用凡替 代人在 迭 代的每一步更新。近代莱温伯格一 马奎特方法实际就是指信赖域算法。 1 9 70年p oell 在7 和 10 中 第一次提出了 信赖域方法，并给出了算法的一 个 详细的求解框架， 他证明了算法具有一阶梯度的全局收敛性， 并且具有很好的稳定性 和收敛速度. 他的算法被称为经典信赖域方法， 其中给出的信赖域半径的更新策略一 直沿用至今。即基于模型函数与目 标函数定义比率 pk=f ( x * ) 一 f ( x * + 5 * ) m * ( 0 ) 一 m * ( 5 * ) ( 1 . 7 ) 其中分子称为预测下降量记为p red ，分母称为实际下降量记为a red 。并用这个比率 来 决 定 试 探性 步 长 的 可 接受 性 并 据 此 来 调 整 新 的 信 赖 域半 径。 注 意 到5 * 是m * 在 包 含 ， = 0 的 区 域内 的 最小 值， 故 预 测 下 降 量 通 常 非 负。 因 而当p * 为 负 值时， 新的目 标函 数 值f( 朴十 5 * ) 大 于 当 前 值f (x * ) ， 故 新 迭 代 点 不 可 接 受 。 如 果几接 近 于1 时 ， 表 明 模 型 对目 标函 数 的 拟 合 很 好， 故 在 下 一 步 迭 代 中 可 以 扩 大 信 赖 域 。 如 果pk为 正 又 不 接近1 ， 则不改变信赖域。如果接近于零，表明拟合不好则减小信赖域。 下面给出具 体 算 法 。 除 去m * 中 的 常 数 项 ， 得 县( 5) = 9 万 ， 十 扣丁 凡 : ， 此 时 子问 题即 为 吵吼 (5 ) = : 二 5 + 告 s r b * 5，115 1卜 凡 ( 1 . 8 ) 硕士论文应用新拟牛顿方程的信赖域方法 算法1 . 传统信赖域方法 令k 。为 常 数， 给定。 ， ， 一 人， 则凡+ 热1 正 定， 应用定 理(1. 1) 可 知 最 优 解p * 此时 存 在 唯 一 ， 故 同 时 有( 凡+ 从 1) p * = 一 9 * 和 ( 凡+ 八i) p * = 一 9 * . 两 式 相 减 得 伽 : 一 产 ， ) 夕 * = 0 如 果几价 0 则产 : = 产 ， : 否 则p * = 0 此时由(1. 1 2) 中 的 互补 条 件知 必 有产 : = 产 ， = 。 ， 因此满足定理 ( ， . 1 )的标量唯一。 根 据上面定理问 题 ( ， . 8) 转 化为了 求 解方程组 ( 1 . 1 2)。 为 进一 步分 析解的 结构， 假设凡 凡 _ : 凡为凡的 所 有 特征 值，由bk+ 八1 至少半正 定知产 * 之 一 人， 故 乓= 代 bk十 热0 十 9 ; ， 并定 义函 数 丸 (产 ) = 1卜 * 112( 1 .l a ) 下 面可 通过 研究函 数汽 切) 得出 产 * 与凡的 关 系。 令uau 丁 为凡的 谱分 解， 其中 a = 苗 吧( 人 人 ) ，则线性方程组( 凡+ 八 1) 几= 一 9 * 等价于线性方程组 ( a + 产 * 2 ) ( v t s ) = 一 v t g * 。 令u t g = (v ， 气 ) t ， 则 5 * ( 产 ) = 一 ( bk+ 产 * 了 ) : = 一 艺 人十 产 ，. 2 _ 。.， ， :。 2 _ v 子v 三 口 t 刀f = 115 llus. 1!十 + “ ， . 2 .， p “ 2( 入 + 川 ( 人 + 产 ) ( 1 . 1 4 ) 由 上 式 可 知辣汽 润= “ 及 如 果 、 “ 忽人 帕一 叭 据此，子问题的解可分为下述三种情况。 ( 1)凡正 定 ， 即 人 0，如 果 卜 ( 0)1 卜 凡， 则 有 二 s( 0) ; 否 则 ， 子 问 题 的 解 由 5 沙 ) 给出， 其中产 0 由 方程 (l， 1 3) 唯一确定。 硕士论文 应用新拟牛顿方程的信赖域方法 (2 ) bk不 定 ， 人、 0，且 v ， 饥这 时 必 有 户 一 凡 ， 因 而 由 (l. 12 ) 式 有 115 (川 卜么 因 此5 * 也 由 s( 声 ) 确 定 ， 其 中 产 一 凡由 方 程(l . 1 3)唯 一 确 定 。 (3 ) b * 不 定 ， 且 对 所 有 的 1 任 1 = 仁 / 凡 = 人 有v = 0 。 令 j = 一 菩 台 ， = 一 (b 如 制 all 、 * 则5 * 取 s k = j+ r z( 1 . 1 5 ) 其 中2 是凡+ 尸 、 1 的 零空 间 的向 量， r 由 方 程 (l .13 ) 确定 ， 此 时 被 称为 最困 难的 情形 。 上 面 分 析 表 明 除 去 s( 0)l 、 爪 和 最 后 一 种 情 况 ， 问 题(l ，8)的 解 均 由 方 程(l . 1 3) 选 取 适 当 的 产 产 ， 确 定 ， 其 中召 ， = max 卜 人 扔， 卜 ( 0)1 卜 么 的 情 况 求 解 并 不 困 难 ， 这 两 种 情 况b 、 十 川均 正定 。 而 后 一 种 情 况 数 值求 解 较困 难， 此时凡十 川奇异 。 m o re和 5 o re ns en5 根据下面引理 给出了 这种情况下近似解的 求解方法， 并给出 子问 题的 近似 精确解的求解算法。 引 理1 .3设 给定口 。 ( 0，1) ， s( 川为 下 列 方 程 组 在产 一 凡的 解 ( 凡+ 川 ) 5 = 一 9 ， 如果向量 2 满足 2 了 ( bk+ 对) : 夕 5 ( 产 ) r ( 凡+ 川) 5 ( 产 ) + 产 时 lls( 川+ 邵 = 凡 则有 f( x k ) 一 q * ( 5 扭 ) + 2 ) 之 ( 1 一 口 ) ( f ( x * ) 一 。 二 ) 其 中 城为 问 题(l .8 ) 的 最 优 函 数 值 。 h eb de n 3 7 利用问 题的 特殊结构 也构 造了 一个 有效的 迭 代方法。 由于 ( ， 1 3 )中解的分式结构知其倒数更像一个线性函数 ，故可应用牛顿法求 解下列等式的根 p ( 尸 ) = l 1卜 凡 + 川 ) 一，9 * 二 o( 1 . 1 6) 得产 * 的迭代公式 川 +1 二 川- ( 1 . 1 7 ) 经过一些基本的处理和变化上式在实际计算中可由下列算法执行。 硕士论文 应用新拟牛顿方程的信赖域方法 子问题 ( 1 .8 )的精确解求解步骤: 第 一 步: 初始 化产 ，风 和9 * ; 第 二 步: 分 解凡十 川= r r r ， 其 中 r 为 上 三 角 阵 ; 第 三 步 : 求 解 p 满 足 r 丁 rp= 一 9 * ， 如 果 月 2 几 则 终 止 ; 第四 步: 求 解q 满 足r 了 q = p ; 第 五 步 : 取 产 一 产 + 山 川 ， /li all ， )4i 川 一 汽 ) 风: 继 续 第 二 步 。 1 .4牛顿信赖域方法 当 海森 矩阵的 计 算 代 价不 高 时 ， 在 信 赖 域 方 法中 当 取凡= v z f (x * ) 时 4 0 ， 便 得 到牛顿信赖域方法。相应的也有四 种子问 题的 求解方法。 ( 1) 折线法;(2) : 二维子 空间方法;( 3 )精确解解法; ( 4 ) 共扼梯度法。其中 (3) 在一定条件下收敛到满足 一阶和二阶必要条件的聚点，并具 有牛顿法的局部二次收敛速度4 3 。 1 .5 信赖域方法研究现状 1 . 5. 1 刻度矩阵 当目 标函数的刻度很差， 即目 标函数对自 变量的微小变化会有较大的波动时。 从 几何上看， 最优点x周围的等高线图 使其位于一狭窄的扁行区域中心，了附近呈现 为 超 不 规 则 椭 圆 形 。 而 信 赖 域 的 定 义 是 以 第k 步 点凡为 中 心的 一 圆 形区 域， 故 对目 标函 数的近似程度在短轴方向， 即目 标函数的 变化最敏锐方向 严重失真。 而补救方法 就是在这些方向上缩小信赖域大小， 并在变化缓慢的方向 增加信赖域大小。 因 而考虑 下述信赖域 dso 占( 1 ，1 8 ) 其中d为正定对角矩阵， 对角元素在目 标函数敏锐方向 较大， 缓慢方向 较小从而达到 信赖区域有效控制。相应的子问 题便是 m i d o( 5 、 二 v flr了 + 冬 s t b l s ，11 1! 次( 1 . 1 9 ) d 的 构 造 信息 可以 通 过 计 算二 阶 导 数护 f / ax 厂 得 到。 d 随 迭 代的 每 一 步 进 行 更 新 ， 并 限 定 其 对 角 元 试 在 预 先 指 定 的 区 域 a， ，dh 内 变 化 ， 其 中 0 dl 么 。 因 为 d只需大致反映出目 标函数的曲折信息即可，故不必非常精确。 将这一方法应用于前述的所有方法中便可得出了具有刻度矩阵的相应信赖域方 硕一 七 论文应用 新拟牛顿方程的信赖域方法 法。 micha elg e rtz3 3给出了 一 类 带 刻 度 矩阵 的 信 赖 域 方 法。 1 . 5. 2 非欧范数信赖域 应用除欧式范数的其他范数来定义信赖域， 如 115 111 凡和15 1!。 凡 特别当 应用无穷范数时，可行域变成为 xk+ 5 之 0 ， 5 之 一 凡 e ， 5 凡 e ， e = (l， 1 ， ，l) r ， 子问 题的 求 解 便 可 应 用 标 准的 二 次 规 划 方 法. 1 . 5. 3 结合线性搜索策略 为了 提高 信 赖 域 算 法 的 收 敛 速 度， toint4 1最 先 提出 了 在 信 赖域 方 法 中 加 入 线 性搜索 想法， 他的 方 法是当 步长 不 可 接受时 ， 取xk 十 ， 代替、， 其中f ( xk + ， ) f (x * ) ， 但没 有 给出 有 关 下 降 量 的 具 体 条 件， 也 不 影响 算 法的 收 敛 性 质。 n o ced al和丫 uan 3 91 提出 了 在 信 赖 域 子问 题的 解不 可 接 受的 情况 时 ， 即当 f (x * + 5 * ) 之 f(凡) 时 ， 在5 * 方向 应 用 后 退 方 法 进 行 线 性 搜 索 得 到、 十 、 ， 使f ( 凡 + ， ) f (x * ) 。 下 面 给出n oc e d al 和y uan 的算法。 通常指定常数0 rl 九 1 。 是 为 防 止 信赖域 半径任意的 减小， 但 在收 敛性证明中为并不 起作用。 算法2推广的信赖域算法 取常 数k 。， 0 泞 : 叭 1 和0 y ， rz 1 二 且 x * 收 敛 ， 则 凡 不 趋 于00 然 后 可 立 即 得 出 任 意 满 足p ， 和尸 2 的 算 法 ， f (x * ) 下 无 界 或 1 加inf，、 . 9 * 卜0 二 者 必 居其一。 为 证 明 信 赖域 算 法的 一 阶 全 局 收 敛 性， p o we“ 对 信 赖域 子问 题的 近 似 解5 * ， 在下 降 量 上， 给出 了 以 下 要求 ， 即 存 在 常 数: 0 使5 * 满 足 一 q ( 5 * ) “ r ll。 * 0 m in( 凡 ， 11。 * / 1bk 1) !卜 * 卜凡( 1 .2 3 ) 对此有下面关于柯西点在下降量方面的引理. 引理， .4( 户 。 w e lo 吼 ( 尸 二 ) 、 一 告 119 * l1m in( 汽 ， 119 * 1!/ 11凡 12 ) ( 1 . 2 4 ) 证 明如 果9 万 凡9 * 0 ， 则 qk( 一 叮* ) = 一 心万 9 * + 合 a 9 万 bk g k 存 在 一 个 无 约 束 的 最 小 值 ， 且 当 a = 9 荟 9 * / 9 二 b * 9 * 区 的 最 小 值 八，_ _ 、 ， _ : _ ， g f g *、 _ ， : _ “ : 力 . 。 ，。 认( 一 ag* ) = 一 专 9 二 9 * ( 拐髻二.) 一 合 ” 9 * 1一 / “ 凡， _ 。一 、 - 一。 二 b *9 * 并 且 g f g * / g f 凡 9 * 爪 19 * 1 ， 则 沁* 卜凡 因 此 在 a 处 取 得 有 约 束 下 的 最 小 值 。 如 果 g j g * / 9 万 凡 9 、 么 115 、 卜则 a = 几 /ll 9 * ! 处 取 得 有 约 束 下 的 最 小 值 硕士论文应用新拟牛顿方程的 信赖域方法 么 (一 、 * ) = 一 9 : 。 * (惠) + 奋 。 (惠)9 : 凡 。 * 119 * 11119 * 11 一 9 : 9 * (惠) + 、 哗 孕 )(惠)9 : 凡 9 * 19 。 119 二 气g k llg * 1 一 一 ， : ， 氏 、 言 9 士 g k 又 万 ， 不) 119 * 11 如 果 g j 风 9 * 。 ， 则 不 存 在 无 约 束 的 最 小 值 且 在 。 = 凡 / 115 * 处 取 得 最 小 值 级( 一 ag * 卜一f g 汁 告 a ， 盯 bk g * 一 ag 荟 9 。翎 9 * llsk 故意列举所有的情况，引理得证 . 如果 是 子问 题的 不 精 确， 则 下降 量 至少 大于 柯 西点. 如 果几 为 精 确解， 由 于 么(s ) 的 最 小 值至 少小 于等 于其 在负 梯 度 方向 上 最小 值， 上述引 理 给出 了qk( 5) 最小 值 的 一 个 上 界 ， 由 此 也 可 得出 (1 .2 3) 中 : 的 一 个 上 界， 即 取: 朴此 时 满 足 (1 .2 3) 的 总是存在. 由于算法2 在结构上实际包含了算法1 ，故只需证明算法2 的收敛性即可。 引 理， .5 (p owe ll)假 设f 在 区 域q 二 护上 连 续 可 微， 序 列 x * 由 算 法2 产 生 ， 并 且 子 问 题 (1 ，8)的 近 似 解凡 满 足 (1 .2 3) ， 平 凡 一 致 有 界 ， 如 果 f 在 。 上 有 下 界 并 且 存 在 e 使 得 119 * 卜e ， 证 明 : 艺 。 . f( 凡 ) 则 算 法 或者 找到 一 些 满 足 收 敛 条 件 的点x * 或者 有凡峥0 且(x * 收 敛. 假设算法 2不终止于满足收敛的点x ; 。由于f有下界， 一 f (xl* 1 ) 。 ， 可 得 云 f( 乓 ) 一 f( 凡 + ， ) ， 又 因 凡 满 足 ( 1 . 2 3 ) 可得 云. ， f ( 乓 ) 一 f ( x * ， 1 ) 叨 ， 云。 : 、 * 1而 n( 凡 ， 1。 * / ib ， 协( 1 .2 5 ) 有 由 于 存 在 : 使 得 115 * 卜: 及 1凡 1 一 致 上 有 界 可 知 必 有 下 式 成 立 工 胜 ， 几 ao 如 果 不 存 在 成 功 的 迭 代 ， 则 爪 片 一 1氏 ， 此 时 显 然 有 么. 么 1，么 对 一 1一 ，成 + 1 ， 同 理 有 艺 k ， 凡 00 另一方面如果存在无穷个成功的迭代点， 令1 表示任一成功的迭代， 但1 + 1 不成功， 令m 表 示 满 足k 任 s w十 1 k m ， 此 时 有占 * 对一 1 一 ， 氏 十 ， r 岁 一 1 一 ， r 、 占 ， 因 此 衍肠 艺凡 艺 对 一 1一 ，凡 药 令 3氏 艺 对= k 二 1 申 ik 二 1 十 1 1 一 儿 因此 矛 。， ， ， . 厂 3、 二 。 二 叽 盗妙宁下，甲) 乙 几 co 无 二 ， 51 一2 2 七 。 亏 立 即 可 知 艺 。 。 凡 0 使 得一 qk(s * ) 之 喊。 由 于x * 收 敛， 所 有 点 列 都 位 于 一 个紧 集中 ， vf( 乓 ) 在 此 集中 一 致 连 续， 所以 如 假设么峥0 ， 则 麟11vf (、 + 5 * ) 一 vf (x * )。 0 。 而 此 时 不 等 式 (1 .2 6) 趋 于 零 表明 p * 峥1 。 但 此 时 根 据 信 赖 域 半 径 的 修 正 法 则 有凡 不 趋 于零。由 此矛 盾可知几必定不 趋于 零，引 理得 证。 由 上述引理算法满足p l 和p z ， 可得如下定理。 定 理， .7( p owe il)设f 在区 域。 二 r上 连 续 可 微， 由 算 法2 产 生 的 序 列仕 * 二 。 。 假 设 子 问 题 (1 .8) 中 9 * = vf(x * ) 且 其 近 似 解 5 * 满 足 (1 .2 3) ， 凡 1 一 致 有 界 ， 如 果 f 在 。 上 有 下 界 ， 则 算 法 或 者 终 止 于 一 些 满 足 收 敛 条 件 的 点 凡 或 者 有 li m infk， 。 115 * 卜0 。 i 2 硕士论文应用新拟牛顿方程的信赖域方法 1 .7不精确线性搜索策略的主要方法 1 . 7 . 1戈德史丹准则: 给 定 产 ， 。 ， 。 尸 。 1 ( 通 常 取 产 。 (0 ， 与 ， 。 。 己 ，1) ) 选 取 、 满 足 乙乙 f(乓+ 气 入 ) f(凡 卜ak 尸 可 ，( 凡 )t 爪 f( 乓十 气 么 ) 之 f (x*卜气 动 了 ( 乓 ) r 几 戈德史丹准则的一个缺点是可能将目 标函数的极小点排除在可接受区间之外。 为 了克服这个缺点，沃尔夫提出一个沃尔夫搜索准则。 1 . 7 . 2 沃尔夫准则: 参 数0 从 告 ，。 ， : 。 0 满 足: f ( x * + a k s * ) 一 f ( x k ) 粉 la k g j s ，( 1 2 7 ) 9 ( xk+ a * 5 * ) t s * 之 。 9 万 5 ， 一般而言，口 越小， 线性搜索越精确。 然而，口 越小，工作量越大，用得最 多的就是沃尔夫准则。当第二个条件改为 : (x+ a * 5 * ) r 、 1 一 ， (、 ) 了 、( ， ，2 5) 称为强沃尔夫准则。 1 . 7 . 3 简单准则的后退方法: 给出p 。 (0 ， 幻，。 1 0，只 需 在 氏 。 。 定 理1 .8 假 设 函 数f 二 阶 连 续 可 微， 如 果扛 ， 收 敛 于 一 点二 满 足g( x ) = 0 和v ， f( 犷 ) 正定，则 =1 ( 1 3 1 ) 应用以上处理方法及定理表明，更新公式 1 .3 0可保持正定，当k 充分大时修正 公式1 . 3 0可自 然保持正定。 下面定理见z h a n g和x u 2 41 ， 说明 新拟牛顿方法中p 万 凡 习 p * 对二 阶曲 率 v ， f ( x * + ， ) 夕 * 的 逼 近 程 度 更 高 。 定理 1 .9假设f ( x)在包含点乓和xk + 1 的开凸集合上二阶连续可微， 海森矩阵 v f(x)u pechitz连续， 则 有下 面估 计 式成立: 尸 万 ( v ， f ( x * ， 、 ) 尸 * 一 夕 * ) = 0 ( !1尸 * 1 尸 荟 ( v f ( x * + ， ) 尸 * 一 2 * ) = 0 ( 1夕 * 1! 3 ) )。 硕士论文应用新拟牛顿方程的信赖域方法 1 .9本文的研究问 题和结论 由上述研究现状可知， 影响信赖域方法收敛速度的关键是子问 题的求解和信赖域 半径的选择， 其中子问题的求解方法已 经趋于稳定， 关键便是提高二次模型的 近似程 度。 当 信赖域可信且较大时， 这时子问 题可以 在较大的范围内 求解， 步长通常也较大， 这样每次迭代点的跳跃幅度也较大， 收敛速度会增加。 对于传统信赖域方法只有子问 题的 求 解较好， 即 二 次 模型 近 似 程 度 较 高时 ， 解 得的5 ， 才 会 足 够的 好， 此时八接 近 于 1 ，信赖域半径被合理增大，此时收敛速度理应加快。如在牛顿信赖域方法中取 凡= v ， f( 凡 ) ， 算 法 具 有 牛 顿 法 的 局 部 二 次 收 敛 速 度。 但当 海 森 矩 阵 的 求 解 代 价 太 高 或不可行时，牛顿信赖域方法不可行。 另一方面， 在信赖域方法结合线性搜索策略研究中， n o ced al和丫 u a n 给出在信 赖 域 方法失 效时， 即 在pk ， : 时 ， 在 信 赖 域内 应 用 简单 准则 的 后 退 算 法得 到 新的 下 降 点凡 + ， ， 但 他们的 想 法只 是 使算 法 在 实 用中 对 传 统 信赖 域 方 法 起 到 弥 补， 并 没 有 使 用 线 性 搜索 方法 提 供的 下降 条 件去 改 善 算 法的 收 敛 性。 g e rtz使 用a * 5 。 调 整 信 赖 域 大 小的 好处是 当八不 理想时 ， 如果 线 性 搜索 能 够对 下降 量 提 供帮 助， 则 说明 在 线 性 搜 索 意 义 下， 二 次 模 型的 逼 近 程 度 也 是 可以 接 受 的 ， 此时 根 据可 a ks * 的 信息 调 整 信 赖 域 大 小，由 于5 * 在 信赖 域内 是 近 似最 优的 ， 故“ * 往 往 大 于 等于1 会 导 致 信 赖 域 增大 或 不 减 ， 因 此 每 一 步 迭 代 的 跳 跃 也 较 大 。 但 他 对 p 的 定 义 中 有 q 。 ( 5)1 别 qk 。 习 ， 故 p pk， 这会使比 率几可 接受 性 标 准 提 高， 例 如当p 冲 p* 时， 本来 对八可 接受 的 步长会因 取p 而 被排除， 另 外他的 带 变化沃尔夫条 件(1.21) 和 (1.2 2 ) 也 过于苛 刻， 虽 然a * 存 在 但实际 计 算困 难。 因 此， 我 们 便想到 应用 新的 拟牛 顿 方程 来 产生bk，以 达 到 对目 标函 数 更 高的 逼 近精度。 并使用强沃尔夫准则进行线性搜索， 在信赖域半径的 调整