（应用数学专业论文）有界约束半光滑方程组的信赖域方法.pdf

中文摘要 摘要 半光滑概念是光滑概念的推广，光滑可以说是半光滑的特殊情况。所以，研究具有 半光滑性质的非线性系统问题并提出一种具有总体收敛性的算法将具有更为一般性的意 义。本文主要分析研究在不同的范数意义下，分别使用仿射投影技术和内点回代法结合 信赖域策略来解决有界约束非线性半光滑方程组问题。 在最流行的信赖域方法中，如何鼹决信赖域子闻题是一个菲常值得研究的闻题，特 别是仿射内点信赖域问题。而不同范数的选取直接关系到信赖域子问题的构建、柯西点 的性质和算法的核心运算。本文研究无穷范数和欧氏范数这两个常用范数意义下的仿射 尺度信赖域方法。无穷范数意义下，基于简单有界约束的非线性优化问题构建信赖域 子问题，莉用半光滑类牛顿步在可行域投影得到投影牛顿的试探步，获得搜索方向。 在d e n l l i s m o 一条件下证明，在正则解附近，信赖域算法转化为投影牛顿算法。这既保证 了算法的全局收敛性，也得到了算法的局部超线性收敛速率。欧氏范数意义下，基于简 单有界约束的非线性优化问题构建信赖域子问题，但所用的最小仿射尺度比c o l e m a n - l i 所 用的仿射尺度更为一般。在没有严格互补假设条件下，本文所提供的最小仿射尺度，可 给出更强的全局收敛性结果。 线性搜索方法和信赖域方法是保证最优化问题的整体收敛性的两种基本策略。本文 研究与分析如何结合贾种技术，使用菲单调线搜索与信赖域簧略结合来处理，不仅使算 法具有整体收敛性，而且克服高度非线性的病态问题。对欧氏范数意义下的仿射尺度内 点信赖域算法，利用数学软件m a t l a b 编程进行数值实现，表明所提供算法的有效性和可靠 性。 全文共分六章。第一章简单介绍最优化的一些基本理论和概念。第二章介绍部分半 光滑理论。第三章和第四章分别在无穷范数和欧氏范数意义下提出投影信赖域方法和仿 射尺度内点信赖域方法。在合理假设条件下，证明算法的全局收敛性和局部超线性收敛 速率。第五章给出欧氏范数意义下算法的具体数值试验结果，表明了算法的可行性和有 效性。最后，第六章对本文工作进行总结，同时提出了进一步的研究方向。 关键词：有界约束；半光滑方程组；仿射尺度；信赖域方法；非单调线搜索。 第1 页 英文摘要 a b s t r a c t h lm i sp 印e r w ed e v e l o p 卸da l l a l y z eac l a s s0 f 缅n es c a l i n g 仉璐t - r e g i o nm e l o d si n 硒- s o c i a t i o nw i t l ln o n m o n o t o n ei i 她r i o rb a c l c t r a c k i n gh 鹏僦h l l i q u ef 6 rs o l v i n gb o u n d c o n s 位a i n e d s e n l i s m o d t l le q u a t i o n s a ni m n 彻tp m c t i c a la ：印e c to f 仉l s t r e g i o nm e t l l o di st l l es h a p e0 ft l l e 们l s t 陀舀6 ni t s e l f ， w h i c hi sd e t 州n e db yt l l en o 珊邯c di ni t ss 州l e m n ec h o i c eo fn o r n lm a yh a v eas e r i o u s h p a c to nn l ec o r ec o m p u t a t i o n s ，m en a n 聆0 ft l l ec a u c h yp o i n t 觚d l ( x l e li i l i i l i i i l i z e r 舔w e l l h lo l l re x p e r i e n c c ，w ec h 0 0 j a n d ；2n o 加晦i no u r 咖s t - r e 舀o nm e m o d s t h ez 一n o m l 仇j s t - 蟛i se a s yt 0u s e ，嬲ap o i n tm a y b ec h e c k e dc o m l 娜e n tb yc o m p o n e n tt 0s e ei fi tl i e si n 也er 锷如n s o ，i n 也ei o o n o m l 仇l s t r e 垂o np r o b l e n i w ep p o s eaw a yo fc o m p u 矗n gt r i a ls t l 叩s b yas e “s m 0 0 ln e ：咖n - l i l 【cm e t h o dt l l a ti s 嬲g m 朋砌b yap 删e c t i o n0 n t 0t l l ef e 硒i b l es e t u n d e rad e n i l i s m o 厄- t y p ec o n d i t i 蚰，w ep i u v et l l a t ，c l o t 0ab d 他g u l 盯s o l u t i o n ，吐l e 蜘峪t - r e g i o na 1 9 0 r i m mt i l m si n t ot h i sp 删e c t c dn e 、矾o ni i 把m o d ，w l l i c hi ss h o w nt 01 0 c a lq s u 删i n e 盯 c o n v e 略e t h ez 2n o 肌i sn o t 嬲e 硒y t 0a p p l y b u th 弱as 臼o n gt h e 嘣i c a la d 蛆t a g ei nm a tn l e 陀 a r ep r 0 v a b l ye f j f i c i e n tm e t l l o d sf o rl i l i n i 血五n ggw i n l i n 觚如觚s tr e g i o n s 0 ，i n 恤n s eo f 如 n o m ，w ed 嘶n em em l s tr e g i o ns u l ) 】呻b l e mb ym i n i m i z i n gas q u a r e di 沁d i d e 趾n o mo fl i n e 盯 m o d e lw i man e wa f j f i n em 撕xc a l l e dl i l i i l i m m n s c a l i n g u n d e rar e a s o n a b l e 勰s u m p t i o no fn l i s n e wa f ! 丘n e s c a l i n gm 撕x ，w es 缸e s s l a tm el i l i t i i m u m s c a l i n gh 硒s o m ea d d i t i o n a lp r o p e n i e s 1 a t a l l o w su st 0p r o v es 仃0 n g e rg l o b a lc o n v e 曙e n c er e s u l t st h 趾f b rt l l ec o l e i i 姗一l i - s c a l i n g b o ml i n es e a r c ha i l d 仇l s tr e 百o na l g o r i m ma 他w e l l a c c 印t e d 伧t l l o d si nt l l e 叩t i i i l i z a t i o n 幻弱s u r e 甜o b a lc 0 i i v 哪e n c e h 也i s 弘l p e w ec o n s i d e rh o wt oc 砸b i n em en o n m o l l o t 衄el i n e s e a r c hw 地仃u s tr e g i o ns 仃a t e g ) r 觚du s em e mt 0e n 呲t t l e9 1 0 b a lc o n v e 唱e n c e 锄ds p e e du pt l l e c 伽【v e 堵e n c ep r o g r e s si nt l l ec o m o u r s0 fo b j e c 石v ef u n c t i o nw i t l l1 a 玛ec l l r v a n j r e k e yw b r d s ：b o u n dc o n s 垃a i n t s ；s 锄i s m o o 也e q l l a 垃o n s ；a 伍n es c a l i n g ；t n l s tr 9 9 i o nm e 也o d ； n o n n l o n o t i d n el i n es e a r c h 第1 i 页 主要符号对照丧 i 主要符号对照表 n 维实向量空间 n m 维实矩阵 e c ；i l c l i d 范数 o o 一范数 礼维决策变量 向量z 的第j 个分量 目标函数的局部极小值点 目标函数 在当前迭代点瓢处的函数值 日 半光滑向量值函数 q 可行集 i n t ( q ) 严格可行集 v ，( z )，在。处的梯度 ( z ，)，在z 处的方向导数 ( z ) 雅可比矩阵 如，( z ) b 次梯度 甜( z )函数，在点z 的c l a r l ( e 广义雅可比矩阵 x ( z ) 临界准贝i j 忍 有界约束q 上的投影 甄 目标函数在z 七处的局部二次近似 七 信赖域半径 c ( z o ) = z 9 p i 危( z ) ( z o ) ) 水平集 第1 页 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名： 论文使用授权声明 日期：f s 7 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 储躲孔确新躲 日期：p 曲思；1 第一章最优化理论基础 第一章最优化理论基础 1 1 最优化问题简介 最优化理论与方法是一门应用性和综合性都很强的学科。近年来，随着电子计算机 的普及以及优化计算方法的迅速发展，最优化技术在国民经济的许多领域( 如国防、工 农业生产、交通运输、金融、贸易、管理等) 的实际应用日益广泛。所谓最优化就是研 究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优 方案。为应用最优化技术确定最优方案，需要针对具体的实际问题建立相应的最优化模 型。 最优化问题的数学模型一般形式为： m i n ，( z ) 8 t c ( z ) = o ，t ( 1 1 1 ) c ( z ) 0 ，t z 其中z = ( z 1 ，勋，z n ) t 舻，：舻一鸵1 ，c ：咿_ 驼1 。z 称为决策变量，仕) 为目 标函数，q ( z ) 为约束函数。和z 分别是等式约束的指标集【1 ，2 ，仇) 和不等式约束的 指标集 m 十l ，m + 2 ，p ) 。定义集合q 为 q 磐 ziq ( z ) ；o ，l ；q ( z ) o ，i 2 ) ( 1 1 2 ) 则称q 为约束集合、约束区域或可行域。若z q ，则称为可行点或可行解。当不要求不 等式约束等号满足时，可行域成为“严格可行域一，即( 1 1 1 ) 的严格可行域为： m ( q ) 磐 zic ( z ) = o ，i g ；q ( z ) o ，i z ) ( 1 1 3 ) 对于一个可行点z ，所有的等式约束都被认为是有效约束。考虑不等式约束c ( z ) 0 ，如果有q 0 ) = 0 ，就称约束q 扛) 0 在点z 是有效约束或起作用约束；如果有q ( z ) 0 ，就称不等式约束c ( z ) 0 在点z 是无效约束或不起作用约束。如果所有的不等式约束 都是不起作用约束，就称z 是可行域的内点。 若模型( 1 1 1 ) 中不含约束条件，即q = 舻，称模型( 1 1 1 ) 为无约束优化问题，无约束 优化问题是在空间舻上寻求使目标函数，( z ) 达到极小或最小的点矿。 若模型( 1 1 1 ) 中含有约束条件，即称模型( 1 1 1 ) 为约束优化问题，约束问题是在约束 集q 上寻求使达到极小或最小的点矿。 若模型( 1 1 1 ) 的目标函数，( z ) 和约束函数q ( z ) 都是线性函数，则称模型( 1 1 1 ) 为线性 规划。若，( z ) 和c ) 中至少有一个是非线性函数，则称模型为非线性规划。特别地， 当，( z ) 为二次函数，c f ( z ) 为线性函数时，则称模型为二次规划。 第l 页 1 2 最优性条件 1 2 最优性条件 最优性条件是指最优化问题( 1 1 1 ) 的最优解( 局部的或全局的) 所必须满足的条件。 它不仅对于最优化理论的研究具有重要意义，而且对最优化算法的设计和终止条件的确 定起重要作用。本节将简单地介绍常用的一阶和二阶的最优性条件。 定义1 2 1 诳q ，4 ( 矿) 是起作用约束集，如果或者所有的k ( 矿) ，t 4 ( 矿) ) 都 如的线性函数，或者 v q ( 矿) ，i 4 ( 矿) ) 线性无关，则称问题( 1 1 1 ) 具有线性无关约束 品性 为了更方便地讨论约束优化问题的局部极小点的最优性条件，引入约束优化问 题( 1 1 1 ) 的l a g 啪g e 函数： p l ( z ，入) = 他) 一九c ( z ) ， ( 1 2 1 ) t = 1 其中入称为l a g 锄g e 乘子。 下面先给出最优解的一阶必要性条件。 定理1 2 1 设矿q 是问题( 1 1 1 ) 的局部最优解，若在矿点线性无关约束品性成立，则存 在向量 = ( 入i ，k ) t ，使得 v $ 三( 矿， ) = 0 ， x 0 ，t z n q ( 矿) = o ，i z ( 1 2 2 ) ( 1 2 3 ) ( 1 2 4 ) 定理1 2 1 通常被称为l ( a m s h k l l l m n c l 澍( 简称k k - ，i ) 定理，( 1 2 2 ) 一( 1 2 4 ) 称为问 题( 1 1 1 ) 的一阶必要性条件或k k - t 条件。满足此条件的点称为k l l l l n r i 、l c l 【e r 点或k - k - t 点。( 1 2 4 ) 式称为互补松驰条件。如果对任意i z ，n 和色( 矿) 中有且仅有一个取零值， 则称为严格互补松驰条件成立。 由于无约束最优化问题中无任何约束条件，由定理1 2 1 立即可得无约束最优化问题 最优解的一阶必要性条件为 v ，( 矿) = o 下面我们讨论最优解的二阶最优性条件。首先，假定在点矿处严格互补松弛条件成 立，并给出二阶必要性条件。 定理1 2 2 设矿q 是最优化问题( 1 1 1 ) 的最优解，且函数，( z ) 与q ( z ) ， = 1 ，2 ，p 二阶连续可微又设定理1 2 1 中的约束规范条件在点矿成立，从而存在l a 乒a i l g e 乘子向 量”使k k t 条件成立设严格互补松弛条件在矿成立，则有 ，v ：霉l ( 矿，”) 3 o 第2 页 第一章最优化理论基础 对- 切满足 ，v c t ( z + ) = o ，t 4 ( z + ) 的方向s 均成立其中，v ：霉三( 矿，”) 是l 唧g e 函数在( 矿，”) 处关于z 的二阶偏导数矩 阵 下面的定理则给出最优解的二阶充分条件。 定理1 2 3 设最优化问题( 1 1 1 ) 的函数，( z ) 与c i ( z ) ，t = 1 ，2 ，m 均二阶连续可微设对 于可行点矿存在l a 伊卸g e 乘子向量 使k - k - t 条件成立若对所有满足 s t v q ( z ) = o ，i 4 ( z + ) 的非零向量s 有 s t v 免l ( 矿，”) s o ， 则矿是问题( 1 1 1 ) 的一个严格局部最优解。 1 3 最优化方法的结构 最优化方法通常采用迭代方法求解问题( 1 1 1 ) 的最优解。其基本思想是：给定一个初 始点z o 舻，按照某一迭代规则产生一个逐步改善的迭代序列 z 七) ，使得当_ 瓢) 是有限 点列时，其最后一个点是k _ l 点；当 矾) 是无限点列时，其任意一个聚点是k - k t 点。 根据最优性的一阶必要条件，最优解一定是k - k - t 点，因此理论上由迭代法所确定的解一 般是k k t 点，再由方法的其他一些特性，如下降性可以确保所得的k - k - t 点是所论问题 的最优解或近似最优解。 最优化问题求解的基本迭代格式如下： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定一个初始点跏，置尼0 ； 2 如果瓢满足对最优解估计的终止条件，停止迭代； 3 按某一规则构造搜索方向巩； 4 确定步长口七( 对于某些算法口七三1 ) ； 5 得到最优解的一个更好的估计点z 知+ 1 = 孤+ 口七陬，置七七+ l 后转步2 在上述迭代法的基本格式中，关键的两步是构造搜索方向m 和确定步长口奄。不同的 搜索方向m 和不同的步长因子q 构成了不同的算法。其中，线搜索策略和信赖域策略是 保证最优化方法整体收敛的两类技术 一个好的算法应具备的典型特征是：迭代点z 七能稳定地接近局部极小值点矿的邻 域，然后迅速收敛于矿。因此，收敛速率也是衡量最优化方法有效性的重要方面。设算 法产生的迭代点列 ) 在某种范数意义下收敛于矿，即 - l i mi i z 知一z 。i l = 0 ( 1 3 1 ) 糟+ o o 第3 页 1 4 信赖域方法 若存在实数a 。0 及一个与迭代次数七无关的常数g o ，使得 熙酬= g ( 1 3 2 ) 七一l l z 七一z i i “ 。 则称算法产生的迭代点列 ) 具有q q 阶收敛速率。特别地， ( 1 ) 当口= 1 ，o 口 1 时，迭代点列 矾) 具有q 线性收敛速率： ( 2 ) 当1 o ，o 仇仡 1 ，o 饥 1 7 2 ，置南o ； 2 如果鲰，停止迭代； 3 ( 近似) 求解子问题( 1 4 1 ) 得到s 知； 4 计算，( z 七+ 鼠) 和风令 撕- = s 幻茹? 劲1i ， 古贝q 5 校正信赖域半径。令 知+ 1 ( o ，饥七】，m 0 ，g v 0 ，使得对所 有y 如日( 可) ，怙一z i i g ，y 都是非奇异的，且0 y _ 10s 进一步，如果日在z 处是 半光滑的，则存在6 o ，e o ，使得对所有可舻，恼一z i i 6 ，有 日( 可) 一日( z ) i i ( 1 l 可一z l i ( 2 2 3 ) 2 3 半光滑投影类牛顿方法 2 3 1 投影类牛顿算法 本节介绍m i c h li j l m c h 【2 0 】给出的半光滑投影类牛顿方法。考虑有界约束非线性半 光滑方程组 日( z ) = 0 ， l z 牡( 2 3 1 ) 第8 页 第二章半光滑理论 构建非线性优化模型 m i n ( z ) ， s t z z ， 其中， ：u 一虢，九( z ) = | 1 日( z ) f 1 2 2 ，| i i i 为欧氏范数。 由于q = 【f ，t 】是有界约束，因此可简单定义投影为 忍( z ) = m a x z ，n l i n z ，钍) ) 下面建立算法。 算法2 3 1 ( 投影类牛顿迭代) 1 选取初始点z o ，置七仁0 2 如果日( 孤) = o ，则停止迭代 3 选取非奇异矩阵地g p 加，并通过求解下面的方程得到类牛顿步s j 2 r 4 计算s 在q 一钒上的投影 s j 2 r = 一日( z 知) s 暑= r ( z 七+ s ：2 r ) 一z 七 5 令z 七+ 1 = 钆+ s p ，置七譬忌+ 1 ，转步2 2 3 2 收敛性分析 本节给出半光滑投影类牛顿方法的局部收敛性分析。 定理2 3 1 假设半光滑函数日：u - 渺局部l i p s c l l i t z 连续。令牙x 是日( z ) = o 的一个正 则解，且令0 黝一刮和6 0 充分小假设算法不是有限步终止，且对所有的后有 纵2 y 露殁珀l i ( 一y ) s 钏驯s 2 r l l ( 2 3 2 ) 则有 z 惫) 收敛到牙。 进一步，如果有 恕渤划， ( 2 3 3 ) 则序列 吼) 超线性收敛到牙 证明：首先，由局部l i p s c l l i t z 连续，牙的b d 正则性及正则性引理2 2 4 ，得：存在 0 ，工 o 和c v o ，使得日在统( 牙) = 扛；忙一列e ) 上l i p s c l l i t z 连续，且有 y 一10 c v ，v y 如日( z ) ，v z 臃( 牙) 。 ( 2 3 4 ) 第9 页 2 3 半光滑投影类牛顿方法 任取瓢毽 ) ，令k 如日 ) 满足鲰= i f ( 地一k ) s i f 。定义 d 知= z 七一孟，e 奄= z 奄+ s 牙 如果j 1 ( 2 仇) ，则有 | l s 2 r l l o 且0 z o 一引l 充分小时，序列【) 收敛到牙。 进一步，如果( 2 3 3 ) 式成立，则由引理2 2 2 ，( 2 3 4 ) 式，及( 2 3 7 ) 式，可 得e 七与o ( 1 | 以l i ) 同阶。又由( 2 3 9 ) 式，即得算法的超线性收敛速率。证毕。口 第1 0 页 第三章半光滑投影信赖域方法 第三章半光滑投影信赖域方法 3 1引言 本文考虑有界约束的非线性半光滑方程组： 日( z ) = o ， z q ( 3 1 1 ) 其中，q = 【l ，川= z 舻池戤地，i = 1 ，钆 ，日：咿) u _ 舻是定 义在包含可行集q 的开集u 上的函数。假定上下界f 跪u 一o 。) ，地跄u + ) 满 足如 0 是与七无关的常数。 考虑用第二章的投影类牛顿迭代求解信赖域子问题( 3 1 3 ) ，得到可能试探步。若该步 满足可行性条件( 3 2 2 ) 和下降性条件( 3 2 3 ) ，则该步为解子阿题( 3 1 3 ) 所得的试探步；否 则，重新计算试探步满足条件( 3 2 2 ) 、( 3 2 3 ) 。进一步，由于( 3 2 3 ) 较为抽象，对其进行 改进，用下面的柯西下降条件【2 0 】来替代 吼( s 知) 口饥( s 譬) ，( 3 2 4 ) 其中，a ( o ，1 ) 为一常数。柯西步s 暑由下面的优化问题求得： n l i n 吼( s ) s t s = 一t d ( 钆) 研鲰，亡o ，s q 奄 ( 3 2 5 ) 其中，y 1 是固定的，仿射对角阵d ( z ) 舻竹定义为 f l i n k d ，戤一如) ， 如果( v ( z ) ) i o ； d ) “= l i n k d ，一z i ) ， 如果( v ( z ) ) i o 为一个常数。在可行域q 上定义x ，使得对某个常数傀 0 ，成立 岛x ( z ) x a s ( z ) = l i d ( z ) 7 v 九( 。) 1 1 ( 3 2 6 ) 第1 2 页 第三章半光滑投影售赖域方法 下面给出引理3 2 1 ，表明当柯西下降条件( 3 2 4 ) 成立时，( 3 2 3 ) 也成立。 引理3 2 1 ( 【2 0 】) 令x 满足( 3 2 6 ) 假设序列 氟】- 有界，即小于等于某一常数c k ，则存在 只依赖于口，风，y ，k d 和c k 的常数忍 o ，使得：如果x ( 巩) 0 ，且试探步s 七满足柯西 下降条件( 3 2 4 ) ，则( 3 2 3 ) 也成立 在确定了临界准则，解决了信赖域子问题求解的基础上，建立投影信赖域算法如 下。 3 2 3 投影信赖域算法 1 初始化：选取参数叩1 ，7 7 2 ，p ( 0 ，1 ) ，且? 7 1 调参数c ，令m ( o ) = 0 选取临界准则x ) ， 置忌e0 p ，n i i n 0 ，选取某一正整数为非单 z o 凰，o2 n l i n ，非奇异矩阵 2 计算瓢：= x ( 瓢) 如果瓢= o ，则停止计算，瓢为最优解；否则转步3 3 计算投影牛顿步s 暑。 3 1 通过求解 磊s 擘= 一日( ) ，得到类牛顿步s 謦 3 2 计算投影牛顿步s 暑：= r 。( 8 掣) 3 3 如果s 满足条件( 3 2 3 ) ，则令s 奄：= s 暑；否则，转步4 4 通过求解( 3 2 5 ) 得到s 譬计算s 知满足( 3 2 2 ) 式和( 3 2 4 ) 式 5 选取钒= 1 ，u ，u 2 ，直到第一个u k 满足： 危( z 膏+ 口知5 七) ( z l ( ) + a p v 九( z 詹) t s 七 ( 3 2 7 ) 其中， ( 铆( 功) 2 。g 蠹 危( z 膏。) ) ，o m ( 七) m m m ( 七一1 ) + 1 ，g ) ，七l 令z h l 2 z 知+ q 奄s 七 6 计算矶： 则 r 触e d k ( q 奄s 知) 型 ( z l ( 七) ) 一危( z 七+ a 知s 知) ， p r e d 七( 蚶七) 磐一鲰( q 觑) = 一( a 蠡v ( 瓢) t s 知+ 翱i 尥珊) ， 班磐脚胁) = 裂 7 计算新信赖域半径詹+ l ：钔 伽 饥 p 。 由非单调线搜索技术( 3 2 7 ) 及相对实际改变量的定义，有 又由 r j a r e d 知( 口知s 七) = ( z l ( 知) ) 一九( 。k + a 知s 知) 一a 七p v ( z 蠡) t s 知 ( 3 2 9 ) o p r e d 知( 蝴七) = 一吼( 蚶七) = 一( 口奄v ( 孤) t s 知+ 三q ；i l 尥珊) 一口南v 九( z 知) r 舰， ( 3 2 1 0 ) 得到 m = 警裂三芝黯= p c 3 2 ， 所以，为使算法执行有效，必须保证，7 1 卢。同时，也可看到，非单调线搜索技术在信赖 域中的运用可克服高度非线性带来的计算困难。 3 3 全局收敛性分析 本节将给出所提供算法的全局收敛性证明。首先，在假设( a 1 ) 、( a 固成立的前提下， 再给出一些常见假设： 假设a 3 水平集c ( z ) = z 舻i ) 九( 勋) ，zsz u ) 有界。 假设a 4k 近似阵 靠按范数一致有界。 假设a 5 函数九：渺_ 敬在水平集( z ) 上下有界。 首先，类似【2 0 】，估计比值m 的值。 引理3 3 1 假设( a 1 ) ( a 5 ) 成立若巩，o 知s 七，知等是由算法3 2 3 产生的如果x 如) 0 对z q 成立，则对卵( o ，1 ) ，存在 o ，艿 o ，若i l 钆一圳6 ，七s 满足， 则下式成立： m 7 7 ( 3 - 3 1 ) 证明：因为x ( z ) o 是连续的，所以存在6 o ，g o ，当瓢满足l | 一z i l 6 时，x ( ) 第1 4 页 第三章半光滑投影信赖域方法 成立。现在，取o o ，若l i 瓢一。i i 6 ， s 满 足，则有 a 詹 ( 3 3 8 ) 证明：假设结论不真，则对任意z 满足忙七一圳6 ，知s ，有q 知 毒成立。类 第1 5 页 3 3 全局收敛性分析 似引理3 3 1 的证明， 取o m i n 1 ，s ) ， 由x ( z ) o 的连续性，得：对0 瓢一圳6 ，有x ( 瓢) g 成立 则对i l z 七一z l ls6 ，o ks ，可得 p r e d 七( s 知) = 咄( 乳) = 一( v 九( 巩) t s 知+ 扣尥乳1 1 2 ) 届2 x ( z 奄) m i n 1 ，奄，x ( z 七) ) 岛七 成立。结合可行性条件( 3 2 2 ) ，将其进一步转化为 v 舻聪一伪a 一箸i i s 川。 由假设q 知 危( 姐砷) + p 罟v ( ) t 双 ( z 知) + p 警v 危( 观) t 踮 ( 3 3 1 1 ) 其中，以磐 当l l z 知一z 0s 即 ：九( z 知) + p 鲁v 危( z 奄) r 乳+ ( 1 一国鲁v 九( z 知) t 乳 + 坐( v ( 孤+ 亿塑s 七) t s 七一v ( 孤) t 靠) ： ( z 七) + p 鲁v 危( ) r s 七+ ( 1 一p ) 鲁v ( z 七) r s 七+ 以 ( 3 3 1 2 ) 警( v 九( 孤+ 亿警s j c ) t s 知一v 危( z 知) t s 知) 结合( 3 3 1 0 ) 式和( 3 3 1 1 ) 式，得： 6 ，七时， ( 1 一p ) v ( z ) t s 奄 - ( 1 一p 铮s 川 ( 1 卅箸忪川 ( 3 3 “) 又由v 危( 瓢) 的局部l i p s c h 地连续性，得： 即 i 【v ( 瓤) 一v 九+ 詈s 七) n 知i 三詈恢慨己詈慨慨， ( 3 3 1 5 ) q 知( 1 一卢) 彘紫 取= 常，可得( 3 3 1 6 ) 式与假设矛盾。因此，( 3 3 8 ) 成立口 下面，给出算法3 2 3 的全局收敛性证明。 定理3 3 1 假设( a 1 ) ( a 5 ) 均成立若【瓢) c 渺是由算法3 2 3 产生的迭代点列，则 i x q 知) = o 七_ + 。o 第1 6 页 ( 3 3 1 6 ) ( 3 3 1 7 ) 一 十 p m 对 外 此 0 ，若在孟的6 邻域存在七，满 足麝，则有m ，7 2 成立。因此，在牙的6 邻域，l 七。即南值下降当且 擘当七 。，譬登立：因此，奄l i n ( k ，7 1 ) ，v 忌k 。即，1 鬯磐f 詹o 结 合( 3 3 2 4 ) 式，此时只有l i m 鲰= 0 。 荐 第1 7 页 3 3 全局收敛性分析 由于q 知是由线搜索约束( 3 2 7 ) 决定，则由线搜索准则，有警s l ，及( 3 3 1 1 ) 式 ( z 七+ 鲁甄) 一九( z 七) ( z 七+ 鲁甄) 一九( 规( 七) ) p 鲁v 危( z 知) t s 知 u ，w 又由( 3 3 2 5 ) 式及半光滑性质，对充分大的后，有 ( 瓢+ 詈s 七) 一九( 巩) = 詈v ( 钆) t s 詹+ 。( i l q 七s 知忆) p 詈v ( 钒) t ( 3 3 2 6 ) 结合( 3 3 2 3 ) ，及可行性条件( 3 2 2 ) ，对充分大的后，有 及 v 毋七一铷蚓k ( 3 3 2 7 ) o ( 1 一p ) 等v 危( z 南) t s 七+ d ( 1 l 口七& i l ) 一譬。= 云篡字i i q k s 圳+ 。( o q 知钆o 。) o ，及子序列 ，l = 1 ，2 ，使得 x ( ) 黯坛，l = 1 ，2 ( 3 3 3 0 ) 由定理3 - 3 1 ，我们有1 钽粤f x ( ) = o 。因此，存在子序列 觑t ) ，z = 1 ，2 ，使得 及 x ( z 七) ，v 盂惫 如， x 【z t j e ， v ，l = l ，z ， 类似定理3 3 1 的证明，对五后 如，由( 3 3 2 2 ) 式，及( 3 3 2 3 ) 式，可得：。 m ) 叫) 茎卯v 毋七一警q 圳训k 成立。即， v 一铷s 堋 笛18 酉 ( 3 3 - 3 1 ) ( 3 3 3 2 ) ( 3 3 3 3 ) 第三章半光滑投影信赖域方法 及 。u 码q 知恢怯= o 七一蕊知 “一 此外，对亿f o