（运筹学与控制论专业论文）优化问题中的广义模式搜索算法.pdf

大连理工大学硕士学位论文 摘要 目前，不用导数的最优化算法在实际中的应用日益广泛。本文主要针对广义模式搜 索算法进行研究。它是直接搜索算法的一种，在迭代过程中只需目标函数值信息，而无 需计算或近似任何的导数信息，不强加任何充分下降的条件，即可保证算法的收敛性j 鉴于模式搜索的这种特点，使得这种算法比较适用于那些目标函数比较复杂或导数信息 不易计算的优化问题。 本文的主要工作分为两部分：首先对文献 8 】中所给出的线性等式约束优化问题的模 式搜索算法做了进一步的分析，给出了算法的局部收敛性结果；其次是将模式搜索算法 应用于有限的极大极小值问题。取得的结果如下： 1 第二章进一步分析了文献 8 】中提出的关于线性等式约束优化问题的新的模式搜 索算法的局部收敛性。在此文献中，通过将约束问题投影到约束矩阵的零空间上，从而 降低了求解原问题的复杂程度。本文假设目标函数在孤立的局部最优点的邻域内具有二 阶连续可微的性质，并对方向集和步长控制参数附加一定的约束条件，从而证明了算法 中的步长控制参数为一阶稳定性提供了一个可靠的度量，用这个稳定性的度量分析了在 孤立的局部最优解的邻域内此模式搜索的特征。 2 第三章给出了极大极小值问题的模式搜索算法，并证明了这种算法的全局收敛性。 首先通过引入一个光滑参数，得到一个逼近原问题的光滑问题，利用模式搜索算法求解 此光滑问题，在_ 定条件保证下即可得到原问题的最优解。它不但解决了原问题不光滑 的缺陷，而且在不要求计算或近似所涉及到的函数的一阶或二阶导数信息的情况下，得 到此类问题的模式搜索算法的全局收敛性结果。 关键词：广义模式搜索；正基；极大极小值函数；光滑参数；收敛性 优化问题中的广义模式搜索算法 g e n e r a l i z e dp a t t e ms e a r c hm e t h o d sf o ro p t i m i z a t i o np r o b l e m s a b s t r a c t n o w ，m a n ya p p l i c a t i o n so fa l g o r i t h m st h a td on o te m p l o y t h ee x p l i c i td e r i v a t i v e s i n f o r m a t i o no ft h eo p t i m i z a t i o np r o b l e m sh a v eb e e nd e v e l o p e dm o r ea n dm o r e g e n e r a l i z e d p a t t e ms e a r c hm e t h o d si st h em a i nw o r ki nt h i sp a p e r ，w h i c hi sap a r t i c u l a rs u b s e to fd i r e c t s e a r c hm e t h o d st h a tn e i t h e rc o m p m en o ra p p r o x i m a t ea n yd e r i v a t i v e s ，a n dc o n s e q u e n t l yd o n o tn e e dt oe n f o r c ee x p l i c i t l yan o t i o no fs u f f i c i e n td e c r e a s et og u a r a n t e et h ec o n v e r g e n c e t h u s ，t h i sc l a s so fm e t h o d si ss u i t a b l ef o rp r o b l e m sw h e nt h eo b j e c t i v e sa r ec o m p l i c a t e do r t h e i rd e r i v a t i v e sa r ed i f f i c u l tt oc o m p u t e t h em a i nw o r ki nt h i sp a p e rh a st w op a r t s ：f i r s t ，w ec o n t i n u et oa n a l y z et h el o c a l c o n v e r g e n c ep r o p e r t i e so fp a t t e ms e a r c hm e t h o de s t a b l i s h e di n 8 】a n dt h e nw ep r o p o s et h e g e n e r a l i z e dp a t t e ms e a r c ha l g o r i t h mf o rf i n i t em i n i m a xp r o b l e m s t h em a i nr e s u l t s ，o b t a i n e d i nt h i sp a p e r , m a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2s t u d i e st 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 em e t h o de s t a b l i s h e di n 【8 】，w h i c h i sb a s e do np r o j e c t i n gt h ec o n s t r a i n e dp r o b l e mo n t ot h en u l ls p a c eo ft h ec o n s t r a i n tm a t r i x a n dt h e r e f o r es i m p l i f y i n gt h ec o m p l e x i t y i nt h ep r o c e d u r eo fp r o o f , w ea l w a y ss u p p o s e t h eo b j e c t i v ef u n c t i o nh a st h ep r o p e r t yo fs e c o n d - o r d e rc o n t i n u o u s l yd i f f e r e n t i a b i l i t yi n t h en e i g h b o ro fa l li s o l a t e dl o c a lm i n i m i z e r 。s o m ea d d e dc o n s t r a i n t sa r ee n f o r c e do nt h e s e to fd i r e c t i o n sa n dt h es t e p - l e n g t hc o n t r o lp a r a m e t e rw h i c hc a n p r o v i d ea r e l i a b l ea s y m - p t o t i cm e a s u r eo ff i r s t o r d e rs t a b i l i t y ，a n dw ea n a l y z et h eb e h a v i o ro fp a t t e r ns e a r c hi nt h e n e i g h b o r h o o do fa ni s o l a t e dl o c a lm i n i m i z e ru s i n gt h i ss t a t i o n a r ym e a s u r e 2 c h a p t e r3c o n s t r u c t san e wp a t t e r ns e a r c ha l g o r i t h mf o rm i n i m a xp r o b l e m sa n dg i v e st h e a n a l y t i c a lr e s u l t so ft h eg l o b a lc o n v e r g e n c e w ec o n v e r tt h eo r i g i n a lp r o b l e mi n t oa n a p p r o x i m a t es m o o t ho n eb yu s i n gas m o o t h i n gp a r a m e t e r ，a n dt h e np r o p o s et h ep a t t e r n s e a r c hm e t h o df o rt h ea p p r o x i m a t es m o o t hp r o b l e m ，a n dt h e r e f o r eg e tt h es t a t i o n a r yp o i n t o ft h eo r i g i n a lp r o b l e mu n d e rs o m ea d d i t i o n a lc o n d i t i o n s w h i c hm e t h o ds o l v et h e n o n s m o o t h n e s so ft h eo r i g i n a lp r o b l e ma n dg e tt h eg l o b a lc o n v e r g e n c er e s u l t sd e s p i t et h e e x p l i c i ti n f o r m a t i o nc o n c e r n i n gt h ef u - s to rs e c o n d o r d e rg r a d i e n t s k e yw o r d s ：g e n e r a l i z e dp a t t e r ns e a r c hm e t h o d s ；p o s i t i v eb a s i s ；m i n i m a xp r o b l e m s ； s m o o t h i n gp a r a m e t e r ；c o n v e r g e n c e i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包舍其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：包丝邋空函亟撞盘盛耸益 作者签名：翌燃 日期：土盟l 年月一e t 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版。可以将 本学位论文的全部或部分内容编人有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：优化问题中的模式搜索算法 作者签名： 墨熔e l 期：型年王月i e l 导师签名： 丞耋盟 1 3 期： 独2 年二王月上日 大连理工大学硕士学位论文 1 绪论 广义模式搜索算法( g e n e r a l i z e dp a r e ms e a r c h ) 的研究是本文的主要工作，它属于直 接法的范畴，在求解无约束及约束优化问题时，不仅具有直接法的优点，既无需计算也 无需精确近似目标函数的导数，且可保证算法的全局收敛性。这一理论上的保证大大提 高了人们研究模式搜索算法的兴趣，从而使其在工业和科学技术发展中得到了广泛的应 用。在此，首先简要介绍一下优化问题和直接法的有关知识和背景，以便读者对最优化 这方面有所了解，然后再对模式搜索算法的相关知识及算法结构特征做详细的阐述。 1 1 引言 最优化是一门应用相当广泛的学科，它主要讨论决策问题的最佳选择特征，构造寻 求最优解的计算方法，研究这些计算方法的理论性质和实际计算表现【l 】。最优化问题形 形色色，具体的模型多种多样，根据约束函数和目标函数的线性与否可分为两大类： 目标函数是线性函数并且约束条件全是线性等式( 或不等式) 的这一类数学规划，均 属于线性规划的范畴。它是运筹学中研究较早，发展较快，应用较广泛，且方法比较成 熟的一个分支，是辅助人们进行科学管理的一种数学方法。 而目标函数非线性或含有非线性约束的数学规划问题，均属于非线性规划的范畴。 在实际应用中，更多的问题可归结为非线性规划。非线性规划含有深刻的背景和丰富的 内容，现已发展成为运筹学的重要分支，在最优设计、科学管理、系统控制等领域得到 越来越多的应用。 由文献 1 ，2 】可知，求解一般的非线性规划问题，最直接的想法是借助微分学和变分 法、l a g r a n g e 乘子法等数学工具，通过逻辑推导和分析计算直接得到问题的解或解的表 达式，即所谓的解析方法。这种方法对一些具有特殊结构的非线性规划问题很有效。非 线性规划问题的第二种方法是实验法。它们虽然操作简单，但仅能处理低维的情况。事 实上，对于一些实际问题，人们尝试利用目标函数和约束函数在某局部区域上的函数值 信息或导数信息，构建迭代型数值解法，即从当前的一个近似解点，逐步调优来产生新 的更好的近似解点，直到不能再改进为止。这种方法对于求解工程技术中的非线性规划 问题最为典型和常见。根据迭代过程中搜索策略的确定性与否，这类方法可分为两类： 随机搜索型方法和确定性方法。 随机搜索型算法属于智能算法的范畴，是启发式算法，更适合求解组合优化问题。 目前应用比较广泛的随机搜索型算法主要有遗传算法、模拟退火算法和蚁群算法。 优化问题中的广义模式搜索算法 确定型方法根据所利用函数信息的程度分为梯度型方法和直接搜索方法。梯度型方 法在迭代过程中除了利用函数值信息外，还需要函数在当前点或已产生点的梯度信息和 h e s s i a n 阵的信息，一般具有较快的收敛速度。常见的算法有牛顿法、共轭梯度法、拟 牛顿法等。有兴趣的读者可参考文献【l ，2 】等。 直接搜索算法( 简称为直接法) 在迭代过程中主要利用函数值信息，适用于变量较少、 目标函数结构比较复杂或梯度不易计算的情形。常见的直接法有坐标轮换法【射、模式搜 索算法m 】、n e l d e r - m e a d 单纯形调优算法 7 1 等。本文第二章讨论的便是模式搜索算法在 处理线性等式约束最优化问题【8 j 中的局部收敛性质。直接法早在2 0 世纪5 0 年代就已问 世( 有关的历史回顾可参考【3 】) ，不过由于某些原因一直被优化界所忽视。直到1 9 9 1 年， 一篇带有收敛性分析的直接法( 多方向搜索算法) 的发表【9 j ，直接法才重新引起人们的研 究兴趣。“直接法”一词最早出现在1 9 6 1 年h o o k e 和j e e v e s 的论文中i l o l ，之后便成为 专指那些不需要涉及目标函数精确的梯度信息的优化算法的代名词。后来发展起来的格 子基算法l l l ，屹j 也是直接法的一种。 本文的主要研究对象就是直接法中的模式搜索算法。一般的直接法单纯利用目标函 数值，而没有很好的考虑目标函数的光滑性这一优势，从而导致直接搜索法的运算量较 大，由于没有统一的结构，有些收敛性结果也不易得到p 1 。模式搜索算法则不同，它是 直接法中具有相同结构的一个子集族，不仅具有直接法的优点：构思直观，迭代比较简 单，编制程序也容易实现，对于变量不多的问题，能够收到较好的效果；更为重要的是， 在迭代过程中，模式搜索在不要求目标函数值充分下降的条件下，得到了类似于非精确 线搜索【1 2 1 3 】和信赖域【1 , 2 1 方法的全局收敛性结果。这种算法实施的可能性在于，模式搜 索算法产生的迭代位于一个具有一定大小的移动的整格中，从而可以放松对步长接受准 则的要求，而通过在步长形式上附加更强的条件来达到收敛的目的 4 1 。模式搜索算法能 够在一个点的邻域内准确地对目标函数进行抽取，因此能够鉴别一个“好”的方向，即 沿此方向目标函数值有实质性的下降。 1 2 广义的模式搜索算法 广义模式搜索算法( g e n e r a l i z e dp a r e ms e a r c hm e t h o d s ) 是直接搜索法中的一个特 殊的子集族。此算法主要是在特殊的方向集上抽取目标函数，通过比较目标函数值的大 小，找出下降方向进而解决优化问题。g p s 算法无需计算或精确近似任何的导数，也无 需计算或近似任何的惩罚因子或l a g r a n g e 乘子信息，不强加任何充分下降的条件，仍然 可以得到算法的收敛性。 大连理工大学硕士学位论文 1 2 1 模式搜索算法的背景与基本思想 模式搜索算法( p a t t e r ns e a r c hm e t h o d s ) 最初是h o o k e 和j e e v e s 于1 9 6 1 年提出来的【旧j ，用 来求解非线性目标规划问题。1 9 9 7 年，v i r g i n i a t o r c z o n 将原始的模式搜索算法加以推广， 发展和总结了直接法中的一个特殊的子集族，给出了广义模式搜索算法的抽象定义，尤其 是对这类算法的全局收敛性的证明，大大提高了人们对这种方法的研究兴趣。直观上来讲， 模式搜索算法与一般的直接法的不同在于，它在其搜索过程中均使用具有某种“模式”的 试验点，而这种“模式”与目标函数无关，这种非正规的想法是模式搜索的一般性定义的 基础。 形式上 4 1 ，模式搜索算法要求存在一个网格丁，使得如果“，x 是由模式搜索算法 产生的前n 个迭代点，则必存在一个参数因子矽n ，使得步长 x ，一x 0 x ：一x ，x 一x 一。 都落在参数网格九t 中。网格丁由迭代点及r ”空间( 约束问题中为可行域) 的正跨越集 ( 见定义1 1 ) 生成【1 4 1 ，它依赖具体算法所定义的搜索模式以及步长控制参数的最初选择， 但不依赖目标函数，从而不需要函数值的充分下降就能得到算法的全局收敛性结果，而不 用满足像线搜索中的a m i j o - g o l d s t e i n w o l f e 步长规则或信赖域方法中的柯西下降条件 或最优下降条件。关于模式搜索算法的具体的发展历史可参考【4 ，1 4 ，1 5 】中的介绍。 模式搜索算法主要利用有限个具有合适的下降性质的方向进行迭代。在无约束的情 况下，这些方向必须正跨越r ”。一个正跨越集可保证至少包含一组正基，但它可包含 更多。一组正基是这样一组正跨越集，它的任何真子集都不能正跨越r ”。正基含有疗+ 1 到2 力个元素【1 6 】。关于正基的性质和例子可参考【3 ，1 6 ，1 7 】。如果目标函数具有一定的光滑 性质且所用的正基数目保持有限，则模式搜索在l i m i n f 的意义下收敛到稳定点。 对于模式搜索，具体的搜索过程分为两步【1 8 j ：s e a r c hs t e p 和p o l ls t e p 。首先，对当前 网格的任意的有限个网点( 由当前点和搜索模式所确定的试验点组成) 处的函数值进行 比较，如果没有发现能够减小函数值的点，则将搜索限定在一个p o l l 集上进行。对于无 约束优化而言，p o l l 集里的所有向量必须构成r ”的一组正跨越集，从而保证这个集合中 肯定有使函数值下降的点( 除非当前点就是最小值点) 。如果在第一步发现了能够减小函 数值的点，则规定这个点为新的迭代点；p o l ls t e p 的执行是在s e a r c hs t e p 失败之后，在当 前点的一个网格邻域内( 即p o l l 集) 进行搜索，主要是通过比较当前点的附近的一些试验 点的函数值的大小，来确定下一步的搜索。关于网格和p o l l 集的相关的具体介绍可参考 a u d e t 和d e n n i s 在 1 9 】中的描述。只要目标函数具有一定的可微性质，贝, i j p o l ls t e p 一定可 以找到下降的点，除非当前点是稳定点1 1 7 j 。搜索过程中的s e a r c hs t e p 倾向于对变量空间 进行全局搜索，根据这种特性，可以用代价低的目标函数值或约束函数的替代点去预测 优化问题中的广义模式搜索算法 一些能够降低目标函数的点，从而减少迭代次数。这一步的搜索具有随机性，在收敛性 结果的分析中不起实质性作用。p o l ls t e p 主要围绕当前迭代点进行局部搜索，其搜索步 长可由控制参数和模式矩阵足来确定。其中，模式矩阵只由基矩阵( b a s i sm a t r i x ) 和生 成矩阵( g e n e r a t i n gm a t r i x ) 构成，迭代过程中的下降方向即是从模式矩阵的列向量中选 出。下面我们简单介绍一下模式搜索算法中常用到的一些概念和结论【4 l 。 1 2 2 基本概念与结论 为了文章论述上的方便，下面对模式搜索算法中常要用的基本概念和结论做一下简 单的回顾与介绍。 定义1 1 【4 】( 正跨越集) 称一组向量 a i ，口。) 正跨越r ”，如果对任意的向量x r ”，都 可以表示成这些集合中向量的非负线性组合，即， 工= 口l a i + 口2 a s + + 口p a v ，q 0 ，v f 定义1 2 【4 】( 正基) 集合 口l ，a 。 称为正无关的，如果任何一个均不能表示成其他向 量的非负线性组合；我们称正无关的一组正跨越集为一组正基；正基含有疗+ l 【1 6 】到2 刀个 元素。例如，向量集溉，e 2 ，- ( e + p 2 ) ) 和他，p 2 ，呻i ，巳) 分别是r 2 的一组正基。 定理1 1 【1 7 】 圪是r ”的正跨越集当且仅当对v u r ”，甜0 ，了d k ，s f u r d 0 。 下面给出当前网格【1 4 】的定义。 设d 是一个有限矩阵，它的列构成r ”的一个正跨越集。d d 表示d 的列向量， 且每一个列向量都可以表示成一个可逆矩阵和一个整向量的乘积。极值函数m ( ，) 表示 当前网格，由d 中的列向量以当前迭代点为中心生成： m ( ，a 七) = 以+ a 七d ziz n a 。r + 表示网格大小的参数，刀d 表示矩阵d 的列数。 定义1 3 【4 】( 基矩阵)基矩阵可以是任意的非奇异矩阵b r 。 定义1 4 【4 l ( 生成矩阵) 生成矩阵指的是一个整数矩阵g z “ ，其中以 2 n ，用0 列表 示0 步( a px k + = 毛) 。通常将g 分解成如下形式：q = 【，一帆，厶】_ 【f 。，厶】，其中 帆m cz “”非奇异，且其列向量是r ”的一组正基，控制每一步的搜索方向。肘是一 个非奇异矩阵集合，且元素数目有限。l 称为中心模式，z 州a 2 帕由正跨越集中的 其他向量组成，且至少包含- n 向量，即零向量。 模式矩阵丑= b g = 【盯。，】，由b 和g 的性质可知，只的列向量构成r ”的一组 大连理工大学硕士学位论文 正基。一般情况下，可取b = i 。在搜索过程中，不同的探测移动决定了不同的模式矩 阵，模式矩阵的列向量包含了搜索过程中可能选取的所有方向。 在迭代过程中，如果x 川满足f ( x ) 0 ，设p i ，e 2 代表r 2 的标准单位基向量。 依次在点x k a 。弓，i = 1 , 2 估计函数值，直到找到，满足厂( ) f ( x k ) ，如果找不到， 则将色减半，再重复上述操作：否则，保持色不变或使之增加，然后令五+ = ，重复 上述过程直到。小于事先给定的充分小的正数为止。 o o 色 厂k 弋 耳 o o 图1 1一个简单的模式搜索的例子 1 3 几种特殊的模式搜索算法 根据搜索策略( 模式) 的不同，可以把模式搜索算法进行分类。具体的例子很多，例 如经典的直接法，包括具有固定步长的坐标搜索( c o o r d i n a t es e a r c hw i t hf i x e ds t e ps i z e ) ， 使用因子设计的调优运算【2 0 2 1 1 ( e v o l u t i o n a r yo p e r a t i o nu s i n gf a c t o r i a ld e s i g n s ) 等；h o o k e 和 j e e v e s 最初提出的模式搜索算法1 1 0 】以及d e n n i s - t o r c z o n 的多方向搜索算法【9 】等等。 1 指南针搜索算法( c o m p a s ss e a r c h ) 优化问题中的广义模式搜索算法 正如上述例子所述，这种算法是在搜索空间的每一维正负坐标方向进行简单的搜 索，如果发现使目标函数值下降的试验点，则替换当前点变成新的迭代点，重新开始搜 索；如果所有的协调方向都找不到改进的试验点，则将试验步长参数缩短一半继续进行。 如果步长控制参数小于预先给定的停止标准，则称收敛性已被断定，稳定点已找到。这 种算法是一种最简单的模式搜索算法。 2 协调搜索算法1 4 1 ( c o o r d i n a t es e a r c h ) 协调搜索算法又称为轮换方向法、变换变量法、轴向法或局部变换法。这种方法要 求在每一个迭代点处对其所有协调向量的正负方向都进行搜索，也就是说，当协调搜索 在某个方向上发现函数值下降时并不立即更新迭代，而是在此试验点的其他正负坐标方 向继续进行搜索，直到找到使目标函数值最小的那个点作为新的迭代点。在很多问题上， 协调搜索比指南针搜索表现出更好的改进。 3 多方向搜索算法( m u l t i d i r e c t i o n a ls e a r c h ) 1 9 8 9 年，d e n n i s 和t o r c z o n 在利用并行计算处理问题时，为了实现迭代优先向具有预 期性质的试验点移动，引入了多方向搜索算法，并证明了此算法的全局收敛性1 9 】。之后人 们对这种方法进行进一步的研究，产生了一系列考虑到计算过程灵活性的算法i 3 1 。 多方向搜索算法是基于单纯形的一种算法，模式点可以表述为当前迭代点处的单纯 形的顶点。它的构思源于s p e n d l e y h e x t h i m s w o t h 2 4 】单纯形算法的设计及n e i d e r - m e a d 7 j 的单纯形调优算法，关于它的详细的描述可参考【9 】。 1 4 模式搜索算法的研究进展 h o o k e - j e e v e s 在1 9 6 1 年提出了原始的模式搜索算法，1 9 9 7 年由t o r c z o n 将其加以推 广，引入模式矩阵的概念( 包括基本矩阵和生成矩阵) ，提出了g p s 算法，并证明了它关 于无约束最优化问题的收敛性。1 9 9 9 年，l e w i s 和t o r c z o n 结合正基的性质将g p s 算法推 广到盒式约束的情形【6 】，进而于2 0 0 0 年推广到有限个线性约束的情形【引，证明了由这种算 法产生的迭代收敛到问题的稳定点。这种推广主要是要求模式矩阵必须包括可行域边界附 近任意可行点处切锥的生成元。2 0 0 1 年，a u d e t 和d c n n i s 结合过滤的步长接受标准分析研究 - j g p s 算法关于求解广义的混合变量优化问题1 2 5 ，并由m a r ka a r o na b r a m s o n 于2 0 0 2 年 将其推广到一般非线性混合变量的优化问题，得到了一系列的收敛性证明。近年来，模 式搜索算法与其他方法相结合，一定程度上克服了其在接近稳定点时不成功的迭代增加 从而使搜索进程变慢的缺陷。例如，在模式搜索中引入单纯形导数，根据它的信息对搜 索方向进行编号；利用拟牛顿法中近似计算的h e s s i a n 阵作为模式搜索算法中的一组方向 大连理工大学硕士学位论文 集【2 6 2 7 】；以及蚁群( a n tc o l o n y ) 算法在模式搜索的应用【2 8 1 等。 1 5 本论文的主要工作 文献【8 】将模式搜索算法应用到线性等式约束最优化问题，给出了一种新的算法，并 得到了这种算法的全局收敛性。第二章对这种算法进行进一步的研究，给出了它的局部 收敛性结果。证明了此算法中的步长控制参数对一阶稳定性提供了一个可靠的度量，并 且可以适当放松对目标函数二阶导数正定性的假设，第二章的最后给出了数值算例，从 数据试验上验证了我们的局部收敛性结果。 第三章将模式搜索算法应用于求解有限的极大极小问题，鉴于这类问题的非光滑 性，以及模式搜索算法在求解非光滑问题中的缺吲3 1 ，我们引入一个带有参数的光滑函 数来近似逼近原函数，对光滑函数使用模式搜索来求解最优，进而得到原问题的最优解。 同样的，此算法也无需计算或近似任何的导数信息，迭代过程中不需要目标函数值的充 分下降，即可得到全局收敛性。 大连理工大学硕士学位论文 2 线性等式约束最优化问题的广义模式搜索算法的局部收敛性 考虑下面的优化问题： n f i n ( x ) s t a x = b ( 2 1 ) 其中，f ：r ”一r ，a r “”，聊 0 。若k 是有限集，则存在 0 ，使得r ( 圪) ，k = l ，2 ，一 推论2 i t 8 】在定理2 1 中令材= 一z7 v f ( x ) 0 ，其中z r 州4 1 】，且它的列由约束矩阵彳的 零空间的一组单位基底构成，并满足z 7 z = ，其中，表示历维的单位矩阵。设 r ( 圪) ，则存在，圪，使得 - z7 可歹( 工) 】r y k i 。i iz7 可丁( x ) i i i i ，i f 2 2 问题的描述 2 2 1关于收敛到k k t 点的度量的分析 正如 8 e p 所述，若x 是问题( 2 1 ) 的约束稳定点，则存在允r “，使得 w ( x ) + a 7 元= 0 ，( 2 2 ) 在式( 2 2 ) 的两边分别左乘z7 ，可得 z 7 夥( x ) + ( 彳z ) 7 允= 0 ， 即， z 7 可( 曲= 0 ( 2 3 ) 由此结论可得，当x 是问题( 2 1 ) 的稳定点时，当且仅当z r w ( 工) = 0 ，其中z r 州” 如前面所定义。如果工不是稳定点，即z r 夥( x ) 0 ，则由推论2 1 可知，在r ”叭p 必有 向量y 满足1 ，7 z r 夥( 工) 0 ，即z y 是问题的下降且可行方向。因此只要初始迭代点是 可行点，则以形式= t z 吃确定的步长一定能保证以后的迭代点均可行，故只需在 r ”的一组正跨越集中寻找下降方向，从而达到降维的目的。 2 2 2 算法的结构 文献【8 】中的模式搜索算法采用了一种特殊的探测移动，其模式矩阵为：只= z k z v ，其中，z r “( ”如推论2 1 中所定义。y r ”弦( ，n - - r e + 1 ) 表示一个有限 矩阵，且它的列由空间r ”的正跨越集组成；k 表示当前网格中r ”的正跨越集，：表 示圪的第f 列，且圪y 。这样定义的搜索模式是合理的，因为在其正规的定义中1 1 4 1 所 要求的条件的目的就是为了在p o l l 集中至少存在一个下降方向，由上一节的分析可知， 大连理工大学硕士学位论文 在此新定义的情形下，这个事实也是成立的。关于模式矩阵只和探测步有如下假设【8 1 ： 假设z 1对v v 矿，有成；。纠i 叫l 儿，令y 眦。= 风。i iz l i ，则对任意的步长& ，都有， i i 吼l i a i 。 这个假设可保证任意的步长都是有界的。 假设2 2n m i n l f ( x 。+ 色z v ) i1 ，圪 0 ，则令以+ l = ：否则，令t + 。= _ ； e 更新圪和七。 算法2 1 是模式搜索算法的一般形式，对于具体的不同的算法有不同的策略移动，如 指南针移动、坐标轮换移动等，我们可在 3 ，4 】等文献中找到相关的描述。在实际操作中， 圪也可保持不变。 关于色的更新，仍采用【4 】中的法则： 算法2 2 【4 1 更新趣： 给定f q ，令臼= f 吨，五人= f n ，f 吨) ，其中f l ， c o o ，q ，吼) z ， 司人l o ，w ( x ) 在开邻域u = u ，“( 而) b ( x ，p ) 上是，枷c 加2 连续的，常 数为m ，则存在暖2 o 和巳2 0 ，满足如果五是一个网格局部最优解，则当a 。 疋上时， 有 i iz r v f ( x , ) i i - c 2 2 a i 证明：设，= m i n l ，纠，若x 三( 而) ，则b ( x ，) cu 。考虑步长& = 色z ，其中圪cv ， 由假设2 1 ，i l & i l 0 。 定义 r = q 。盯曲，( 2 5 ) 和 r = 厂( y 一+ 1 ) ( 2 6 ) r 的选取可保证如果0 _ 一五l i r 且i r ，则对于任意的步长s t i z v , ，有 i i ( x 。+ 5 i ) 一五i i 0 满足：如果以是一个网格局部最优 解，满足| l 吒一五i i r 且i r ( r 如式( 2 6 ) 中定义) ，则 i i x 七一x 。l i t m i 。i iz 7 v 厂( 工) 川v0 ( 2 7 ) 如果以是网格最优解，则有 f ( x k + 女z v ) - f ( x i ) 0 ， v v 圪， 因为 _ a m 忆0 ， ( 2 9 ) 结合式( 2 8 ) 和式( 2 9 ) ，我们得到 l jx k - x i i - i iz v , i i q iz i i i i 州l 爰芝h2 薏吣 如一2 薏，则 i l x 七一x i i o 满足：对于v k n ，n 如假设2 3 中定义，如果a i 盈3 ，且吒满足i | x k li i 岛3 则对于v l k ，有 i i 而一五i i 1 其中，i 如式( 2 6 ) 中定义。 优化问题中的广义模式搜索算法 证明：选取盈，和占2 3 满足 证明采用归纳法。首先考虑耳+ ，= x k + & 。由假设2 1 ，对任意的步长，有 & 临色，于是，当，= j | + l 时，结论成立。即， 0 + i 一l i q l 一l l + 坼一夏i i ，嗍i + 岛3 k + l ，假设0 而- x i l r ，则 0 而卅- x , i l 鸳i 而+ 。一而0 + i i 而一五l i ( 2 1 1 ) 由假设2 3 得，当，k 时，f 。，因此， 0 巧+ i 一而0 y m “，s 以州i 由归纳假设知，而e 曰似，r 1 ) n q ，又( 西) f ( x k ) ，由命题2 2 和假设0 五一五l i 乞3 得 !三 0 而- - x 1 峰k 20 黾一五0 o 满足命题2 3 。如果对某个七n ， n 如假设2 3 中所述，有色 岛3 且| l 一l0 岛3 ，则有 l i r a 。= 0 1 此命题是通过反证法来证明的，具体的证明可参考命题4 4 【2 9 1 的证明思路。 结合上述命题，本文可以得到下面的局部收敛结果，即如果在某个迭代点处，所有 ， l 一2 老屯 0 满足：如果在某次迭代k 处，有 靠+ x z 吆b 伍，p ) ，k n ，而霞是k 之后第一个不成功的迭代，则对所有的k 露， 有 i i 吒一矗i i c 2 3 a 肼( t ) ( 2 1 2 ) 其中，r e ( k ) 表示在k 之前( 包括k ) 的最后一个不成功的迭代。进一步，有 ! i m t = 五 o t n 由于对任意的非零的试验步s ：a 。z k ，都有， 0s 川= a i lz 嵋i i a 。i l 西l i ，( 2