（运筹学与控制论专业论文）非线性全局优化的变换函数方法.pdf

摘要 最优化是- f - j 应用相当广泛的学科，它讨论决策问题的最佳选择，构造寻求 最佳解的计算方法并研究这些方法的理论性质及实际计算表现由于社会的进步 和科学技术的发展，最优化问题广泛见于经济计划，工程设计，生产管理，交通运 输，国防军事等重要领域，因此受到高度重视，伴随着计算机的高速发展和最优 化工作者的努力，最优化的理论分析和计算方法得到了极大提高本论文主要工 作就是讨论，研究了非线性最优化问题的几个算法及理论分析 本文包含五章内容第一章简述了目前国内外几种主要的全局最优化问题和 算法及本论文所要用到的非线性规划的一些基本概念及性质后面四章由四篇基 本独立的文章组成 第二章和第三章主要讨论求解无约束全局最优化问题的变换函数法求解 一般函数的全局最优解问题是热点课题之一对全局问题有两个困难需要解决 一是如何从一个局部极小解出发找到更好的局部解，另一个是全局最优解的判定 问题打洞函数法和填充函数法是解决第一个困难的实用方法它们的共同点是 如果已经找到了一个局部极小。；，但它不是全局最小，我们可以在z ：处构造一个 辅助函数一打洞函数或填充函数使迭代点列离开z ：所在的谷域，找到更好的点z 7 ( 即一处的函数值比矿处的函数值更小) 然后以一为起点找出更优的局部极小点。 笫二章定义了两类变换函数，在适当的条件下证明了它们兼具打洞函数和填充函 数的特点和性质，即填充函数法和打洞函数法两种方法在某种意义下是可以统一 的因此可称其为b f 函数第三章给出了几个简单，易于计算且函数性态较好 的变换函数，同样它们兼具打洞函数和填充函数的特点和性质文章证明了第：， 三章定义的变换函数的主要性质：在，扛) 的值比当前局部极小值，0 ：) 大的水平 集上变换函数没有极小点或稳定点；在比当前局部极小值小的水平集上变换函数 一定有微小值点当然这两章也给出了数值试验结果 第四章将用于无约束全局最优问题的思想方法拓广到求解带有约束的非线 性规划问题的全局最优问题首先对于求解带有线性约束的非线性规划问题的 t 局部解，已有很多算法但这些方法考虑的都是局部问题，所以要得到全局解必要 有”凸m 陛条件本章去掉目标函数的凸性要求，在比较宽松的假设下给出了一个 算法，证明了算法的一些理论性质然后，对于带有非线性约束的一般形式的全 局优化问题给出了另一个算法，此算法对目标函数和约束函数都没有凸性要求， 同样在较宽松的假设下证明了算法和变换函数的主要理论性质 第五章提出一个用于求解带不等式约束非线性规划问题的修正共轭梯度投 影方法由于其较快的收敛性，拟牛顿法仍然是非线性规划领域的重要方法之一 相比于其它约束拟牛顿方法，本章的方法有两个优点一是不用严格互补条件而证 明了算法的全局收敛性和局部超线性收敛性，二是每步迭代只需计算一次投影矩 阵从而减少了计算量搜索方向是显式的 关键词非线性规划全局最优解变换函数填充和打洞函数梯度投影 超线性收敛 i i a b s t r a c t t h eo p t i m i z a t i o ni saw i d e l yu s e dd i s c i p l i n e ，w h i c hd i s c u s s e st h ec h a r a c t e r s o fo p t i m a lc h o i c eo nd e c i s i o np r o b l e m sa n dc o n s t r u c t sc o m p u t i n ga p p r o a c h e st o f i n dt h eo p t i m a ls o l u t i o n d u et ot h ea d v a n c e m e n to fs o c i e t ya n dt h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , t h eo p t i m i z a t i o np r o b l e m sa x eo f t e nd i s c o v e r e d i nt h ef i e l do fe c o n o m i cp l a n n i n ga d m i n i s t r a t i o n ，e n g i n e e r i n gd e s i g n ，p r o d u c t i o n m a n a g e m e n t ，t r a f f i ct r a n s p o r t a t i o n ，n a t i o n a ld e f e n c ea n ds oo n t h e ya r es o i m p o r t a n tt h a tm e e tw i t hm u c hr e c o g n i t i o n w “ht h es p e e d yd e v e l o p m e n to f c o m p u t e ra n dt h eh a r dw o r ko fs c i e n t i s t s t h et h e o r e t i ca n a l y s i sa n dc o m p u t a - t i o n a im e t h o d so no p t i m i z a t i o nh a v eb e e nh i g h l yi m p r o v e d ， t h i sp a p e rm a i n l yc o n s i s t so ff i v ec h a p t e r s i nt h ef i r s tc h a p t e r ，s o m em a i n l ym e t h o d sf o rg l o b a lo p t i m i z a t i o np r o b l e m s a r eb r i e f l yp r e s e n t e d a n ds e v e r a lb a s i sc o n c e p t sa n dc h a r a c t e r so ng e n e r a l l y n o n l i n e a rp r o g r a m m i n ga x ei n t r o d u c e d i nt h es e c o n da n dt h i r dc h a p t e rt h et r a n s f o r m a t i o nf u n c t i o n sf o ru n c o n s t r a i n e d g l o b a lo p t i m a lp r o b l e m sa x em a i n l yd i s c u s s e d t of i n dt h ee f f e c t i v em e t h o d sf o r f i n d i n gt h eg l o b a lo p t i m a ls o l u t i o n so fag e n e r a lm u l t i - m i n i m i z e r sf u n c t i o ni so n e o ft h eh o tt o p i c s t h e r et w od i f f i c u l t i e si ng l o b a lo p t i m i z s t i o n 0 n ei sh o wt o l e a v ef r o mal o e a lm i n i m i z e rt oas m a l l e ro n ea n dt h eo t h e ri sh o wt oj u d g e t h a tt h ec u r r e n tm i n i m i z e ri sg l o b a ；t h et u n n e u i n gf u n c t i o np r o p o s e db y l e v y a n dm o n t a l v o ( 1 9 8 5 ) a n df i l l e df u n c t i o na l g o r i t h m si n t r o d u c e db yg ea n dq i n ( 1 9 8 7 ) a r et w ow e l l k n o w na n dp r a c t i c a lm e t h o d sf o rs e t t l i n gt h ef i r s td i f f i c u l t y t h e yh a v ec o m m o nc h a r a c t e r i fal o c a lm i n i m i z e rz ：h a sb e e nf o u n d ，w ec a n m a k eaa u x i l i a r yf u n c t i o n 、s u c ha st u n n e l l i n gf u n c t i o no rf i l l e df l l n c t i o n ，s u c ht h a t i t e r a t i v es e q u e n t i a lp o i n t s1 e a v et h ev a l l e yi nw h i c h 拼1 i e st of i n dab e t t e rp o i n t z 7i nt h el o w e rv a l l e y ( i e ，( 一) 冬( x d ) t h e nl e tz b ean e wi n i t i a lp o i n tt o s e a r c hf o rab e t t e rm i n i m i z e r i ns e c o n dc h a p t e rt w oc l a s s e so ft r a n s f o r m a t i o n f u n c t i o n sf o rg l o b a lo p t i m i z a t i o na r ed e f i n e da n di t i sp r o v e dt h e o r e t i c a l l ya n d c o n l p u t a t i o n a u yt h a tt h e yp o s s e s st h eb o t hc h a r a c t e r so ft a n n e l l i n gf u n c t i o n s a n df i l l e df u n c t i o n su n d e rs o m eg e n e r a la s s u m p t i o n si nt h i r dc h a p t e rs o n l ee a s y a n dc o m p u t a b l et r a n s f o r m a t i o nf u n c t i o n sa r ep r e s e n t e d t h e yh a v et i l eb o t h c h a r a c t e r so ft u n n e l l i n gf u n c t i o n sa n df i l l e df u n c t i o n sa sw e l l w p r o v e dt h em a i n c h a x a c t e r so ft r a n s f o r m a t i o nf u n c t i o n s ，t h a ti s ，t h et r a n s f o r m a t i o nf u n c t i o n sh a v e n 。a n yn l i n i m i z e ro rs t a t i o n a r yp o i n to nt h er e g i o n z ：，( z ) 2 ，( o ；) ) a n dh a v e a tl e a s to n em i n i m i z e ro nt h er e g i o n z ：f ( x ) “，t 1 ，2 ，m ) ) = 0 ，即妒d ，则算法终 止；否则转步3 步3 选择j ，( 矿) ，令r + - = 最n ( x i 巧z b ) ，计算y ( r + 1 ) ，转步1 外逼近方法的步骤非常简捷。它已被广泛用于凹规划、反凸规划和d c 规划 及单调规划问题，详尽的结果可参见文献 3 3 】外逼近方法的收敛性 i 扫h o r s t 等 人在文献f 3 4 1 给出 定理1 2 1 基于上述的外逼近方法，算法具有m 步终止 1 2 2 单调规划 在经济、工程及其他一些领域中的大量数学模型通常都具有某些变量或所有 d 上海大学博士学位论文 一个非常值得研究的全局优化问题之一为带有线性约束的，目标函数为凹 的最小化问题，亦称带线性约束的凹规划问题，其可表述为一定义在多面体dc 胛上的凹函数的全局极小问题： m i n c ( 嚣) i 。d ) ，d 竺缸且“i 口矗n ，i ! i ，一，m )( 1 22 ) 二十世纪七十年代。对此闯题作了非常详尽的研究3 0 多年来在对这个问题 研究过程中的很多思想被进一步应用到了更一般的d g 规划中1 9 9 4 年以前这 方面的主要成果可参见文i 敬 3 3 1 最早应用凸规划的外逼近方法被成功地应用于凹规划，以后叉被成功地应用 于反凸规划、d g 规划及单调规划问题由于定义在多面体上的四函数的最小值 在顶点上达到，所以基于上述性质可以通过构造一簇多面体序列p 13 尸23 ) d 使得用问题1 i n c ( z ) i z r 的解逼近于n l i n ( c ( z ) 【z d 的解，其中r + l 是 由多面体最添加线性约束后所构成的通过文献【3 4 】中的一个有效方法，从最导 出相应的顶点集k ，然后计算一8 9 m 2 n c ( z ) 扛k ) = n ，9 r n 讯( c ( z ) 陋p ， 并且得到序列 一) 的聚点即问题的全局最优点 我们可将外逼近方法表述如下： 步0 构造一多面体p l d ，计算它的顶点集k ，k ：= 1 步1 解问题m i n c 扛) iz r ) 的解一，即一a r g n t i n c ( z ) it k ) ，月= c ( x ) ，口sc t = m i n c ( x ) ：。d ) 步2 若z ( x ) = ( i l 口 扩 b ；，i 1 ，2 ，m ) = o ，即一d ，则算法终 止；否则转步3 步3 选择j j ( 矿) ，令r + ，= r n 扛l 巧z b ，计算v ( r + 1 ) ，转步1 外逼近方法的步骤非常简捷它已被广泛用于凹规划、反凸规划和dc 规划 及单调规划问题，详尽的结果可参见文献 3 3 1 外逼近方法的收敛性已i 拍h o r s t 等 人在文献i 3 4 1 给出 定理1 2 1 基于上述的外逼近方法，算法具有m 步终止 1 2 2单调规划 在经济、工程及其他一些领域中的大量数学模型通常都具有某些变量或所有 在经济、工程及其他一些领域中的大量数学模型通常都具有某些变量或所有 d 上海大学博士学位论文 变量的单调性的性质在最优设计的相当多数量的文章中，单调性在数值方法的 研究中起着相当重要作用当单调性与凸性和反凸性结合在一起时，产生了乘积 规划 3 3 】c 一规划 4 1 l 等等低维的非凸问题在过去的十年间，参数方法、对偶基 的补偿方法对求解低维的上述问题的速度是相当快的 下面我们考虑下述问题： m i n f ( x ) ig ( x ) i ( z ) ，z 月：)( 1 23 ) 此处，( z ) ，g ( z ) ， ( z ) 都是单调增加的( 即当osz z ，( 一) ，( z ) ，称，( z ) 为增加 的) 由考虑的抽象凸性在某种特殊假设下，此类问题可由广义外逼近方法来处 理然而，纯单调结构的最重要的优点在于利用全局信息，通过在可行域的限制区 域上的极限的全局搜索，可以用来简化问题事实上，当( 1 2 ，3 ) 的目标函数是单调 增加的，若z 为可行域已知的可行点，因在0 4 - r ：没更好的可行解，故z 在z + 兄2 上 为不起作用的类似地，当函数9 ) ( 相应地 ( 。) ) 是单调增加的，o 为在z 十尺： 卜对于约束g ( x ) 1 ( 相应地 ( z ) 1 ) 为不司行点，则整个z + r ! 可以不予考虑 基- 二上述观察，外逼近或分支定解等有效方法来可以用求解易处理的单调规划 如果存在单调增加函数g ( z ) ，使得g = z r ：f g ( 。) 1 ) ，其形如g = u 0 ，：】其中g = u ( 0 ，。】为箱子族 o ，。 的和集，z z ，则称g 是正规的当z 延2o z 为有限集时，正规集称为多胞块正像紧凸集是一簇多胞体的交集紧正规集是一 簇多胞块的交集由此，单调系统的解集结构的特征可以被建立起来，用于单调不 等式和单调优化问题的数值分析更重要的是，多胞块逼近方法可以推广到求解 两个单调增加函数差的优化问题( 亦称为d 0 函数的规划问题，比如问题( 1 21 ) ) 参见文献f 6 4 ，65 1 由于n 个变量的多项式可表为两个正系数的多项式之差，即西 个r ；卜的单调增加函数之茬，f h w e i e r s t r a s s 定理可知，在i o ，6 】= z r “i os 。s6 上的di 函数在 o ，b 1 上为稠密的，因此，d ，最优化的适用范围包括多项 式规划( 特别是非凸二次规划) 和各类仝局和组合优化问题虽然如此，但到目前 为止，解df 规划问题仍然是一个较困难的问题，在理论和算法上都没有de 规 划完备 5 上海大学博士学位论文 1 2 3 分枝定界方法 在组合最优化中解全局最优的最普遍工具是应用分支定界原理，特别地在求 解( 1 2 2 ) 时，将区域d 划分成多面体子集，即划分成单纯形( 单纯形剖分) ，划分 成超长方体( 超长方体剖分) 或划分成锥体( 锥剖分) 通常情况下，在小区域上 易确定目标函数值的上下确界，从而逼近全局最优值该方法已广泛应用于凹规 划，d c 规划及l i p s c h i t z i a a 规划 首先用分支定界方法求解下述全局优化问题： 卿他) 其中，：月”一月，dcr ”，d 为紧集，在d _ k 连续 下面介绍分支定界方法的主要步骤 步1 选择初始可行域m o ，m o3d ，把m o 划分为有限个子集聪，i i ，是指 标集这里划分要满足条件： m o = u 尬， e j 心n 坞= o m , n o - _ f ，v i ，j ，i j 其中a 鸭表示坞的边界 步2 对每个子集舰确定满足下面条件的上，下界( 舰) ，卢( 以) ： p ( 坛) i n f f ( m r d ) a ( 尬) 再令p = m i n 卢( ) li j ) ，a = m a d c o ( 慨) li ) ，则有 口s r a i n f ( d ) s0 1 步3 若a = 卢或a 一口e ，e 为充分小的正数，则算法终止否则转步4 步4 选择适当的子集m ，作更细的划分，转步2 分支定界方法的实现主要是划分、选择和定界三个运算步骤划分、选择和 定界的不同，产生相应不同的实现算法 一般地，多面体或者凸多面体的划分的最简单形式是：单纯形，超长方体和 多面锥从而划分集合由它们所组成，并且一般都假定细分是彻底的“细分 是彻底的”的定义如下： 6 上海大学博士学位论文 定义1 2 1 多面体的一个细分是彻底的，如果由连续细分多面体所产生的 每一个下降子列 m q 趋向于单点集j 凸多面体的一个细分是彻底的，如果由连续 细分凸多面体所产生的每一个下降子列趋向于一条射线 t h y 等在【6 2 中讨论了一大类单纯形的彻底的细分用的最多的是j 。：等分，参 见 2 8 】， 2 9 1 ，f 3 0 其主要思想是： 设m 是一个n 维单纯形，它是由n + 1 个仿射独立的顶点所组成的凸包 1 。y m ru 新】是m 的最长的边，令口= ；( u m ，u 玉) ，用u 分别代替顶点u x ，和”i ，这 样产生二个单纯形，其体积之和等于m 的体积这就是单纯形的二等分 设s 是一个内部含原点0 的单纯形，( 比如，令s 的n + 1 个顶点为矿= e ( = 1 ，2 ，n ) ， “+ 1 = 一e ，其中e 是第i 个分量为1 的r “中的单位向量，e = ( 1 ，1 ) r 足。) 考虑s 的 r t + 1 个斜面只，每一个只是n 一1 维单纯形对每个r ，令a 是 一个凸锥，它的顶点是原点0 ，n 条边是从0 开始，通过只的札个顶点的射线于 是 gle = l ，2 ，礼+ 1 ) 是舒的一个锥划分如果对初始的斜面进行细分，就 可以导致锥的细分所以，对扎一1 维单纯形的二等分导致的锥的细分，就是锥的 ：二等分 设m = z in z 6 是一个n 维的超长方体用个通过点 ( n + b ) 的超 平面垂直割该矩形的最k 的边，这样把矩形m 分成二个n 维的超睦方体这就是 超长方体的二等分 设凡是当前的一个划分，r 为分支定界过程的第k 迭代的细分中，所选的 划分元的集合显然，如果满足仇一1 = z ( m ) 的m r 划分是精细的，那么下 界凤一1 m i nf ( d ) 是可以改善的划分是精细的定义如下： 定义1 2 2 称划分元m cm 是吖的精细的子集如果满足 卢( m ) 卢( m ) ，n ( m ) a ( m ) t u 5 等 6 3 提出了一个选抒原则，即具有“界改善的”选抒 定义1 2 3 称选择是界改善的，如果至少在迭代有限步后，r 满足 r n 吼ip ( m ) = 阮一) o 7 上海大学博士学位论文 一般来说上界d ( m ) 比较容易定，只要取在可行域中的最小值即可较精确 地，可令 a ( m ) = m i n ，( s k ) ，s m m n d 而下界就较麻烦令m 是一个多面体，找下界p ( m ) 经常用的办法是，作，( z ) 在m 中的凸包络妒，求妒在mnd 上的极小值，以它作为下界 对于凸函数，其下界可以由下式给出【3 0 ，晴1 ： f l ( m ) = m i n ，( 矿( p ) ) ， 其中v ( p ) 是满足d n mcp cm 的凸多面体的顶点集 对于在单纯形上的d c 函数，( z ) = ( 。) + ，2 ( z ) ，其中 是凸的，2 是凹的 令妒2 是，2 在m 上的凸包络，则其下界可阻由下式给出： ( m ) = m j n ( z ) + 妒2 ( z ) z d n ，) 对于l i p s c h i t z i a n i 函数，其下界可以由： p ( m ) = m a x ( s ) 一l d ( m ) ， 其中s 是m 的任意一个非空，有限个点的集合，d ( m ) 是m 的直径，厶黾l i p s c h i t z i a n 常 数 h o r s t 等给出了分支定界方法求全局极值的收敛性质，其主要结论是下面定 理 3 1 ： 定理1 2 2 设分支定界方法中的选择是界改善的，且逐次细分的划分元的 任一下降序列 屿) 满足： 恕( a a 一卢( 坞) ) = o ， 别该方法是收敛的，即 。：。占恐。e 2 墨恐，( z 2 ) = r a i n ，( d ) = 占恐展= ：卢 8 上海大学博士学位论文 1 2 4 填充函数方法 填充函数法是由西安交通大学的葛仁溥教授等人首先提出的，参见 1 6 ， 1 7 ， 【1 8 ，【1 9 】和 2 0 】- 以后很多学者对此方法又作了许多有益的工作和改进 考虑问题( 1 1 2 ) 如果我们假设，( z ) 在彤上连续可微且满足强迫性条件： 假设1 ，( z ) 一+ o 。，当睁| | 一+ 。 则问题( 1 1 2 ) 退化为 卿，( z ) ( p ) 这是因为由假设1 知，一定存在有界闭集x 使得f ( x ) 在舻上的所有极小点都在x 的内部 介绍几个概念。 定义1 2 4 函数，( z ) 在一极小值点z 弘l 的盆谷是指一连通域毋，具有下外眭 质? ( i ) z ：b ；i ( i i ) 对于任意一点z 研使得。z ：l 义f ( x ) ，( z ：) 存在一条从z 到z i 的 下降路径 若_ ：是，( z ) 的局部极大点，则一，( z ) 在局部极小点z ：处的盆谷称为，( z ) 在 局部极大点z ：的峰 定义1 2 5 设。：和z ；是函数，( z ) 的两个不同的极小景如果，( z i ) ，( = 【；) 则称在3 ；处的盆谷彤比z ：处的盆谷日i 低，或称研比垦高 般使用填充函数方法还要求假设2 或假设2 7 假设2 f ( x ) 只有有限个极小值点 假设2 ，( z ) 只有有限个极小值 孤立点。j 处盆谷研的半径定义为： 兄2 茹忙： 如果，缸) 在z ：处的h e s s i a n 矩阵v 2 ，( z ：) 正定，则_ r 0 9 上海大学博士学位论文 填充函数算法由两个阶段步组成一极小化阶段和填充阶段这两个阶段交 替使用直到找不到更好的局部极小点在第一步里，可以用经典的极小化算法如 拟牛顿法和最速下降法等，寻找目标函数的一个局部极小值点。；然后第二步，主 要思想是以当前极小点z ：为基础定义一个填充函数，并利用它找到z z ：，使得 ，( 一) ，( z i ) 而后以一为初始点，重复第一步重复下去一毒到找不到更好的局部极小点 足 设。：是，( z ) 的一个局部极小点，文献【1 8 】中定义： 定义1 2 6 函数p ( z ，。：) 称为，( z ) 在局部极小点z ：处的填充函数，如果满 ( 1 ) ，x ：是p ( z ，z ：) 的一个极大点，( z ) 在点z ：处的盆谷b ；成为p ( 。，z ：) 的峰 的一部分 ( 2 ) v ( z ，z ：) 在比b ；高的盆谷里没有稳定点 ( 3 ) 如果存在比研低的盆谷奶，则存在b ：使得p ( 。，z ：) 在z 7 和z ：的 连线上有稳定点 在各种文章中对填充函数的定义有所不同，尤其( 3 ) 是一个很强的要求条件 很多文章做了改进 葛等人定义了一个两个参数的函数 聊，卯) = 南吲一学) 后来他们注意到这个函数存在缺陷，由于受到指数项“p ( 一监亏掣) 的影畹 当p 太小或忙一z ；l 太大时，p ( x ，z i ，n p ) 和v p ( z ，z ：，n p ) 几乎都不会变化，为 1 0 上海大学博士学位论文 了克服缺陷，葛和秦在 1 7 】给出了七个填充函数： 即，味_ 萨南唧( 一宇) ， c ( z ，z ：，n p ) = 一p 2 l o g r + ，( z ) 】一l l z 一。：1 1 2 ， 0 ( z ，。：，- p ) = 一p 2 l o g r + ，( z ) 】一i i z z ：忆 q ( z ，z ：，a ) = 一 ，( z ) 一，( z ：) ie x p ( a l l z z ：i | 2 ) ， q ( z ，z ：，a ) =