（机械设计及理论专业论文）工程中非凸非光滑优化算法及其可视化系统的研究.pdf

文义优化设计理究开发求解一求解复杂工程优化设计问题的驾驭式可视化软件系统。不可微性和非凸性是自然界的普遍现象，目前捆集法已成为求解一般非光滑优化问题的主要方法。针对工程实践的需要和捆集法数值实现的困难性，本文详细研究了一般捆集法数值实现的关键技术。提出了一个计算次梯度的数值方法及其相应线搜索规则的数值实现方法，并针对捆集法的二次规划子问题提出了一个求解一般半正定二次规划的稳定数值方法：将针对凸规划的e 次梯度捆集法推广到了一般非凸非光滑问题并证明了其收敛性，较好地克服了参数e 对算法性能的影响；在现有割平面捆集法的基础上，率先提出了一个针对非凸非光滑问题的变尺度因子校正方法，较好地克服了函数尺度变化对算法的影响，在一定程度上加速了算法的收敛；针对e 一次梯度捆集法稳定性较好但搜索效率稍差和割平面捆集法搜索效率较好但稳定性稍差的特点，提出了个结合两者优点的混合型捆集法；针对实际优化问题的复杂困难性，提出了一个随机复合形算法及一个结合该算法与实数编码遗传算法的混合型随机算法，并研究了捆集法与这些随机算法相结合的方式，在保持捆集法计算效率的前提下，增强了捆集法的数值稳定性，拓宽了捆集法的适用范围。然后在此基础上，研究并实现了优化计算中的驾驭式可视化系统。、通过该软件，用户能对优化计算过程进行实时监控，观察分析计算结果，重新选择算法和初始点，重新设置算法的相关参数并对数学模型作必要的修改后再继续计算。最后给出了上述算法和软件系统在若干实际工程优化设计实例中的应用，并提出了若干尚待进一步研究的问题。7 本文的研究在捆集法及其在实际工程优化设计中的应用方面取得了一些实质性的进展，为工程优化设计提供了一系列对模型的数学性态没有特殊要求的、效率较好、可靠性较高的计算工具，并实现了一个用于优化计算的驾驭式可视化系统适应面广，具有一定的实用价值。卜、l关键词：最优工程设计：非凸非光滑优化，捆集法，数值计算，科学计算可视化，可控可视优化计算系统华中科技大学博士学位论文a b s t r a c tt h i sr e s e a r c hi ss u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a( n n s f c ( 打a 1 1 tn o5 9 6 3 51 5 0 ) ，t h em a i np u r p o s eo ft h i sp a p e ri st od e v e l o pas e r i e so fe m c i e mo p t i 如- i z a t i o na l g o r i t h m sf o rn o i l s m o o t ha n dn o n c o n v e xp r o b l e m sm s i n gi np r a c t i c a le n g i n e e r i n go p t i m a ld e s i g na n dt h em e t h o d st oi i i l p l e m e mt 1 1 e mn u m e r i c a l l yav i s u a l i z e ds t e e r i n go p t i i l l i z a t i o ns y s t e mi sa l s os t u d i e dn o n s m o o t l l n e s sa 1 1 dn o n c o n v e x i t ya r ec o m m o np h e n o m e n ai 1 1n a t u r ea n d 撕s ei nal a 唱ec l a s so fe n g m e e r i n g 印p l i c a t i o n sa j le x i s t i n gt r a d m o n a lo p t i m i z a t i o nm e t h o d sc a nn o ts o i v es u c hp r o b i e m sb e c a u s eo f t h en 0 1 1 s m o o t t l l l e s sn o wt 至l em o s tp r o m i s i n gm e t h o d sf o rg e n e r a ln o n s m o o t ho p t i m i z a t i o ns e e mt ob et h eb u n d l em e t h o d sb u tb u n d l ea l g o r i t h m sd e v e l o p e da tt h em o m e n ta r ed i f f i c u l tt oi m p l e m e n tn u m e f i c a l l yb e c a u s eo f t h en e e dt oc o 1 p u t eas u b g r a d i e n te x a c t l ya n dc a nn o tm e e tt h en e e d so f e n g i n e e r i n gd e s i g nt h em a t e r i a lo ft h i sw o r ki so r g a n i z e da sf 0 1 l o w sf i f s t ly ，n u m e r i c a lm e t h o d sf o ri m p l e m e m i n gb u n d l em e t h o d sa f es t u d i e di nd e t a i la ne m c i e n tn u m e r i c a lm e t h o df o rc o m p u t i n gas u b g r a d i e n ti sg i v e na n dt h en u m e r j c a m p l e m e n t a t i o no ft h ec o r r e s p o n d i n gl i n e s e a r c hm l e sa f ed i s c u s s e da na l g o r i t h mb a s e do ng i l l & m u r i 了。sa l g o r 油mf o rg e n e r a lp o s i t i v es e m i d e f 血t eq u a d r a t i cp r o g r 锄m i n gi sa l s og i v e n ，w h i c hc a ns 0 1 v es u b p r o b l e m sa “s i n gi 1 1e a c hi t e f a t i 0 丑o fb u n d j em e t h o d se m c i e n t l ya n dn u m e r j c a ls t a b 】ys e c o n d ly a na l g o r i t h mf o rn o n s m o o t ha n dn o n c o n v e xp r o b l e m sw h i c hi sb a s e do nl e m a r e c h a l s- s u b g r a d i e mb u n d l em e t h o di sp r o p o s e d ，a n dt h e r ei sn on e e dt og i v et h ep r i o rc h o j c eo ft 1 1 ea p p r 0 ) 洫a t i d dt 0 1 e r a n c ei nt 1 1 i sa l g o r i t h mt h ec o n v e 曙e n c eo ft 1 1 ea l g o r i n l mi sp r o v e da n ds o m en u m e r i c a lr e s u h sa r es h o w nt h i r d ly an e wp r o x i m a lb u n d l em e t h o df o rn o n s m o o t ha n dn o n c o n v e xp r o b l e m si sp r e s e m e dt h ew e i 曲血gt e c h n i q u et oo v e r c o m et h es e n s i t i v i t yt ot h es c a l i n go fo b j e c t 如n c t i o ni sd i s c u s s e di nd e t a i l t h ec o n v e r g e n c eo fm ea l g o r i t h mi sp r o v e da n ds o m en u m e r i c a lr e s u l t sa r ep r e s e n t e da na i g o r i t h mw h i c hc o m b i n e st h ea d v a n t a g e so f l e m a r e c h a l s一s u b g r a d i e n tb u n d i em e t h o da n d 酗w i e l sc i l 仕i i 培p l a n eb u n d l em e t h o di sa l s op r o p o s e df o u n h l y ，i no r d e rt os 0 1 v ec o m p l e xa n dm - c o n d i t i o n e dp r o b l e m sa r i s i n gi np r a c t i c a le n g i n e e r i i l go p t m 脚d e s 培n ，s o m ee 岱 c t i v er a n d o ms e a r c hm e t h o d si n c l u d i n gg e n e t i ca l g o d t h ma r ed i s g u s s e da n dt h em e t h o dt oc o m b i n eb u n d i em e t l l o d sw i t l lt h e s er a n d o mm e t h o d si ss n l d i e dni s 印p a r e n tt h a tn os i l l 9 1 eo p t i m i z a t i o nm e t h o dc a ns o l v ea l le n g i i l e e r i n go p t i m a ld e s i g np r o b l e m sb e c a u s eo ft h ec o m p l e x i t i e so fr e a lw o d d t h e r e f o r a 1 1i n t e g r a t e dv i s u a h z e ds t e e r i n go p t i m i z a t i o ns y s t e mw h j c hc o m p r i s e ss o m ee 岱：c t i v ea l g o r i t h m sf o r、，1-r，_华中科技大学博士学位论文g e n e r a ln o n h n e a rp r o 乒锄m i n gi sd i s c u s s e d t h e 如n c t i o na n dt h es t r u c t u r eo fs u c has y s t e mi ss t u d i e di nd e t a i l ，a n dt h es y s t e mc a np r o v i d ee n o u g hm e a n st oi n t e e n ei m o 血eo 面m i z a t j 0 丑p _ r o c e s s ，s u 曲a s 咖晒丑g 出ec d m p u 掘亡j o 丑o fa 丑a j g o 一如脚，0 b 鲫叫n g 锄da n a i y z i l l gt h ep r e s e n tr e s u l t s ，m o d 酊i n gt h eo p t i m a ld e s i g nm o d e la d j u s t i n gt h ei n i t i a lp o i n ta t l ds w i t c h i n ga l g o r i t h m s ap r o t ，p eo fs u c has y s t e mi sr e a l i z e df i n a l l ms o m ep r a c t i c a lo p t i m a ld e s i g np r o b l e m sa r es 0 1 v e db ya l g o r i t h m sp r o p o s e di nt h i sp a p e rt h er e s u l t ss h o wt h ee 俑c i e n c yo f t h e s ea l g o r i t h m st h ef e s e a r c ha c q u j f e ss o m ea c h i e v e m e n t si np r a c t i c a ln o i l s m o o t ha n dn o n c o n v e xo p t i m a lc o m p u t a t i o nf u n h e rr e s e a r c hd i r e c t i o n sa r ea l s os u g g e s t e dk e y w o r d s ：e n g i n e e r i n go p t i m a ld e s i g n ，b u n d l em e t h o d s ，n u m e r i c a lc o m p u t a t i o n ，o p t i m i z a t i o ns y s t e mn o n s m o o t ha n dn o n c o n v e xo p t i m i z a t i o n ，s c i e n t i f i c s u a l i z a t i o n ，s u a l i z e ds t e e r i n g华中科技大学博士学位论文第一章绪论1 1 工程优化设计及优化算法的发展概况工程优化设计以优化理论和数值计算方法为基础，以计算机为工具，在现代设计理论的指导下，尽可能考虑各方面的复杂因素，在多种制约条件下，通过寻优工具( 包括数值和非数值) 寻找满足预定目标的最优或更好的设计方案。实践表明，通过优化设计方法可以有效地提高设计质量，缩短设计周期，获得显著的经济效益。因此优化设计方法一开始就得到了人们的广泛重视，并己成为现代设计方法学的重要内容。在国际上，优化技术从二十世纪六十年代起迅速发展起来，七十年代走向成熟。无约束优化的数值算法、非线性规划( 包括罚函数法、拉格朗日乘子法、广义简约梯度( g r g ) 法、序列二次规划( s q p ) 法等) 、动态规划法、目标规划法、几何规划法、整数规划法以及随机规划法都是在这期间提出的。国内研究从二十世纪七十年代中期开始，近二十多年来发展迅速，开发研制了非线性优化、混合离散变量优化、随机变量优化、多目标优化、遗传算法和优化设计专家系统等一系列优化计算软件和工具，并在工程应用中取得了显著的效果，文献 1 4 对此作了一个概括性的总结。随着社会的进步和技术手段的发展，在优化设计中需要考虑的因素越来越多。在现代设计中，不仅要考虑产品设计的技术性和经济性，还要考虑产品的市场需求、售后服务、绿色环保等与设计相关的各个环节；不仅要考虑零部件的优化，还要考虑整个产品系统的优化；不仅要考虑产品某个阶段的优化设计，还要考虑把产品的整个生命周期作为一个整体进行优化。优化设计正在向产品设计的全系统、全过程方向发展，并需要考虑产品的整个生命周期【5 1 。与此相应，工程优化的模型也越来越复杂，越来越大型化，依靠传统的设计理论和优化方法难以对大型复杂系统进行有效的优化设计，这对设计理论和优化方法都提出了新的要求。因此人们在优化设计方法上陆续提出了多级( m u l t i l e v e l ) 或分级( h i e r a r c h i c a l ) 优化设计方法、” 、广义优化设计方法玷1 叫和多学科综合优化设计方法( m u l t i d i s c i p l i n a r yd e s i g no p t i m i z a t i o n ) 【1 “，这些方法都具有并行性的特点。多级或分级优化设计方法是针对复杂大系统的求解在二十世纪八十年代初提出的，其基本思想是将产品分解为若干个子系统，并分别对各子系统进行求解，然后根据子系统之间的关系采用某种合适的策略获得产品在整体上尽可能最优的结果；广义优化设计主要由国内一些设计专家提出，其概念的内涵一直在发展，文献 5 1 0 对其理论作了较为系统的研究，明确提出了优化设计应面向产品的全系统、全性能和全过程，并考虑产品的整个生命周期。整个优化设计过程应包括优化设计建模、优化计算以及对优化计算结果的分析与评价三个部分；不仅要考虑参数优化设计，还要考虑方案优化设计；在优化策略上，应使用结合传统优化方法的智能优1华中科技大学博士学位论文化方法，并采用分部件、分性能、分层次和分步骤的、结合计算机网络的分布式串并行协同优化策略 5 ；多学科优化设计方法则是在多级或分级优化设计方法的基础上发展起来的，并借鉴了集成制造技术和并行工程的基本思想。它面向产品的整个系统和全生命周期，将单个学科( 领域) 的分析与优化同整个系统中互为耦合的其它学科的分析与优化结合起来。通过充分利用各个学科( 子系统) 之间相互作用所产生的协同效应，以期获得系统整体上的( 近似) 最优解，并通过实现并行设计，来缩短设计周期，从而使研制出的产品更具有竞争力。在多学科综合设计优化中，学科是指产品设计的不同阶段或所包含的部件及性能等等的泛称。由此可见广义优化设计与多学科综合优化设计的主要思想是相同的，两者均有值得相互借鉴之处。综上所述，现代优化设计已经开始面向产品的整个系统，并需要考虑产品整个生命周期中与设计有关韵各个环节、各种因素，传统的优化设计正在向多学科综合的广义优化设计发展。随着优化设计中考虑因素的增多，在工程优化实践中出现了大量的非凸非光滑优化问题，并常常含有离散变量和多个局部最优点，传统的优化方法无法有效地求解这类问题，这对优化的理论和方法都提出了新的要求。研究开发对模型的数学性态没有特殊要求的并尽可能找到全局最优解的高效率高可靠的优化算法已成为工程优化设计的追切需要“1 。从工程应用角度出发，人们陆续提出了与传统优化方法显著不同的模拟退火算法“6 、“ 、遗传算法 1 ”2 ”和神经网络优化方法o “2 “。设计这些方法的出发点是要尽可能找到复杂优化问题的全局最优解。这三种方法，特别是模拟退火算法和遗传算法，对模型的数学性态没有特殊要求，具有广阔的应用领域，已成为现代优化计算中寻找困难问题近似全局最优解的主要方法。用于优化问题的神经网络主要有h o p f i e l d 网络和b o l t z m a n n 机，其理论基础是动力系统的李雅普诺夫稳定性理论，其目标是获得能量函数的极小点，即动力系统的稳定状态。h o p f i e l d 网络是确定性网络，一般只能得到能量函数的局部极小点：b o l t z m a n n 机则是随机型网络，通过采用模拟退火算法，能使能量函数以很大概率收敛到全局最优点【1 6 、1 “ 。对于不同的优化问题，神经网络优化方法需设计不同的模拟电子线路，若直接求解动力系统方程，又将依赖于偏微分方程的数值求解，计算量很大，而且偏微分方程数值解法本身往往也是非常复杂和困难的( 如刚性问题等) ，因而在实践中很少使用。相比之下，模拟退火算法和遗传算法则在工程优化实践中获得了广泛的运用。模拟退火算法由k i r k p a t r i c k 等在1 9 8 2 年提出，以求解n p 完全的组合优化问题的近似全局最优解。在实际计算中模拟退火算法收敛一般较慢，人们对此提出了许多改进方法，如快速模拟退火算法等“6 。“2 3 。遗传算法由h o l l a n d 在1 9 7 5 年提出“，其思路与其它优化方法显著不同。它模仿自然界的自然进化过程，能充分利用全局信息，具有很强的适应性。遗传算法主要由复制、杂交和变异三个算子组成，以不同的概率执行杂交和变异算子，其中以杂交算子最为重要，这也是遗传算法区别于2华中科技大学博士学位论文其它随机型搜索方法的根本所在。正是通过杂交算子的作用，遗传算法能高效地搜索空间中尚未检测的部分，以很大的概率找到全局最优解口。为进一步提高遗传算法的效率，人们又提出了演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 口们的思想。演化计算程序的基本结构和遗传算法相同，但编码不再局限于二进制，遗传算子也不再局限于复制、杂交和变异三个算子，而采用具体问题具体分析的方法，针对特定问题采用特定的编码和数据结构，并引入包含问题相关知识的遗传算子，结合遗传算法的基本思想，以期在保持算法稳定性的同时，获得较好的计算效率。事实上，在实践中运用成功的遗传算法中，其遗传算子大都是经过改造的【2 ”2 ，往往需要其它与问题相关的知识。因此，遗传算法在函数优化领域的成功运用仍将需要传统优化的思想和方法以引入新的遗传算子。应该指出的是，目前提到的遗传算法常常是指包含演化计算思想的新遗传算法，和原来的基本遗传算法已有很大差别，这使得遗传算法和其它演化算法的界限变得模糊不清了汜5 、2 6 。除模拟退火算法和遗传算法外，人们也研究了其它全局最优化方法。这些方法可分为确定型方法和随机型方法( 包括人工智能启发式寻优方法) 两大类。在随机型方法中，除上述算法外，还有聚点分析法”、统计模型法 3 “、禁忌搜索“。、s ”等，其中禁忌搜索是一种采用概率的启发式优化方法，在国际上也得到了广泛的重视，并正在溶入到演化计算方法中，成为优化计算领域的一个重要研究方向。确定型方法主要研究如何跳出局部最优解并尽可能逼近全局最优解，一般需要先计算出( 近似) 局部最优解，依赖于计算局部最优解的方法。该方法目前主要有轨道法( t r a j e c t o r ym e t h o d ) m 1 、“隧道”方法0 2 1 和填充函数法 3 3 等。总的看来，目前在计算实践中较为成功的全局最优化方法主要是随机型方法，特别是遗传算法。虽然模拟退火算法和遗传算法具有强大的搜索能力，但通常收敛较慢，计算量巨大，在求解规模适中、变量取值范围较大的优化问题时，往往需要巨型并行计算机。在实际计算中模拟退火算法和遗传算法的成功还依赖问题本身的性态，对一些问题较为有效，而对另一些问题则收敛缓慢o “” 。与专门的优化方法相比，模拟退火算法和遗传算法的效率要差许多。因此针对工程实践中非凸非光滑现象越来越突出的情况，人们也希望将传统的、高效率的、稳定性好的非线性优化算法直接推广到求解一般非光滑优化问题，以获得速度快、效率高、适应面广的确定性( 局部) 寻优方法，并进一步发展传统的优化理论和方法。正是由于工程实际的需要，国际上对非光滑优化的理论和方法的研究从二十世纪六十年代起迅速开展起来，迄今为止人们已提出了多种针对非光滑优化问题的算法，如拟微分方法”l 、信赖域方法【3 ”“、针对极大极小问题的极大熵算法【4 ”】、针对一般非光滑问题的次梯度法”划( s u b 酊a d i e n tm e 也o d ) 和捆集 去f ”l ( b u n d i em 劬o d ) 等。传统的确定性优化方法( 包括不使用导数的直接搜索方法) 无法求解工程优化实践中出现的非光滑优化问题“”5 7 “7 “，因此必须建立新的理论和方法。目前非光滑分析的理论与方法在国际上已得到了广泛的重视，但由于其理论较华中科技大学博士学位论文为深奥，方法较为复杂，计算效率和数值稳定性都有待于进一步改进，因此在工程实践中尚未得到广泛的运用。非光滑优化方法与演化计算方法( 包括智能优化方法)己成为现代优化设计中算法方面研究的主要内容。在工程优化设计中，除了算法方面的研究外，优化建模和对优化结果的分析与评估也已成为现代优化设计中的重要组成部分o 、8 。目前优化设计在工程实践中未能得到广泛应用的一个主要原因就是优化计算没能与优化建模及其它辅助设计工具如c a d c a m 有效地结合在一起o “。随着优化设计中考虑因素的增多以及系统集成的需要，对优化结果进行分析和评估越来越重要，也越来越困难。由于现代优化设计已面向产品的整个系统和全生命周期，模型的高度复杂性和巨大规模已使任一种优化算法无法应付，不得不采用分阶段、分部件、分层次的串并行协同优化方法，不同阶段、不同部件的优化设计结果需要不断进行反馈、协调，以获得系统的整体近似最优，这也对优化结果的分析与评价提出了新的要求。在整个现代优化设计过程中，优化计算只是其中的一部分，并仅针对产品设计的某一部件、某一阶段，优化问题模型中的各种量化关系，如目标函数、约束函数等，难以完美无瑕地反映出实际问题要求的各个方面，设计人员还需对优化结果的合理性进行分析，根据产品整个系统的需要以及设计方案付诸实施时所受到的实际工业过程的限制对优化结果作必要的调整，分析甚至修改优化的数学模型。优化建模和优化结果之间需要不断进行反馈、协调，传统的人工建模方法和对优化结果的人工分析评价方法己无法满足这种需要。同时由于实际工程优化问题的复杂性和数值计算的固有精度限制，无法找到一种对各种问题都能保持数值稳定的优化算法，现有的每种优化算法在实际计算中都有着其优缺点和相应的适用范围。对一个复杂的优化问题，可能需要用到多个优化算法进行计算。然而目前的优化软件通常是单个算法的简单集成，难以有效地综合利用，设计人员无法对计算过程进行监控和实时干预，在计算过程中切换算法也较困难。同时由于问题的复杂性和巨大的规模，设计人员难以对庞大的计算数据作出准确的分析和评价。因此有必要引入可视化技术，研究面向设计全过程( 包括建模和评价) 的、包括多种算法的、具有可控可视功能的、综合求解复杂优化问题的软件系统。在该系统中，用户应能建立和修改优化模型，并能在计算过程中实时观察算法的运行情况，及时中止算法的执行，观察分析计算结果以及优化模型在当前点处的数学性态，修改算法的各种敏感参数，改变初始点，甚至修改数学模型，然后再调用其它合适的算法继续计算。综上所述，传统的优化设计正在向多学科综合的广义优化设计发展，优化方法在横向上正在向人工智能优化、并行协同优化和演化计算方向发展，在纵向上正在向非凸非光滑优化方向发展。多学科综合的广义优化设计在工程实践中的成功运用将依赖于以下三个方面：1 具有并行特征的智能设计方法和优化方法的研究与开发，如整个产品系统的解耦与分解方法，多学科( 领域) 协同优化方法，大规模复杂优化问题的分布式算法等。4华中科技大学博士学位论文2对模型的数学性态没有特殊要求的、高效率高可靠的串行算法的研究与开发。3 面向设计全过程的、包括建模工具和分析评价系统的、具有可控可视功能的优化软件系统的研究与开发。对于上述三个方面，国际国内学术界正在展开积极的研究。文献 5 1 3 、7 1 、7 2 对第一个方面进行了较为系统深入的研究，代表着现代优化设计理论与方法的最新成果。第二个方面主要体现在非凸非光滑优化方法和演化计算方法的研究与开发方面。目前国际上在非光滑优化算法方面已提出了一系列实用的算法，但主要是针对凸问题，对于非凸非光滑闻题，实用的算法还很少，计算效率和数值稳定性尚不能令人满意，离工程应用尚有一段距离，而非凸非光滑却是现代工程实践中普遍出现的现象；演化计算方面的研究目前则正是方兴未艾，已发表了大量的文章和专著”2 2 7 、7 4 “，获得了许多成功的算例，缺点是收敛较慢，往往需要用到巨型计算机。在可视化优化软件系统方面，目前解决的问题多为组合优化问题，而且通常是针对特定问题，如线路规划问题等 8 “；或是针对特定的优化算法，如单纯形法、模拟退火算法的可视化等“，针对一般非线性规划的研究则很少，驾驭式的可视化优化计算系统更是少见。从工程优化设计的实际需要出发，本文将着重研究针对一般非凸非光滑优化问题的实用算法，试图在工程优化算法方面取得一些实质性的进展，获得收敛较快、适应面较广的优化设计计算工具。然后在此基础上，针对复杂的、数学性态很差的优化问题研究了结合非光滑优化算法与随机搜索方法( 包括演化计算方法) 的实用算法，以进一步提高算法的数值稳定性并拓宽算法的适用范围；针对实际工程优化问题的复杂多变性研究并实现了一个用于优化计算的驾驭式可视化软件系统，试图为研究针对一般非凸非光滑问题的、寻找问题全局最优解的演化计算方法和智能优化方法打下一个坚实的基础。1 2 非光滑优化方法的发展概况非凸非光滑是自然界的普遍现象。随着优化设计的发展，在工程应用中出现了大量的非光滑优化问题，并常常表现出非凸的特点。文献 5 8 、6 0 、8 3 给出了工程应用中常见的非光滑优化数学模型。正是由于工程实际的需要，非光滑优化的理论和方法从二十世纪六十年代起迅速发展起来。传统的使用导数的优化方法无法求解非光滑优化问题1 5 0 】。这是由于：一是停止准则不再适用。例如对于无约束光滑问题，可f ( x ) 存在且连续，并在极小点x 处有v f ( x 。) = o ，因此当x 靠近x 时，i p f ( x 一定非常小，固此终止条件常常是忭f ( x ) 4 c s ，而对于非光滑优化问题，则没有类似的结果，如考虑函数f ( x ) = h ，o5华中科技大学博士学位论文是其最优点，而对x ；o ，均有f 甜( x ) i = 阿( x ) i = l ；二是对于非光滑问题，存在着w o l f e：指出的“折线收敛于非解”的现象【5 “，如用精确搜索的最速下降法求解非光滑问题1时，可能产生一个收敛于非稳定点的点列 x 。) ；三是对于光滑问题，负梯度方向总是下降方向，而对于非光滑问题，则不是这样，并不是所有次梯度的反方向都是下降方向。例如考虑函数f ( x ) = h ，在x = o 处，甜( o ) = 卜1 ，1 ，而1 和+ 1 均不是下降方向。同时，实际计算表明，传统的不使用导数的直接搜索方法，如h o o k e j e e v e s方法、p o w e u 方法等也无法求解非光滑优化问题郾】，这主要是因为非光滑优化问题的数学性态往往很差，直接搜索方法一般无法找到一个有效的下降步长。因此对于非光滑问题必须建立新的优化理论和方法。国际上对非光滑方法的研究可追溯到1 9 6 0 年由k e l l e y 、c h e n e y 和g o l d s t e i l l 提出的针对凸规划问题的k c g 割平面法队8 ”。随后，关于非光滑分析的理论研究迅速发展起来。人们首先将经典的导数、微分推广到了凸函数，提出了次梯度和次微分的概念。文献【8 6 】针对实际应用概括了凸分析的主要成果，其出版标志着凸分析正式成为个学科。紧接着人们开始尝试把凸分析的主要结果推广到非凸函数( 局部l i p s c h i t z 连续函数) ，这是一项漫长而困难的研究。目前这方面的工作大致可分为两大流派：西方学者的工作和前苏联学者的工作。西方学者的工作主要以if h c i a r k e 8 7 】、j p _ a u b i n 和i e k e l a i l d ”8 9 】为代表；前苏联学者的工作则以f d e m v a n o 、，f 3 q和a d i o 仃e l ”】为主。从应用角度上看，文献【8 6 、8 7 】的理论成果目前在非光滑优化，算法的研究中占据着主导地位，事实上己成为研究非光滑优化算法的理论基础。根i据文献 8 6 、8 7 】，非光滑分析的主要结果可概括如下：i( 1 )设s 是p 中非空凸集，f 是定义在s 上的实函数。如果对任意x ，y 。s及每个x o ，1 ，均有：f ( 五x 十( 1 一五) y ) 胛( x ) + ( 1 一五) f ( y )则称f 是凸集s 上的凸函数。( 2 )设x 是p 的子集，若存在一常数k o ，对任意x ，y 。x ，均有l f 【曲- f 【y ) i k l l x - y 1 |i则称f 在x 上是l i p s c h i t z 连续的，其l i p s c h i 乜常数为k ；若f 在p 的任意有界子集上都是l i p s c h i t z 连续的，就称f 在p 上是局部l i p s c h i t z连续的；若f 在点x 附近的某个邻域里是局部l i p s c h i 乜连续的，就称f在点x 附近是l i p s c h i t z 连续的。( 3 )函数f ( x ) 在点i 处沿方向de 肿的方向导数定义为：f ( 刈) 二协塑半盟其中t io 表示t 从。的右边趋于o ( 即t o ) 。6华中科技大学博士学位论文( 4 )设f ( x ) 是凸函数，则f ( x ) 任意在点x 附近是l 啦s c h i t z 连续的，且对任意d p ，f ( x ) 在点x 处沿方向d 的方向导数f ( i ；d ) 均存在，并对v y s ，有f ( y ) f ( x ) + ( v f ( x ) ) 1 ( y x )( 5 )设f 承n _ 一 取是凸函数，若j ；m “，对任意v i r n 均有：f ( y ) f ( i ) + 7 ( y x )则称e 是在点x 处的一个次梯度( s u b g r a d i e n t ) 。称函数f ( x ) 在点x处所有次梯度所构成的集合为f ( x ) 在点x 处的次微分( s u b d i f f e r e n t i a l ) ，记为a 。f ( x ) 。对于凸函数f ( x ) ，a 。f ( x ) 是个有界的非空闭凸集，且有：f7 ( x ；d ) = m a x ( 7 d v ；a 。f ( x ) )( 6 )定义f 在点x 处沿方向d 。珏p 广义方向导数m 1 为：f 。( x ；d ) ：l i m s u p 迎苎坚塑磊1并且若存在；p ，使得对任意d p ，均有f 。( x ；d ) 写1 d则称e 是f ( x ) 在点z 处的( 广义) 次梯度。由f ( x ) 在点x 处所有次梯度所构成的集合称为f 在点z 处的( 广义) 次微分，记为a f ( x ) ，即：a f ( x ) = f ；t “j f 。( x ；d ) ；7 d ，v d t “)( 7 )当f 在点x 附近是l 币s c h i t z 连续的时，a f ( x ) 是一个非空有界的闭凸集，且f 。伍d ) = m a x 能1 d f v 砑( x ) )( 8 )当f 是p 上的局部l i p s c h i t z 连续函数时，f ( x ) 在r 上几乎处处可微，且集合m ( x ) = 馐瓜。f 存在序列( x i ，使f 在x 处可微且x 。斗x ，v f ( x 。) 叶劬非空并成立：7华中科技大学博士学位论文甜( x ) = c o i 】_ v m ( x ) 。( 9 )对于局部l i p s c h i t z 连续函数f ( i ) ，钟( ) 是上半连续的，即对任意序列 x i ) ，x i x ，g 。a ! f ( x 。) ，g 为序列( g i ) 的某个聚点，则必有g 甜( x ) 。( 1 0 ) 若f ( x ) 是凸函数，则点x 是极小点的充分必要条件是o 6 f ( x ) ，即x 是f ( x ) 的稳定点。( 1 1 ) 设f 在点x 附近是l i p s c h i t z 连续的，若点x 是f ( x ) 的局部最优点，则0 甜( x ) ，即x 是f ( x ) 的稳定点。( 1 2 ) 设f 在点x 附近是l i p s c h i t z 连续的，则甜( x ) 是一个非空的闭凸集，若。仨甜( x ) ，则1 1 + i l = 。蝤! 、l l ；i po 且d = 一+ 是f ( x ) 在点x 处的下降方向。# d ix )( 1 3 ) 记乏( y ) = f ( x ) + 7 ( y x ) ，t ( y ) = m a x 乏( y ) ；a f ( x ) )设f 在点x 附近是l i p s c h i t z 连续的，则问题r n i nt ( x + d ) + 纠圳2 有唯一d 碾“2 ”解d + ，且有d = 一l + ，其中| | ；+ j p 趔! 、惦肌当。诺钟( x ) 时，d + 即函t t i j数f ( x ) 在点x 处的下降方向。上述结果构成了研究非光滑优化算法的基础。在非光滑优化算法方面，大致可分为两大类：一类是专门针对特殊问题设计的算法，如针对复合非光滑优化问题的信赖域方法口”4 ”、针对极大极小问题的极大熵算法h ”j 等，这类算法对函数的形式有着特殊要求，通常是将非光滑问题化为光滑问题后再求解。另一类则是针对一般非光滑优化问题的算法，仅要求函数是局部l i p s c h 娩连续的，这类算法主要有次梯度法 5 0 1 和捆集法【5 0 ”。由于这类算法的广泛适用性及潜在的理论和应用价值，很快引起了国际学术界的重视。次梯度法主要是由前苏联学者如s h o r 、e 衄o l i e v 和p o l v a k 等从1 9 6 4 年起逐渐发展起来的，基本思想是把解光滑问题的下降方法中的梯度用任一次梯度来代替：将最速下降方法中的梯度用次梯度来代替便得到经典的次梯度法；将变尺度法中的梯度用次梯度替代并对变尺度矩阵h 的校正稍作改进便得到空间扩张法和椭球法。次梯度法有以下主要缺点：一是由于并不是所有次梯度都是下降方向，而且一般不可微点处的次梯度集合是一个无限集合，因此算法本身并不是一个下降算法；g华中科技大学博士学位论文二是次梯度法没有一个在理论上可行的停止准则，这是因为对光滑无约束问题，目标函数在极小点的梯度一定是零，而对于不可微问题则没有类似的结论。总得看来，次梯度法是非线性光滑优化方法的平行推广，在理论上缺乏有力的支持，但结合算法的参数调整在某些问题的实际计算中仍可取得较好的计算效果。文献 4 8 、4 9 对次梯度法作了全面总结。为克服次梯度法的上述弱点，人们从1 9 7 5 年起陆续提出了共轭次梯度法印5 “s ：、。”、一次梯度法1 5 2 、5 3 1 和割平面捆集法【5 6 “。文献 5 2 、5 3 】首先提出了捆集法( b u n d l em e t h o d ) 的基本思想( “捆集法”的提法见文献【5 0 】，文献【5 1 则将之称为“束法”) ，并指出捆集法可有两种基本形式：源于最速下降算法的次梯度捆集法和源于k c g割平面法的割平面捆集法或称为广义割平面法。为克服计算过程中的锯齿现象，文献f 5 2 、5 3 在【9 1 的基础上给出了第一个实用的捆集算法一次梯度法。文献 5 6 则在 5 2 5 5 】的基础上，给出了系列实用的割平面捆集法。由于捆集法有着良好的理论背景和停止准则，实际计算的效果也要优于次梯度法，因此该方法目前已成为求解一般非光滑优化问题的主要方法。捆集法的基本思想就是通过一簇次梯度( 即“捆集”或“束”) 来构造一个对非凸非光滑函数的的分片线性逼近，然后通过该逼近函数找到一个较好的下降方向。在算法的每次迭代中，捆集法引入了严格步长和零步长的概念，并保证两个严格步长之间只有有限个零步长。当出现零步长或小步长时，采用次梯度方法的策略移动到附近某个可微点处并计算该点处的梯度，然后把该梯度加入到以前计算的梯度集合捆集( b u n d l e ) 中形成一个新的捆集，以便在下次迭代中通过新的捆集在当前迭代点附近对目标函数构造一个更好的线性逼近，从而找到一个更好的搜索方向。e 一次梯度捆集法和割平面捆集法都是通过解一个由一组次梯度及其逼近误差形成的半正定二次规划子问题来求得下降方向。e 一次梯度捆集法可看作是最速下降法的推广。根据前面的结论( 1 2 ) ，当。芒a f ( x ) 时，盛现、l l ； l 的解；的负方向d = 一；州；+ 是f ( x ) 在点x 处的下降方向。注意到f 。( x ；d ) = m a ) 【( 1 d i v ；甜( x ) ) ，于是d + 实际上是下面问题的解：血nf 。( x ；d )s t | | d i 喀1 ，d 己“当f ( x ) 光滑时显然f 。( x ：d ) = ( v f ( x ) ) 7 d ，这时上述问题的解是d + = 一v f ( x ) 州v f ( x ) ，这就是经典意义下的最速下降方向。但对于非光滑问题，不可微点处次梯度集合往往是一个无限集合，在实际计算中不可能得到不可微点处的一9华中科技大学博士学位论文全部次梯度，因此，只能用一束次梯度去逼近贯( x ) 。为避免光滑优化中最速下降法的锯齿现象，在第k 步迭代时，应找到方向d k ，使【5 2 f ( x k + d k ) 0 ，存在6 o ，当| fx x 。i l 6 且f 【x ) 在点x 处可微时，存在某个g 甜( x 。) ，使得l i v f ( x ) 一酬 s 。实际工程优化问题一般会满足条件a ，如极大极小问题，精确罚函数问题，分片光滑函数等，此时函数坟x ) 在r 中是几乎处处连续可微的。当问题不满足条件a 时，数值计算次梯度的成功率将难以得到保障，此种情形的具体解决方案将在后面讨论。在条件a 的前提下，由m ( x ) 非空便知可用不可微点附近某个可微点处的梯度来近似该点处的某个次梯度，问题的关键便成为如何判断函数在某个点处的可微性。根据微积分的基本理论呻】，当函数f 强) 在点x 处的各个一阶偏导数均连续时，f ( x ) 在点i 处可微。因此可分别用前、后差分计算函数在该点的梯度至一定精度并加以比较来判断函数在该点的可微性。若两者近似相等，则可认为函数在该点处的各个偏导数均连续，从而在该点处可微。于是计算函数在不可微点处某个次梯度的数值方法可设计如下：算法2 1 计算点y k + ，处的次梯度的数值算法1 6华中科技大学博士学位论文1 0 、用前差分计算点