（应用数学专业论文）简单界约束优化的仿射尺度内点信赖域算法的收敛性.pdf

简单界约束优化的仿射尺度内点信赖域算法的收敛性 中文提要 中文提要中又提要 在建立简单界约束优化问题的局部收敛结果时 多数论文均假设在解处 严格互补条件成立 本文在去掉了这一假设的基础上发展出一种既全局收 敛又局部二阶收敛的仿射尺度内点信赖域算法 首先考虑用拟一n e w t o n 法解简单界约束优化问题的一阶k k t 条件 从中 建立了一个二次模型 每步迭代解一个信赖域子问题 即在一个椭球约束下 极小化一个二次函数 再使用投影来保持迭代点严格可行 并根据目标函数 及其近似来决定是否接受尝试步 其次我们建立了收敛到一个稳定点的全局收敛结果 即若 z t 是由仿 射尺度内点信赖域法产生的序列 则序列的每个极限点都是问题的一个稳 定点 另一方面 假设在迭代的极限点牙处只成立强二阶充分最优条件 而严 格互补条件并不要求 我们的主要结果表明序列 t 以二阶的速度收敛到 牙 从而得到了算法的局部收敛结果 最后我们用一个数值例子说明了理论分析和数值试验结果的一致性 关键词 简单界约束优化 信赖域 内点算法 收敛速度 作者t 刘静 指导老师 陈中文 t h ec o n v e r g e n c eo f a f f m e s c a l i n gi n t e r i o r p o i n ta b s t r a c t t h e c o n v e r g e n c eo fa f f i n e s c a l i n gi n t e r i o r p o i n t t r u s t r e g i o nm e t h o d sf o ro p t i m i z a t i o nw i t hs i m p l eb o u n d s a b s t r a c t t oe s t a b l i s hl o c a l c o n v e r g e n c e r e s u l t sf o r o p t i m i z a t i o np r o b l e m s w i t h s i m p l e b o u n d s m a n yp a p e r sa s s u m e s t r i c tc o m p l e m e n t a r i t ya tt h es o l u t i o n t h em a i np u r p o s eo ft h i s p a p e r i st ow e a k e nt h i sa s s u m p t i o na n dt od e v e l o pa na f f i n e s c a l i n gi n t e r i o r p o i n tt r u s t r e g i o na l g o r i t h m t h a ti sg l o b a l l ya n dl o c a l l yq u a d r a t i cc o n v e r g e n t w ef i r s tc o n s i d e rt h eq u a d r a t i cm o d e l w h i c hi se s t a b l i s h e dw h e nt os o l v et h ef i r s t o r d e rk k tc o n d i t i o no ft h ep r o b l e mb ye m p l o y i n gaq u a s i n e w t o nm e t h o d at r u s t r e g i o ns u b p r o b l e m w h i c hi s d e f i n e db ym i n i m i z i n ga q u a d r a t i cf u n c t i o ns u b j e c to n l y t oa 丑e l l i p s o i d a lc o n s t r a i n t i ss o l v e di ne a c hi t e r a t i o n w eu s eap r o j e c t i o nt om a i n t a i n s t r i c tf e a s i b i l i t y w h e t h e rt h e t r i a l s t e p sa r ea c c e p t e dd e p e n d s o nt h eo b j e c t i v ef u n c t i o n a n di t sa p p r o x i m a t i o n t h e nw ec a ne s t a b l i s hg l o b a lc o n v e r g e n c et oas t a t i o n a r yp o i n t t h a ti s i f 魄 i s t h es e q u e n c eg e n e r a t e db yt h ea f f i n e s c a l i n gi n t e r i o r p o i n tt r u s t r e g i o nm e t h o d t h e n e v e r yl i m i tp o i n to f t h es e q u e n c ei sas t a t i o n a r yp o i n tf o rt h ep r o b l e m t h el o c a lc o n v e r g e n c ep r o p e r t i e so ft h ea l g o r i t h ma r ee s t a b l i s h e d w ea s s u m e t h a tt h es t r o n gs e c o n do r d e rs u f f i c i e n to p t i m a l i t yc o n d i t i o n sa tt h el i m i tp o i n t 至o f t h ei t e r a t e sa r es a t i s f i e d b u ts t r i c tc o m p l e m e n t a r i t yi sn o tr e q u i r e d o u rm a i n r e s u l t s h o w st h a tt h es e q u e n c e z t c o n v e r g e st o 牙a taq u a d r a t i cr a t e f i n a l l yan u m e r i c a le x a m p l e s h o w st h a tt h et h e o r e t i c a la n a l y s i sa c c o r d sw i t ht h e n u m e r i c a le x p e r i m e n tr e s u l t k e y w o r d s o p t i m i z a t i o nw i t hs i m p l eb o u n d s t r u s t r e g i o n i n t e r i o r p o i n tm e t h o d s r a t eo fc o n v e r g e n c e i i w r i t t e nb yl i uj i n g s u p e r v i s e db yp r o f c h e nz h o n g w e n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明 所提交的学位论文是本人在导师的指导下 独立进行研 究工作所取得的成果 除文中已经注明引用的内容外 本论文不含其他个人 或集体已经发表或撰写过的研究成果 也不含为获得苏州大学或其它教育 机构的学位证书而使用过的材料 对本文的研究作出重要贡献的个人和集 体 均已在文中以明确方式标明 本人承担本声明的法律责任 研究生签名 立4 尊日期 狃四 q 学位论文使用授权声明 苏州大学 中国科学技术信息研究所 国家图书馆 清华大学论文合 作部 中国社科院文献信息情报中心有权保留本人所送交学位论文的复印 件和电子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文 档的内容和纸质论文的内容相一致 除在保密期内的保密论文外 允许论文 被查阅和借阅 可以公布 包括刊登 论文的全部或部分内容 论文的公布 包括刊登 授权苏州大学学位办办理 研究生签名 童 l 趋 日期 2 翌生 生 了 导师签名 毒垒鍪善一日期t 鱼骂醵华 简单界约束优化的仿射尺度内点信赖域算法的收敛性 一引言 第一章引言 本文考虑简单界约束优化问题 i m s t o z b 其中qb 形且n b 记可行域厂 如 舻j o z 吣 可行域的内部 户 伽 r 8 i n 1 阶收敛的 简单界约束优化的仿射尺度内点信赖域算法的收敛性 二 算法 第二章算法 考虑问题 1 1 其中 在 上二阶连续可微 记g z v f z 设点孟 f 是问题 1 1 的一个局部极小点 则它满足一阶k k t 条件 d 牙 9 牙 0 2 i 其中d z 是一对角阵 其对角元素如下定义 哦c z lx i i 一啦 玩一z t 雾 i 差 三i c z z 假设当前迭代点z 女 p 我们如1 6 中那样应用拟一n e w t o n 法解 2 1 m x 女 一x k 一d x k 9 现 2 3 其中m z d z b z e b z 是v 2 z 的一个对称近似 e z 是一对 角阵 其对角元素如下定义 6 f1 9 z t 1 若i 9 z i m i n x t 一啦 风一 t 9 e z 或m i n x 一o i 玩一 i 和 z t p 2 4 10 其余情况 其中p 是某一大于1 的固定常数 由此我们定义二次模型 仇 s g s 严仉s 简单界约束优化的仿射尺度内点信赖域算法的收敛性二算法 类似于c o l e m a n 和l i 在 4 中那样我们考虑子问题如下 i n i n c k 5 29 吾s i 3 t q s 26 s t d i 5 s f 其中 i 为e u c l i d 范数 但我们不是通过简单地将步长乘以一个调比系数 的方法来使新的迭代在可行域内部 而是采用投影的方法来获得可行点后 对这个新步长进行收缩 进而得到新的迭代点 就可保证这个迭代点在可行 域内部 任意z r n 到厂的投影定义为 p z m a x a m i n b z 2 7 上式按分量计算 设靠为 2 6 的解 则定义尝试步孰为 8 k a k p z k 氟 一z r 2 8 其中o k m a x a 1 一i i p x i 一5 9 k l l 盯 0 1 是接近1 的常数 为了决定是否接受尝试步 我们定义目标函数从 到z 一 s 的实际下 降量为 a r e d k 8 f a z k 一 s 预测下降量为 p r e d k s 妒 o 一妒女 s 其中 仇 s g s s t 风s 计算出尝试步乳后 计算比率 p 裂r e a k 2 9 乳j 简单界约束优化的仿射尺度内点倍赖域算法的收敛性 二 算法 步2 如果 i d 9 s 则停止且返回x 作为解 否则求解 2 6 式 其 i 口l k 岛 n 叩2 4 简单界约束优化的仿射尺度内点信赖域算法的收敛性三全局收敛性 第三章全局收敛性 为讨论算法2 1 的全局收敛性 作如下基本假设 a s 3 1 i 在 上二阶连续可微 i i 存在蛳 p 且水平集c 伽 乒 e f x f x o 是紧集 i i i 存在胎 0 使j j 风j j5 加 v k i v 存在x 9 0 使l 9 z 0 使 证令 妣 o 一亿 船 盯2 i m i n 7 l l 彘i e 3 2 喇 蜘t 篙 蜊 毋 一丽d k g 矿k 一1 堕i i 雪k l l 炮 一t d k 9 2 一t 瞀q 1 2 d k b 一慨1 印t 珊 一舷忡互1 t 2 丽1 鳃 玩 吼 氨 由l i d 5 一t 篙川弛 有 由 咄纠黼剑一艚 ts o 啦一z t 一 一t 堕韦 产 以一z t 加i 1 2 n 6 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三 全局收敛性 若g k i 0 贝 也 玩一 i 从而 t 一 o 则哦 写 x k i a i 从而 t s 斟 故 其中 怯为k 范数 因此 恢i i 咚面丽 t 0 巩 其中 t k r a i n 黜一 设吼 t 在 o 孔 上的极小值点为t 若 o 孔 则 若 t k 则 皿娴2 磊币 蕊i i 争k l l 4 墨一兰 牡 一2 i i d 岛磷 b 吼 铂 一最慨 露赤鳍 风西 玩 鲰 一靠1 1 孰 疋 靠i l 一 乃l i 帅i i 7 简单界约束优化的仿射尺度内点信赖域算法的收敛性三全局收敛性 于是 从而由 3 1 皿m t m a x 一互1 i 五i j i l l 彘云蕊1 1 2 一 死l l 觎i 一批灿 燕埘 c k o 一o k s k 妒k s k 一0 2 v k t 1 却钏酬赢埘 卸训侧燕 脞 由 a s 3 1 可知 存在x d 胎 0 使 d 如5 肋 i i e i i5 加 v 七 于是 d 1 鼠d 1 e k l lsx 刍x 日 x e 7 m i n 磊磊1 再 西1 引理得证 引理3 2 在假设 a s 3 1 a s 3 2 下 存在常数 y 0 使 o 一妒 叮2 i i 氟l m i n 删姚乱 3 3 证由娠1 e k 半正定及 3 2 有 m o 一妒 轧 一9 t 8 k 即e 一9 融一 慨 昧1 e k 船 互1 s 虿巧1 吼稚 一 f f s 一秘1 仇s t j l s t d 1 最s m 也 o 一蜘e 爷1 蛾1 取s e 8 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三 全局收敛性 1 f j o 一讥 s 女 去仃2 i i k l l m i n 7 ij 氨0 a z 证毕 由算法2 1 的步4 易得下面的引理 引理3 3 在假设 a s 3 1 a s 3 2 下 若对所有充分大的女 有n 1 则 存在a m i 0 使a k j 对任意 成立 设 z 是由算法2 1 生成的无穷序列 则在基本假设 a s 3 1 a s 3 2 下 有如下全局收敛性结果 定理3 i 在假设 a s 3 1 a s 3 2 下 l i r ai n f 1 1 9 1 1 0 证假设存在s 0 使得对所有充分大的南 有 彘 5 如果只有有限次成功迭代 则对充分大的k 有 州冬阮 e 从而 乱 o 0 如果存在成功迭代的无限序列t 觑 则 箸锚 z k 一 石h s 觑 一 妒 o 一妒k s k i r h 9 3 4 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三 全局收敛性 由引理3 2 有 进而有 f x k 一 z h 7 7 l 妒t o 一垆 8 h q 仃z l i 靠 l l m i n 7 饥川 a k i q i i 靠t l l m i n 7 饥川 m b 一规 2 阶 一m 虬 1 q 1 0 2 慨 i l m i n 州 l l h 0 由于 f x t 单调下降且下有界 又对充分大的k 有i i 彘1 l s 故 h o i 0 不妨设 如 对不成功迭代 有 对成功迭代 有 于是 越 k 0 k 1 仍 a k 1s 岛 s a k 躬 讲 o 0 0h l k i 2 s h 风熙 船 i 0i 0 j o s 1 卢3 厦 k j 0 i 0 叫 岛 静 o o 苌一 瑚 l i 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三 全局收敛性 因此 再由投影的非扩张性 恕 2 o 乳 l 1 a k p x k 氟 一z k l i 尸0 氟 一 k l i l p 氨 一p x k l l 菇d i o 靠1 1 1 1 d i d i 5 瓿 x d 女 于是 由引理3 2 对充分大的七 i r k 1 l 渊一l 1 一f x k s k 一 1 i l o k o 一i o k s k 1 l l 竺 篙箸趣 i 女 酆 一f x k 一鳍s 七l 虿i i t b k s 女i 一 盯2 l 治 i l m i n y l l 彘 k l 粕 一 z 一9 s i i s 吾鼠乳l 1 3 一 盯2 s m i n 似 a k 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三全局收敛性 其中 0 1 故 珏由引理3 3 得到矛盾 证毕 定理3 2 在假设 a s 3 1 a s 3 2 下 j i m 慨 0 k o o 证如果只有有限次成功迭代 则 1 i m 恻l 1 诬掣恻l o 3 5 如果存在成功迭代的无限序列 假设存在s o 0 及无限指标集k s 使得对所有k k 有 l i 2 0 其中s k 2 m k 是成功迭代指标集 定义 则k 霞 而 霞 似 s 酬 印 a r e d k 5 h 2 而瓦两 h 一 岛 8 氟 2 孤矿彳丽 田l 3 6 简单界约束优化的仿射尺度内点信赖域算法的收敛性三全局收敛性 由引理3 2 有 进而有 h 一 z h 兰 l 妒 o 一9 k s k 目 彘 i i m i l g 2 7 轨 f i h 互目 彘 i i m 7 轨t f i h m b 一 l i r a f x k t 2 蚤m 知 一m 川 z t 一f x k 霞 去叩t a 2 协i i m i n 删钏 趣 由 一 单调下降且下有界及 3 6 知 由定理3 1 知 a k k f 乳露 0 故任取克 k 霞垦s 可在s k 中取到大于 的第一个指标 将其记为 f 女 则 j k 一1 i i 勺 一奶 j j s f c k i 物 一q l i j k d s z 一l 恃i l i k d c 8 l 一l x d a i i k d s j 一1 x d a j j 幻e k 简单界约束优化的仿射尺度内点信赖域算法的收敛性 三全局收敛性 故 1 i m1 i x 一z 圳 0 又口 在紧集 上连续 故一致连续 因此 o 舰慨t 一酬 0 另一方面 白 k 一氨i i l l 彘 一i i 鱼 q 2 e o 一占o e 0 矛盾 证毕 定理3 3 在假设 a s 3 1 a s 3 2 下 墨则d 胁忙0 3 t 7 证由定理3 2 熙 i d g t l 1 i m 愀 e d 女j i m i i k l l n 证毕 1 4 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛性 第四章局部收敛性 本章讨论算法2 1 在强二阶充分条件下的局部收敛性 为此给出如下假 设 a s 4 1 i v 2 在 上局部l i p s c h i t z 连续 i i b k v 2 i i i 算法2 1 产生的序列 矾 收敛到牙 引进记号 a i 1 n l 牙 啦 6 i 9 i 牙 o j i l 札 ia i 孟i 定义强二阶充分条件 a s4 2 设孟满足 2 1 且存在a 0 使 s t v 2 s d l i s i l 2 v 8 t s r l s l o v i a 引理4 1 在假设 a s 3 1 a s 3 2 a s 4 1 a s 4 2 下 当k 充分大时 仇 正定 证对v 0 s 舻 如果对v i 互 黾 0 则s t 勇 从而 s t q 自8 8 t b k 匹1 毋 5 3 t v 2f x k s 十s r 巧1 e k s 1 5 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛性 s t v 2 牙 s 8 t v 2 f x 一v 2 牙 5 s t d i l e i s 0 f 一 v 2 z 女 一v 2 f 面 1 1 l l s l l 2 8 t d i l b s 当k 充分大时 有 饥 a z 0 当存在i o a 5 面 0 时 不妨设牙 o 如g l 牙 0 则 充分大时 注意到 及 即得引理结论 记 d l o k 茁 o n i o e t z 七 1 m 茁七 8 丁仉s s tv 2f x s 4 8 t d i l e k s 刊v 2 m 圳 h 卜描慨o 2 s 一q i l 肌 s f p p z k s 一嚣 1 毗 5 面丽两1i 习 w k d i a g w i x k 1 6 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛睦 这里叫i z 的定义与文 6 略有不同 但不难验证 对此m 文 6 中结论都 成立 再记 凰 吼 d k b k 毋 则由文 6 引理2 h k 非奇异 且存在c h 一 0 使得 1 i 酊1 1 l c h l i 故 s 一q i l 鲰 一颤1 砜d k g k 一巧1 w d 甄 从而 懈恪 圳驯 4 1 得 引理4 2 在假设 a s 3 1 a s 3 2 a s 4 1 a s 4 2 下 存在常数国p 0 使 对所有充分大的k 成立 o 一妒自 s r p p l i 纨1 1 2 4 2 s 瓢 若霉 j n j 6 i 啦一z 七 i 若霉 一 s 琢 b l 嘶r 鲰t s k n p 互1 s r t 魄s p 1 7 fi ll l l l p m s 艾 定由征 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛性 s 毋s 扩 互1 s p r 鼠s l f f p g s r 一百1 s t 玩s 妒 s 2 r 9 t l s n 尸一s 譬 s n 7 口t s 7 一s j 1 s n p 8 2 r t b k s 譬p s 2 由于鲰 卫 故对i 及充分大的k 有s 带 s 蒜 由文 6 中 4 5 式 对i 1 l s 孑一s 磊i d i s t x k s n k i 6 4 o 1 1 4 i i 咖 t 2 p 1 茎o 1 1 9 1 1 5 t 2 一 下面估计鲰 i s n p 一5 如 0 a 的大小 当i 五时 不妨设曩 吼 g 牙 0 则对充分大的女 玑 0 从而 如 i g 柳一 如果x k i 8 以 0 l i 则s 孑 s 怨 如果 n i 彰 n b 则 乳 s 怨 o i 于是 珊 t 8 n p s 铱 g k i 吼一 i i s 蒜 g k t 一d k 厂s 以 i 一九j s 2 i 一2 e d k i s 蒜 2 2 e 丸k i s 嚣 2 e i 2 d k 4 e t 2 d k i 2 呶 一2 一2 如 筇n l 一 s 为 2 互e d k i t s n 2 焉一 以 m 溯 畿 s 桫 s 苁 2 1 8 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛性 对i 由 二阶连续可微及文 6 中 4 5 式 因此 g k l g i x 一吼 牙 o 1 1 矾一i 1 o 1 扣枷 so 1 1 0 1 1 妒 g p 妒 s 2 蠢 s 2 p s s t b k s p s s n p 8 t 凤 s n p 8 曼 g k 删n j p s 磊 e 蜘 t s 带一s 蒜 拒五 i e n 日i l s 2 r i s j 2 r p s 1 l 百1 x e l l s n p a n l i i 2 州s 譬 毛薏k n e 2 o 1 1 蟊1 1 州叫印h 1 s 譬 蚤n 菰e k i s 蒜 2 1 1 蟊1 1 唧卅1 觚tn 互1 s g t 玩3 i 1 s t 畴1 风 n 驯酬面n 2 力 1 g t a n b r 互1 s j 2 r t q k s o i i 靠 1 4 缸 2 p 1 也 s o 1 i 彘1 i 2 p 1 注意到对充分大的k 一也 譬 一瓢t nq 1 n t 仇s i f q 如 一互1 一q 1 蜘 t 仇 一q 托 i 靠瓴 1 9 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四 局部收敛性 d 1 肌 t d i q d 1 一1 d 1 鲰 g k d k l q d 一t 颤 a m i n 壤1 饥d 一t 甄l l z 1 l i 饥1 1 2 2 a 磁1q d 一三型 2 1 l d 饥磋1 l 一三 倒 2 1 1 磁1 b d b 1 l 慨1 1 2 2 g x o x e 其中a 幽 珑1 瓴d 一 是 d i 镳d 一 的最小特征值 a 磁1 q d 是d k l q e d 的最大特征值 则有 妒七 o 一妒 s g p 一妒七 s g 一o 1 i 委 l l m l 玎弘伊 1 孺磊1 而一啪t 一2 9 蚓 2 再由慨 斗o 令保p 2 瓦函去干面 引理得证 定理4 1 在假设 a s 3 1 a s 3 2 a s 4 1 a s 4 2 下 序列 是r a i n 2 p 阶收敛到牙 证由定义 8 r e d s 女 一p r e d s l i 0 一 z s k 一 妒 o 一妒 s b i i f x k t s 一 茁 一9 暑s t 一 f l y 2 z t s t l 荟1 s t 女v 2 s s 互1 s 暑v 2 z s 1 扣 1 1 2 i v 2 他e 幺s e 一v 2 m 矾 2 0 简单界约束优化的仿射尺度内点信赖域算法的收敛性 四局部收敛睦 其中靠 o 1 由引理4 2 对充分大的k 及氟 s 盯 s j 2 尸 有 而 于是 p r e d k s e 妣 o 一 i l k s k 寸2 妒k o 一妒 s p 7 2 g 如l 1 1 2 s ij 盯t l i s 尸i i i l s p i isi i s 冶一t1 1 氨 l l 裂 l l 竺 生堕l 丝 生鱼 j p r e d k s k 壤一 恢1 1 2 i i v 2 f x k 矗s 一v 2 z t i i i 面翮孤r 一 一堡 j 里 坐 垒塑 二 f 塑型 由v 2 局部l i p s c h i t z 连续 有h 一1 1 o k o 故对充分大的k n 仉 即对所有充分大的意 乳 吼s 扩都是成功迭代 由文 6 中定理5 知 z e 是r a i n 2 p 阶收敛到蜃 简单界约束优化的仿射尺度内点信赖域算法的收敛性 五数值试验 第五章数值试验 文 6 给出了如下数值例子 m i n z 可 一 茹2 一y 2 一z 2 51 s t 0 z ys 1 在问题 5 1 的解矿 o o 处 严格互补条件不成立 本章利用算法2 1 编 写了m a t l a b 程序 从不同初始点进行数值试验 选取参数 盯 o 9 9 9 5 p 2 1 a m 口 5 l o 1 驰 o 7 5 信赖域半径的修正准则 l0 2 5 a 1 k 轮 使用m o r 6 方法 见1 9 l o 求解子问题 当迭代靠近解时 子f 曰题的解等价 于牛顿步 终止准则 r e s i i d k a k l 1 0 1 0 x 0 1n i t 分别为初始点和迭代次数 计算结果列于表一 简单界约束优化的仿射尺度内点信赖域算法的收敛性五数值试验 x 0 n i tol2345 o 1 0 1 r 尼s8 8 e 一25 0 e 一53 5 五 9 1 8 b 1 7 0 2 0 2 r e s1 5 8 11 o l 41 4 b 8 2 8 e 1 6 0 3 0 3 r e s1 7 e 17 7 e 1 23 3 e 1 38 1 e 61 3 e 1 1 06 5 b 1 7 o 4 0 4 鼬s1 5 e 13 2 d 2 1 2 e 一32 9 e 62 3 e 一1 1 0 5 0 5 r e s1 3 e 一11 7 星 2 2 4 e 1 49 o b 一81 3 e 一1 4 0 6 0 6 r e s 1 9 b l1 9 e 35 4 b 61 8 e 一1 1 0 7 0 7 r e s2 5 b 11 3 e 1 1 g 9 e 一21 9 e 一12 5 e 1 2 1 1 王 3 0 8 0 8 r e s2 5 e 一1 2 2 e 一43 2 e 87 4 e 1 6 0 9 0 9 r e s1 7 e l1 1 8 4 7 9 b 90 0 e o 从表一可见 算法对跏 o 7 o 7 因尝试步过小而没有正常终止 其它情形 都很快收敛 简单界约束优化的仿射尺度内点信赖域算法的收敛性参考文献 参考文献 1 b r a y t o nr k c u l l u mj a na l g o r i t h m f o rm i n i m i z i n gad i f f e r e n t i a b l ef u n c t i o n s u b j a c tt ob o x c o n s t r a i n sa n d e r r o r s j o p t i m t h e o r ya p p l 1 9 7 9 2 9 5 2 1 5 5 8 2 c o l e m a nt f h u l b e r tl a ad i r e c ta c t i v es e tm g o f i t h m f o rl a r g es c a l es p a r s e q u a d r a t i cp r o g r a m sw i t hs i m p l eb o u n d s m a t h p r o g 1 9 8 9 4 5 3 7 3 4 0 6 3 c o l e m a nt f l iy o nt h ec o n v e r g e n c eo f i n t e r i o r r e f l e c t i v en e w t o nm e t h o d s f o rn o n l i n e a rm i n i m i z a t i o ns u b j e c tt ob o u n d s m a t h p r o g 1 9 9 4 6 7 1 8 9 2 2 4 4 c o l e m a nt f l iy a ni n t e r i o rt r u s tr e g i o na p p r o a c hf o rn o n l i n e a r m i n i m i z a t i o ns u b j e c tt ob o u n d s s i a mj o p t i m 1 9 9 6 6 4 1 8 4 4 5 5 c o r ma r g o u l dn i m t o i n tp h l g l o b a lc o n v e r g e n c eo f ac l a s so ft r u s t r e g i o na l g o r i t h m sf o ro p t i m i z a t i o nw i t hs i m p l eb o u n d s s i a mj n u m e r a n a l 1 9 8 8 2 5 4 3 3 4 6 0 6 h e i n k e n s c h l o s sm u l b r i c hm u l b r i c hs s u p e r l i n e a r a n d q u a d r a t i cc o n v e r g e n c e o fa l t l n e s c a l i n gi n t e r i o r p o i n tn e w t o nm e t h o d sf o rp r o b l e m sw i t hs i m p l e b o u n d s w i t h o u ts t r i c tc o m p l e m e n t a r i t ya s s u m p t i o n m a t h p r o g s e t a 1 9 9 9 8 6 6 1 5 6 3 5 f 7 3 l e s c r e n i e rm c 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 s