（运筹学与控制论专业论文）格子基搜索算法解优化问题的一些研究.pdf

大连理工大学硕士学位论文 摘要 目前，在一些不用导数的最优化算法中，已经有许多方法得到了收敛性的证明本 论文主要对格子基搜索算法进行了研究，此算法也是一种无导数方法，最显著的特点就 是无需计算目标函数的导数值格子基搜索算法主要是在由正基族中的某个元素所生成 的格子上进行搜索，因此研究此算法所首要考虑的因素就是选取适当的正基。由于它属 于直接搜索算法的范畴，就使得这种方法比较适用于大规模的优化问题，同时也适用于 那些目标函数导数不存在或者计算繁琐的最优化问题，主要应用于非线性规划和非光滑 最优化领域 本论文主要对格子基搜索算法关于线性等式约束最优化问题和非线性互补问题进行 了研究，主要工作如下： 第1 章和第2 章申简单介绍了有关最优化理论与算法的一些基础知识，包括：最优 化算法的结构、算法的收敛速度、一些基本原理以及几种传统的表示方式 第3 章主要解决一类线性等式约束优化问题主要工作是给出了解这类线性等式约 束优化问题的一种新的方法，即直接搜索方法中的格子基搜索算法，并且证明了这个算 法的收敛性在此问题的算法中采用了投影梯度，因而所用的正基族中的每个元素都是 p 一”中的正基，这样就降低了运算的维数，从而在一定程度上简化了运算过程 第4 章中给出了解决非线性互补问题的格子基搜索算法，将此算法根据条件的强弱， 以两种不同的结构加以讨论，分别从这两个方面分析了算法的收敛性，并且给出了两个收 敛性结果的严格证明第一个结果表明了此算法产生的序列至少有一个极限点是此问题 的稳定点第二个结果则表明了此算法产生的序列的每一个极限点都是问题的稳定点 关键词：格子基搜索算法；无导数优化方法；k k t 条件；正基；收敛性分析 格子基搜索算法解优化问题的一些研究 s o m es t u d i e so ft h eg r i d 小a s e dm e t h o d sf o ro p t i l i z a t i o np r o b l e m s a b s t r a c t n a w ，m 村l yc o n v e r g e n c er e s u l t so ft h ed e r i 、氇t i v e _ 矗e ea l g o r i t h m sf o rt h eo p t i m i z a t i o n p r o b l e m sh a eb e e ne s t a b u 8 h e d g r i d _ b a s e dm e t h o di st h em 血w o r ki nt h ep a p e r i t i so n eo f 七h ed i r e c ts e a r c h l e t h o d s a na t t r a c t i v ef e a t u r eo ft h i s 出g o r i t h mi st h a ti ti 8 d e r i v a t i v e - f r e e ，i e ，n od e r i t i v eo ft h eo b j e c t i v ef u n c t i o nn e e dt ob ee o m p 吼e d t h eg r i d b 8 s e dm e t h o d ss e e kam i i 工l i z e ro ft h eo b j e c t i v ef u n c t i o nb ye x 舭n j n i n gi to nas e q u e n c eo f s u c c e s s i v e l y 酗d s e a c bg r i di sd e 缸e db y8 nd e m e n to fc l a s sc o 璐i s t m go fp o s i t i v eb a 8 e s ， t h l l s8 e l e c t i n gp m p e rp o s i t i v eb a s e si st h e 缸s tc o n s i d e r e df a c t o rf o rt h ea k o r i t h m s s i n c e 主tb e l o n g st ot h ec l a s so fd i r e c ts e a r c hm e t h o d 8 ，i tl ss u i t a b kf o rt h el a r g e - s c a l ep r o b l e m s ， a sw e l la sa p p l i c a t i o n sw h e r et h ed e r i v a 土i v eo ft h eo b j e c t i v ef u n c t i o n 盯en o ta a i l 8 b l eo r a r ec o s t l yt oc o m p u t e t h j 8p 印e rm 甜n l ym m 嘲af 【1 r t h e rd i s c l l s s i o na b o u tt h eg r i d - b a s e dm e t h o d sf o ri i n e a re q u a l i t yc o n s t r 越n e do p t i m i z a t i o np r o b l e l sa n dn o n l i n e 盯c o m p l e m e n t 撕t yp r o b l e l s t h em a j 卫c o n t e n t so ft st h e s i sc a nb es u m m a r i z e da sf b l l o 啊，8 ： i nc h a p t e r1 锄dc h a p t e r2 ，w ed e s c r i b es o m ei n f o r m a t i o no ft h eo p t i m i z a t i o n t h e o r y a n d 出g o r i t hi nd e t a i l ，s u c ha st h e8 t r u c t u r ea n dt h er a t eo fo p t i m i z a t i o na 岖o r i t h m ，t h e c a r d i n a | p r i n c i p l e ，t 王l et r a d i t i o n a lr e p r e s e n t a t i o n s i nc h a p t e r3 ，w ec o i l s i d e rad i r e c t8 e a r c hm e t h o df o rac l a s so fl i i l e 盯e q u 出i t yc o n s t r a i n e do p t i l i z a t i o np r o b l e m s ，w h i c hm 如su s eo fg r i d sc d l e dg r i d _ b a s e dm e t h o d s ，a n d 西v eap r o o f o fi t sc o n v e r g e n c e d u r i n gt h er e s e 盯c ht h ep r o j e c t e dg r a d i e n tm e t h o d sa r e a d o p t e d ，s oe v e r ye l e m e n to ft h ec i a 8 8c o 工1 s i 8 t i n go fp o s i t i 、t eb a s e si sap o s i t i 、，eb a s e so f r n m t h u st h ed i m e n s i o no ft h ev 盯i a b l e sn e e dt ob ec o m p u t e di nt h ea 1 9 0 r i t t l si s d e c r e a s e da n dt h ei m p l e m e n t a t i o no ft h ea l g o r i t h l si ss i m p l m e dt o8 0 m ee x t e n t 1 nc h a p t e r4 ，w ed e 8 c r i b et h eg r i d - b 8 8 e dm e t h o d sf o rt h en o n l i n e a rc o m p l e m e n t 壮i t y p r o b l e m s w ec o n s i d e rt h em e t h o d su n d e rt w od e r 凹l ts t r u c t u r e sa c e o r d i n gt o 七h ec o n - d i t l o nd e g r e e ，a n a l y z et h ec a n v e r g e n c er e 8 p e c t i v e l y ，a n d 前a t e 也es t r i c tp r 0 0 f t h e 缸s t r e s u l ti m p l i e st h a ta t1 e 8 s to n eo ft h e1 i l i tp o i n to fi t e r a t e sg e n e r a t e db yt 1 1 i 8m e t h o di s t h es t a t i o n 螂7p o i n t ，a i l dt h es e c o n do n em e a mt h a te v e r yh m i tp o i to fl t e r a t e 8g e e r a t e d i st h es t a t i o n a r yp o i n t k e yw b r d s ： g r i d _ b a s e dm e t h o d s ；d e r i v a t i 悟序e eo p t i m i z a t i o n ；k k tc o n d i t i o n ；p o s 扎i 、r eb 船e s ；c o n v e r g e n c ea n a l y s i s l l 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：2 虽亟日期：盈么乡 格子基搜索算法解优化问题的一些研究 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口 ( 请在以上方框内打”，) 作者签名：盔远 指导教师签名：数皇脏 型! 年月l 日 大连理工大学硕士学位论文 1 绪论 对格子基搜索算法进行研究是本文的主要工作，它是优化问题的解决方法中直接搜 索方法的一种，也就是利用无导数方法去解决优化问题在此，简要介绍一下优化问题 和直接法的有关知识及相关背景，以便读者对这方面有个了解然后再对格子基搜索算 法的知识背景以及算法结构的导出给出比较详细的阐述。 1 1 引言 目标函数是线性函数并且约束条件全都是线性等式( 不等式) 的这一类数学规划，都 属于线性规划范畴。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的 一个重要分支，它是辅助人们进行科学管理的一种数学方法它研究的问题大致可以分 为两类，一类是已知一定量的人力，物力，财力等资源，研究如何运用这些资源使完成的 任务最多；另一类是给定一项任务，研究如何统筹安排，才能以最少的人力，物力，财力 等资源来完成该任务这两类问题实际上是一类问题的两个方面，都是寻求某个整体指 标的最优化问题。表现在经济管理、交通运输、工农业生产等经济活动中，就是提高经济 效果，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺， 使用新设备和新型原材料。二是生产组织与计划的改进，即合理安排人力物力资源线 性规划所研究的是；在一定条件下，合理安排人力物力等资源，使经济效果达到最好 而目标函数是非线性函数或约束条件有一个是非线性等式( 不等式) 的一类数学规 划，都是非线性规划的范畴在科学管理和其他领域中，很多实际问题可以归结为线性 规划，但更多的问题属于非线性规划由于非线性规划含有深刻的背景和丰富的内容， 现已发展为运筹学的重要分支，并且在最优设计、管理科学、系统控制等领域得到越来越 广泛的应用。 非线性规划求解方法可分为无约束问题和约束问题来讨论，前者实际上就是多元函 数的极值问题，是后一问题的基础无约束问题的求解方法有最速下降法、共轭梯度法、 变尺度法和鲍威尔直接法等约束问题的情况比较复杂，因为在迭代过程中除了要使目标 函数下降外，还要考虑近似解的可行性总的原则是设法将约束问题化为无约束问题； 把非线性问题化为线性问题从而使复杂问题简单化求解方法有可行方向法、制约函数 法、简约梯度法、约束变尺度法、二次规划法和约束集法等虽然这些方法都有较好的 效果，但是尚未找到可以用于解决所有非线性规划的统一算法求解约束极值问题要比 求解无约束极值问题困难得多为了简化工作，可采用以下方法：将约束问题化为无约 束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的 其它方法 格子基搜索算法解优化问题的一些研究 1 2 直接法的研究进展 实际中常常会遇到一些线性或非线性问题，相对而言，线性问题比较容易解决，而 非线性问题就比较麻烦，通常需要将其转变为线性问题来解决 最优化问题f 1 】的一般形式为： m 饥，( 。) ， s t z x 其中z x 为决策变量，( 。) 为目标函数，xc 彤为约束集或可行域 果约束集x = 彤则，最优化问题( 1 2 1 ) 称为无约束最优化问题 约束优化问题通常写为： s t q ) = 0 q 仕) 0 i e i ， ( 1 2 1 ) 特别地，如 这里的e 和1 分别是等式约束的指标集和不等式约束的指标集，q ( z ) 是约束函数当 目标函数和约束函数均为线| 生函数时，问题称为线性规划当目标函数和约束函数中至 少有一个是变量的非线性函数时，问题称为非线性规划此外，根据决策变量、目标函 数和要求的不同，最优化还分成了整数规划、动态规划、网络规划、非光滑规划、随机规 划、几何规划、多目标规划等若干分支。 如果，( o ) 是可微的并且v ，( z ) 是可以被计算出来的或者是被有限差分精确地估计 出来的话，人们一般都会选择一种利用导数信息的优化算法去解决这个问题当时对于 一个可微函数来说，找到它的最优解的必要条件就是梯度v ，( z ) 等于零而当遇到问题 的目标函数不可导或导函数的解析式难以表示时，早期的人们认为想要完全不利用导数 信息去解决一个函数，( z ) 的最小值问题是不现实的，那么在没有明确的导数信息的时候 该怎么去解决这样的问题呢? 这个时候一种被称为直接搜索方法的优化算法出现了由 于这些方法一般都比较直观和易于理解，因而在实际应用中常为人们所采用 在文献中了解到早在1 9 5 0 年直接搜索算法就被认知了，但直到1 9 6 1 年这种方 法才正式出现在文献里，其主要原因是由于当时对这种方法的研究还处在探索阶段，没 有十分有力的收敛性结果的证明，并且有时候直接法搜索速度相对较慢，所以在1 9 7 0 年 以前数学优化界很少采用直接法直到上一个十五年，直接法才又被重新重视起来然 而，直接法却一直受到科学和工程领域的专家的青睐，得到他们的广泛关注早期的直 接法主要是基于一些简单的和人们比较感兴趣的问题来进行探索，这些启发式的研究主 要是来源于那些二维空间中的例子，中有详细的介绍另外一个原因就是很多用户不 喜欢计算梯度，梯度的计算在优化软件库的应用过程中本身就是一个最容易出现错误的 2 大连理工大学硕士学位论文 环节。在1 9 9 1 年，对直接法的关注程度再一次提高了，相关的文章还提及了收敛性分析 【4 】，从此以后，以下两件事情逐渐明了了： 1 对于许多不同的优化问题直接法都是一个很有效的方法，有时候甚至是唯一的 选择方法。 2 许多直接法都是可以给出严格的收敛性保证的 随着时间的推移，许多有关收敛性的主要因素得到了证明nb ，7 ，吲因为缺乏对直 接搜索算法的确切定义，研究起来就更显得麻烦这个术语首次出现是在h 0 0 k e 和j e e v e 8 的1 9 6 1 年的论文剐里，从此以后，这个名词就成了一个专门针对那些不需要涉及目标 函数的精确梯度的优化算法的代名词 目前，对于无约柬最优化问题，已经有很多种不用导数的算法得到了收敛性的结果， 例如格子基搜索算法，格子基射线搜索算法，n e l d e 卜m e a d 算法，广义模式搜索算法等， 而且在解决非线性互补问题方面也有所发展，并且当目标函数是强单调时，利用直接搜 索方法得到的最优解的迭代序列是以线速度收敛的，而在此之前并没有给出有关收敛速 度的结果 1 3 本文的主要工作 在第3 章主要是给出了解一类线性等式约束优化问题的一种新的方法，即直接搜索 方法中的格子基搜索算法，并且证明了这个算法的收敛性在此问题的算法中采用了投 影梯度，降低了运算的维数，从而在一定程度上简化了运算过程 第4 章中，给出了解决非线性互补问题的格子基搜索算法，将此算法根据条件的强 弱，分两种不同的结构加以讨论，分别从这两个方面分析了算法的收敛性，并且给出了 两个收敛性结果的严格证明。 3 大连理工大学硕士学位论文 2 问题描述及有关定义 2 1 最优化方法的结构 最优化方法通常采用迭代方法来求得最优解，其基本思想 1 是：给定一个初始点 z 。酽，按照某一迭代规则产生一个点列 茹k ) ，使得当 z ) 是有穷点列时，其最后 一个点就是最优化问题的最优解当 o k ，是无穷点列时，它有极限点，且其极限点是最 优化问题的最优解 一个好的算法应具备的典型特征为：迭代点z k 能稳定地接近局部极小点o 的邻 域，然后迅速收敛于芏+ 当给定的某种收敛准则满足时，迭代即终止。一般地，我们要 证明迭代点列 g ) 的聚点( 即子序列的极限点) 为一局部极小点 设钆为第次迭代点，以是第次搜索方向，q k 为第女次步长因子，则第七次迭代为 z k + l = 茁k + n k d k 从这个迭代格式可以看出，不同的步长因子k 和不同的搜索方向靠构成了不同的方 法。 最优化方法中，搜索方向也是，在点。女处的下降方向，即如满足 或 v ，( z ) 丁以 0 ，使得 。糌爿= a 则称算法产生的迭代点列 z 具有q n 阶收敛速度特别地， ( 1 ) 当q = 1 ，g o ，时，迭代点列 。 叫做具有q 一线性收敛速度； ( 2 ) 当1 1 ，r = l i m s u p k o 。1 | 。k 一。+ i l 一， ( 3 ) 如果r 1 = o ，则称z k 是r 一超线性收敛于z + ；如果0 r l 1 ，则称吼是 兄一线性收敛于z ；如果尼= 1 ，则称z k 是r 一次线性收敛于z 。 类似地，如果r 2 = o ，则称o k 是r 一超平方收敛于矿；如果0 见 0 ，使得对所有满足z r r 。和忙一矿| l ，( 矿) ，则称矿为，的严格总体极小点 一般来说，实际可行的只是求一个局部( 或严格局部) 极小点，而非总体极小点求 总体极小点的可能性也被考虑到了，但是这是个相当困难的任务。而且在很多实际应用 中，求局部极小点就已经可以满足问题的要求了 在本文中如果不做特殊说明的话，分别记 则我们有 9 ( ) = v ，( z ) ，g ( 石) = = v 2 ，( z ) 定理2 3 1 ：( 一阶必要条件) 设，：dcr “+ r 1 在开集d 上连续可微，若矿d 是 无约束优化问题( 2 3 1 ) 的局部极小点，则9 ( 矿) = o 证明：设矿是一个局部极小点，考虑序列。k = 矿一血桕( z + ) 利用工匆l o r 展式，对于充分大的，有 os ，( z 七) 一，( 。+ ) = 一a 厂7 ( 叩k ) 9 ( 。+ ) ， 其中吼是。k 和的凸组合f 10 1 两边同时除以口k ，并取极限由于，g 1 ，故有 os 一( 。+ ) 俨 显然，仅当，7 ( z + ) = o 时，上式成立 口 定理2 3 2 ：( 二阶必要条件) 设，：dcr “+ r 1 在开集d 上二阶连续可微，若z + 口 是无约束优化问题( 2 3 1 ) 的局部极小点，则 夕( z + ) = o ，g ( ) o ( 2 3 2 ) 证明：( 2 3 2 ) 中的第一式在定理2 3 1 中已经证明了，故只须证明第二式考虑序列。k = 矿+ o d ，d 是任意的。由于，e 2 和9 ( 矿) = o ，故由r a y l 。r 展式，对于充分大的 ，有 。曼，( z 一) 一，( z + ) = ；口* 2 d 7 g ( 叩t ) d ， 7 格子基搜索算法解优化问题的一些研究 其中仉是z 和的凸组合由于矿是一个局部极小点，g 2 ，则上式两边同时 除以 k 2 ，并取极限，得 d t g ( 仉) d o ，v d 舻 从而( 2 3 2 ) 第二式得到 口 定理2 3 3 ：( 二阶充分条件) 设，：dc 舻_ + r 1 在开集d 上二阶连续可微，则z + d 是，的严格局部极小点的充分条件是9 ( ) = 0 和g ( 矿) 是正定矩阵。 证明：假设结论成立，则由t a y l o r 展式，对任意向量d ， m 4 + s d ) = m + ) + i 2 矿g ( 。+ + 蚴) d ， 由于g ( z + ) 正定，e 2 ，故可以选择，使得茁+ 甜札( 矿) ，从而 d g ( 。+ + 口s d ) d 0 ， 这样 ，( z + + d ) ，( z + ) ， 即z + 是严格局部极小点 口 一般地，目标函数的平稳点不一定是极小点但若目标函数是凸函数，则其平稳点 就是其极小点，且为总体极小点 8 大连理工大学硕士学位论文 3 格子基搜索算法解一类线性约束优化问题 格子基搜索算法是一种不用导数的算法，它要求每一次搜索都在某个格子上进行， 这个格子是由一组线性无关的基向量线性张成的，格子上的每一点都是这些向量的某个 线性组合搜索的步骤首先要选定一个初始点，然后就在这个格子上任意找有限个点代 人目标函数进行计算，选出一个下降方向，并得到一个下降点，依次进行下去，最终会 得到一组下降点的迭代序列。接下来的工作就是要去证明这一序列是否能够收敛到目标 函数的稳定点。这种搜索方法的具体结构通常分为两种，一种是在每找到一个下降方向 时，即可将得到的点记为下次搜索的初始点来进行下一次循环；第二种是在找到了一个 最速下降方向的时候再往下进行循环，这样也会得到一个迭代点序列 在最优设计、管理科学、系统控制等领域，很多实际问题可以归结为最优化问题中 的非线性规划问题。由于非线性规划食有深刻的背景和丰富的内容，已发展为运筹学的 重要分支，非线性规划求解方法可分为无约束问题和约束问题来讨论，前者实际上就是 多元函数的极值问题，是后一问题的基础无约束问题的求解方法有最速下降法、共轭 梯度法、变r 度法和鲍威尔直接法等关于约束问题情况比较复杂，因为在造代过程中 除了要使目标函数下降外，还要考虑近似解的可行性总的原则是设法将约束问题化为 无约束问题；把非线性问题化为线性问题从而使复杂问题简单化求解方法有可行方向 法、制约函数法、简约梯度法、约束变尺度法、二次规射法和约束集法等。虽然这些方法 都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。 目前，无约束优化方面，当遇到的问题的目标函数不可导或导函数的解析式难以表 示时，人们一般需要使用直接搜索方法。同时，由于这些方法一般都比较直观和易于理 解，因而在实际应用中常为人们所采用 3 1 引言 本章要介绍的目标函数，( z ) 是连续可微并且下有界的，约束条件是线性等式约束 问题形式可“表示如下： m o n ，( 嚣) 且z = 6 ，( 3 1 1 ) 这里的函数，：彤_ r ，z 册， 胛m ，m 住矩阵 的秩为m 6 是m 维的向量 线性搜索是最优化方法的基本组成部分，无论在无约束优化问题中还是在约束优化 问题中，线搜索都占有相当大的计算花费因此，构造更加有效的线搜索算法从而整体 上降低优化求解的计算量变得非常必要。 对这样的约束优化问题本文建立了两个算法结构在第一个算法中，搜索是按照给 出的格子上的下降方向进行的，可以进行有限步的搜索，最终得到一个收敛性结果，也 出的格子上的下降方向进行的，可以进行有限步的搜索，最终得到一个收敛性结果，也 9 格子基搜索算法解优化问题的一些研究 就是可以得到一个迭代点列，它的一个子列收敛到目标函数的稳定点而在第二个框架 中，假设条件加强了，要求每次搜索是在局部最速下降方向上进行的，也就是说每次得 到的点都是局部最优点这时得到的迭代序列整体是收敛的。 这里先来给出最速下降方向( t h ea d e q u a t ed e s c e t8 t e p ) s ( ) 的定义。满足下面条件 的s ( 2 ) 被称为最速下降方向： f f z + ( r ( 七) ) s ( 七) ) ，( o + ( r ( 七) ) )v 1 ，坚卅j ， 这里的r ( ) 指的是当前点一所在的格子的个数，要确定s ( 2 ) 需进行p ( 7 ( ”次计算 在【儿，“，】中了解了格子基搜索算法的一些性质，它的收敛性也在一些常见的优 化问题类型中得到了证明在主要的收敛性结果的证明中比较重要的一个方面就是成功 的网格可以根据另外一个网格的需要而任意的转化、旋转和修剪，并且每一个网格的轴 都可以单独进行调节1 1 4 ，均】。这种任意性允许二阶信息被融入到网格的形状的确定中 来，比如说，根据共轭方向或者是近似二次方程的主轴方向来调整网格的轴这么做是 希望建立一些保持有共轭方向或拟牛顿方法中有用信息的无导数算法 在了解格子基搜索算法的基础上，进一步学习其它优化算法，掌握其基本算法及优 缺点利用格子基搜索算法并结合其他算法来解决这一类线性约束优化问题 解决这一类线性约束优化问题的时候，困难主要是：首先，要小心处理约束条件中 的维数问题；其次，要尽量将这一问题转化成无约束优化问题来对待；第三，在构建基 于表格的算法时，关键是要选取适当的正基，使得搜索方向可以满足下降的要求 解决无约束优化问题的搜索是在一系列的格子上进行的，也就是说在这一系列格子 上的点处去估计目标函数，：舻一只的值，最终找到最优解 3 2 原问题的分析 在问题( 3 1 1 ) 中，不妨设。是该问题的一个局部最优解，那么必然会存在一个a 尼“ 使得 v ，( z ) + a t a = 0 在式( 3 2 1 ) 的两端乘以z 了1 ，就会得到 z 丁v ，扛) + z t a 丁a = 0 要使式( 3 2 1 ) 成立当且仅当 z t v ，( z ) = 0 ( 3 2 1 ) ( 3 2 2 ) ( 3 2 3 ) 成立其中z 口“( ”) 是由方程a y = 0 的解向量组成的很显然满足条件( 3 2 3 ) 的 z 就是问题( 3 1 1 ) 的k k t 点如果z 不是问题( 3 1 1 ) 的k k t 点，则z t v ，( 。) o ，此 1 0 大连理工大学硕士学位论文 时，由定理( 3 3 1 ) 可知，对于z r v ，( z ) 形一“，一定存在口y 使得 t z t v ，( z ) 0 ， 即 ( 加) t v ，( z ) n ，码= 警1 岛兮丐= 銎l 岛仇 结构等价的正基必须有相同个元素举个例子，以下是三维空间r 3 的两个正跨越 大连理工大学硕士学位论文 这就是两个结构等价的正跨越基，其中岛是第i 个单位向量 以下是四维空间r 4 的两个结构等价的正跨越基： 其中q 是第i 个单位向量。 3 4 算法结构介绍 第二章介绍的最优化算法的基本结构和下面要了解到的算法的结构具有紧密的联 系。本章中将介绍两个格子基搜索算法结构结构1 的主要结论是产生的迭代点序列 中存在一个子序列收敛到目标函数的最优解。这个结构里包括两个不同步的循环，外层 的循环是步骤( 1 3 ) ，选择一个格子去验证终止条件；内部循环是步骤2 ，利用正基k ( ) 中的每一个元素进行有限步搜索，直到p ( ) 次连续搜索都失败，此时就找到了一个格子 局部最小点，从而跳出这个循环，转入外面的循环，在新的格子上重复以上步骤。 格子基算法是直接法中的重要分支，其首要步骤是选取适当的正基h 进行搜索， 寻求目标函数，( z ) 的最优解，算法的基本结构表述如下： 结构j s t 印j 赋初值令r = 1 ，= 1 ，并且选取0 3 ”为初始点z ( ” s t 印2 ( 终止条件不满足) 进行以下步骤： 俐选择适当的整数 ( r 和正基昨。令i = 1 ，t = o 以及p ( r ) = l 哗i 。 r 当 p ( “，则令i = 1 终止。 s 印了记岔【) = 。然后再从格子中任选有限个点来计算函数值，并和，( 矿) 比较，选 取最小的记为* “同时增加和r 的值 转步s t 印2 以上算法中t 表示利用正基瞪中的元素进行有限步搜索时连续失败的次数，已知 搜索的基本结构分为两个层次，在外层循环中选择一个格子使得搜索得以进行并判断是 否满足终止条件，而内层循环则构造了用正基e 叫的每个元素进行具体的有限步搜索 当= 矿时，就找到了当前格子上的局部最优解，记为圣( 。此时即可终止当前格子g ( r ) 1 3 格子基搜索算法解优化问题的一些研究 上的搜索，然后将当前最小点作为在下一个格子上搜索的初始点，记为。3 r + “，进入下 次循环，最终产生一个序列 童( ) 因为步骤( i ) 存在一定的机会性，所以只能保证这个序列的某个子序列收敛。为了实 现序列整体上的收敛性，需要进一步加强搜索条件，将在结构2 中给出具体说明结构 2 中首先通过计算得到当前格子上的一个最速下降方向，然后搜索将沿着正基所给出的 这个最速下降方向进行，前面简单了解了最速下降方向的定义，根据具体条件的不同， 此处最速下降方向s ( 砷指的是满足下述要求的方向： ，( z + ( ( ) ) z s ( 七) s ，( z 七+ 【7 ( ) ) z 可) v o 够” 其中r ( ) 指的是当前点z ( ) 所在格子的个数，要确定s ( 2 ) 需进行p ( 7 ( 。) ) 次计算结 构2 要进行的搜索须沿着方向s ( ) 在一下点列上估计目标函数，的值 磊= z + a 危( r ( ) ) z s ( 知)t = 0 ，1 ，一， 其中参数t 为整数，并且q o = 1 ，当i 之1 时， q t 一】+ 1 q t 茎卢n 。一】 口2 则搜索可以一直进行，直到出现一个满足，( 函) s ，( 童2 + 1 ) 的整数f ，且2 0 由于这 个结构中的每次搜索都是沿着局部最速下降方向进行的，因此由此结构得到的迭代点序 列整体是收敛的，且收敛到问题的一个稳定点。 结构2 s t 印j 赋初值令r = 1 ，七= 1 ，并且选取o 为初始点o ( 。 s 印2 ( 终止条件不满足) 进行以下步骤： 陋，选择适当的整数 ( ) 和正基皑令i = 1 ，= o 以及p ( r ) = l 皑1 陋j 当o ( 姊不是局部最小点时， 俐寻找最速下降方向s ( 舢，使其满足 ，( z + 危( 7 ( 血) ) z s ( ) ，( z + ( ( ) z u )v 钉雌) ) ， 如果，( 矿) ，( 扩+ ( ( 2 ) ) z s ( ) ) 成立，则跳出步骤( b ) ，记z ( ) 为当前的局部最优 解 一f j 从q o = 1 开始，选择一系列整数值n l ，o ，带入函数验证，直到 ，( 。( + 口f + 1 ( 7 ( 知) ) z s ( 七) ，( z ( ) + o i 九( 7 ( 七) ) z s ( 知) 成立为止其中o f + 1 【q 2 + 1 ，序q ，卢2 取整数 一。砂在格子上任选有限个点对函数进行估计，并选出函数值最小的点与点 + 锄丸( ) z s ( ) 处的函数值进行比较，选较小者记为z + 1 同时增加七的值 终止 1 4 大连理工大学硕士学位论文 s t 印3 ，记岔( r ) ：扩。再任选有限个点对函数进行估计，记函数值最小点为毋+ ，如 果，( 。o ( 件1 ) ，( z ( 。+ 1 ) 成立，则记z “+ 1 = 。3 r + 1 并且增加值，且增加r 值。 转步s t 印2 3 5 收敛性分析 上一节介绍了两个算法结构，可以认为后者是前者的特殊情况下面的定理将给出 算法的收敛性证明。定理3 5 1 主要就是针对算法结构1 ，介绍了算法所产生的格子局 部最优解序列的某个子列的收敛性，而定理3 5 2 所说的是整个迭代序列收敛到一个稳 定点，定理3 5 1 的结论在适合结构l 的同时也适合结构2 本节中为了达到收敛的目的，假定终止条件是不成立的。即使从实际角度出发，每 个具体例子所适合的终止条件也是不一样的下面可以看到用以上算法结构得到的迭代 点序列，其某个子序列一定收敛到问题( 3 1 1 ) 的k k t 点，且需要计算的维数已降为 几一m ，在一定程度上简化了计算。 定理3 5 1 ：假设下述条件成立： a 迭代点序列f o ( 钟) 有界； b 目标函数，连续可微； c 存在一个正常数耳和使得1 1 p ，谚! 。1 1 七并且f 1 弗| l 耳对所有的m 和 i 都成立； d 当r _ 。时， ( ) _ 0 ； e 存在启的有限子集使得b 中的每一个元素都与这个有限子集的某个元素结构等价， 这里的b 表示正跨越基 埠) 墨1 的序列。 那么按照结构1 产生的格子局部最优解序列 圣( r ) ) 的元素个数是无限的，并且 仝( ) ) 的 每一个聚点童( 0 0 ) 都是，的一个稳定点。 证明：由定理条件( a ) 可知，一定存在一个紧集d 使得 。( ) ) cd ，因此d n g ( ) 是 有限的从算法结构1 的第2 步可以知道利用每个格子得到的迭代点都为有限个，从当 前格子g ( ) 中跳出的唯一方法就是最后一次迭代得到的点是当前的格子局部最优篇 由定理3 3 1 了解到在正基u 中必存在一个使得z 仇为下降方向，这样，迭代 就需持续进行下去，因此保证了忙( ) ) 是一个无穷数列。 条件( e ) 保证了一个或者更多b 的子集s 存在，除了b 的有限个元素以外所有的 元素都属于类似s 的子集这里s 是一个结构等价基的无限子序列，相应的f 叠( ) ) 的子 集收敛到f 圣( o 。) ) 此时，有： ，忙) + ( 7 ) z ) ，( 岔( r ) 1 ，p ) ，( 3 5 1 ) 1 5 堡茎望墨蔓鲨堡垡些塑堡堕二些堑塞 这里的p = p ( ，其中的r 是满足时s 的。那么现在： ，( 奎7 + 7 z ) = ，( 童1 ) 十曲 r ) + z ) 一雪( r ) + 雪 丁z ) 出 ，刖”) = _ 厂 7 ) + z 7 1 9 ( 垒( 7 ) + t z 可) 一z t 参) + z 丁雪( r t 讲7 d j 0 ， 扣) = ，( 士) + ( z t 互( 7 ) r 趣7 d t + 霹 = ，( 童7 1 ) + ( z t ( ) t ( 越7 + 尉， 这里9 ( 。) 兰v ，( z ) ，互( ) = v ，( 圣( ) p t r j 霹帕= f z t 9 ( 圣( r ) + t z ) 一z t 参( r t 谚) 出 j 0 条件( c ) 给出l i l l sk ，叉因为存在一个z ，且是固定的，所以一定存在一个常 数g 使得zf l g ，这时， 曩”l l z t b 7 1 + z 瑾) 雪( r 1 id t z 丁 9 ( 圣( 7 ) + t z 趣) 一( r i | j r d t k 删 p ) 其中 心叶= m a x j jz 丁b ( 童7 + t z 诺) 一争( 批 o ， ( r 】) 由g 的连续性以及d 的紧致性可知， d 中9 是一致连续的，又知道| l 吐1 1 k 和 j z jj sg ，则由条件( d ) 可得到当r 0 0 时，趔) 一o 因为对所有的r 和i = 1 ，p 都有| | 越l i k ，则保证了序列 ：) 一定存在一 个子序列 磅叫) ，其中i = 1 ，p 由结构等价可知相应的还存在忙) 的一个子序 列 牙) ，都存在唯一的极限，分别记为趣删和童( 一，其中i = l ，p s 中所有 元素结构等价保证了： f 2 m 一。= ”：1 一，p 条件( c ) 意味着”i ，艘。是线性无关的，并且l l i l 茎k 因此 雷严，咿) 是一个正跨越基，并与s 中的元素结构等价 ( 3 5 2 ) 忱= 1 - - 一，p r r h h z z 大连理工大学硕士学位论文 由( 3 5 1 ) 式知： ( z t 雪( ) 7 ( 碰7 + 毯o ， 即 五( 7 ( z t 雪( 7 ) 丁o ：7 + k 捌万( o 成立，其中的矗( r 1 是h i 7 ) 的子序列，当r 一。时，由条件( d ) 得： ( z t 雪( o 。) 了1 谚”2o = 1 ，p 则由定理3 3 1 可知( z t 鸯( 。) ) 丁= o ，即仝( 。) 是 岔( ) ) 的稳定点又因为s 的选取 以及格子局部最优解的聚点的选取都是任意的，则结论成立。 口 注： 条件( a ) 表示迭代序列 。( 埘) 有界； 如果适当地选取正基u ，条件( c ) 是很容易满足的； 只要在每次找到一个格子局部最优解时都将搜索系数九缩小一半，那么条件( d ) 也 是不难得到的； 条件( e ) 是一个实际条件，可以根据实际情况很容易加上去。 当搜索的过程加强之后得到的结论也就随之增强了搜索步骤上的不同具体表现在 前面介绍的两个结构上，结构1 与结构2 的不同之处在于前者是在每得到一个比当前函 数值小的点即作为一个局部最优解记录下来，并且结束这次搜索进入下一个循环，而后 者是在选定一个正基且确定了一个初始格子大小之后，首先计算当前格子的最速下降方 向s ( m ，然后在这个方向上进行搜索，直到得到局部最优解为止。下面的定理主要是针 对结构2 而言，证明了所得的迭代点序列整体收敛到原问题的稳定点。 定理3 5 2 ：如果定理3 5 1 的条件保持成立，那么按照结构2 搜索得到的格子局部最优 解序列f o ( 姊) 收敛到优化问题( 3 1 1 ) 的稳定点。 证明：不妨记z ( o o ) 是序列扛( q ) 的聚点，但是z