（运筹学与控制论专业论文）近似束方法及其应用.pdf

大连理工大学博士学位论文 摘要 束方法目前被公认为是解决非光滑优化问题的最有效和最有前景的方法之一 1 】 他们已经被成功地应用到众多实践领域，如：经济、机械工程以及最优控制方面 对束方法的研究涉及凸分析，线性和非线性规划，非光滑分析等数学分支本论文主 要研究了近似束方法在解决非光滑优化问题中的使用以及它们在解决m p e c s 问题和 变分不等式问题中的应用 本文取得的主要结果属于理论性的，可概括如下 1 第二章中，基于某些函数值不易求得的事实，利用目标函数的近似函数值和近似次 梯度构建了一种对目标函数的分片线性近似模型，该模型位于目标函数的下方 通过与前人给出模型的比较，我们的模型更接近于真实函数，也就是对目标函数 的近似程度更好利用构建的近似模型可获得一个可能的下降方向，而寻找下降 方向的问题又可以转化成一个二次规划来研究，大大降低了问题的难度本论文 的三，四，五，六章均是在这类模型构建的基础上展开研究的 2 在第二章的基础上，提出了一种解决非光滑无约束优化问题的迫近束方法首先 应用构建的近似模型找到可能的下降方向，之后给出保证内循环有限步终止的下 降步条件和零步条件，使迭代或者产生下降步或者产生零步算法后的收敛性分 析证明了即使每次迭代使用的均是非精确函数值和次梯度值，所给算法仍会收敛 到原问题的最优解同样基于上述假设，对于非光滑凸约束优化问题又提出了一 种不可行束方法该方法将原始凸约束优化问题转化成对改进函数的无约束优化 问题的研究但是随着新的下降步迭代点的产生，改进函数需要重新定义该方 法保证即使选取的初始点和迭代过程中产生的下降步迭代点不可行，所产生序列 仍会收敛到原问题的最优篇 3 第四章中，将函数的m o r e a u - y o s i d a 正则化，束思想与拟牛顿相方法结合提出了一种 解决非光滑无约束优化问题的可执行算法该方法首先将非光滑无约束优化问题 转化成m o r e a u - y o s i d a 正则化函数的最小化问题，进而采用束方法对m o r e a u - y o s i d a 正则化函数中的非光滑函数进行下近似，最终使用拟牛顿方法产生迭代序列本 章最后证明了在一定条件下算法的收敛性 4 m p e c s 问题，即带有平衡约束的数学规划问题，在经济，机械结构设计等应用领 域起着重要作用而束方法和隐规划相结合可以处理带有复杂约束的m p e c s 问 题在第五章中，通过调用已有的两种束方法，我们给出了一种求解一类m p e c s 问题的序列束方法该方法构造了原问题的一系列近似问题，通过用束方法求解 近似问题得到一个解序列，该序列能够逼近原问题的最优解 5 变分不等式在运筹学、系统科学，工程技术、交通及管理等许多方面都有广泛应 近似束方法及其应用 用在这一章中我们将求解广义变分不等式的辅助问题原则和非光滑优化问题中 的束方法相结合，求解两个算子之和的零点要求第一个算子是单值单调算子， 第二个算子是一个下半连续正常凸函数为简化子问题求解，考虑对第二个算子 进行近似，所使用的技巧就是非光滑优化束方法中的分片线性近似最后证明了 在一定条件下所构造算法的弱收敛性 关键词：非线性规划，非光滑最优化，束方法，m o r e a u - y o s i d a 正则化，拟牛顿方法， m p e c s 问题，广义变分不等式 大连理工大学博士学位论文 a p p r o x i m a t eb u n d l em e t h o d sa n da p p l i c a t i o n s a b s t r a c t b u n d l em e t h o d sa r ea tt h em o m e n tc o n s i d e r e da so n eo ft h em o s te f f i c i e n ta n dp r o m i s - i n gm e t h o d sf o rs o l v i n gn o n s m o o t ho p t i m i z a t i o np r o b l e m s t h e yh a v ea l r e a d yb e e na p p l i e d t om a n yp r a c t i c a la r e a s ，f o re x a m p l e ，e c o n o m y , m e c h a n i c s ，e n g i n e e r i n g ，o p t i m a lc o n t r o la n ds o o n r e s e a r c h e so nb u n d l em e t h o d st o u c hu p o ns u c hm a t h e m a t i c a lb r a n c h e sa sc o n v e xa n a l y s i s n o n l i n e a rp r o g r a m m i n ga n dn o n s m o o t ha n a l y s i s t h i sd i s s e r t a t i o ni sd e v o t e dt ot h es t u d yo f a p p r o x i m a t eb u n d l em e t h o d sf o rs o l v i n gn o n s m o o t ho p t i m i z a t i o np r o b l e m sa n dt h ea p p l i c a t i o n s o fa p p r o x i m a t eb u n d l em e t h o d st om p e c sp r o b l e m sa n dg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t i e s t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o na r es u m m a r i 7 划船f o l l o w s ： 1 b a s e do nt h ef a c tt h a ts o m ef u n c t i o nv a l u e sa r en o te a s yt oc o m p u t e c h a p t e r2e s t a b l 5 h e sa p i e c e w i s el i n e a rm o d e lb yu t i l i z i n ga p p r o x i m a t eo b j e c t i v ef u n c t i o nv a l u e sa n ds u b g r a d i e n t s b yc o m p a r i n gw i t ht h eo n e sa p p e a r e di no t h e rr e f e r e n c e s o u rm o d e li sm u c hc l o s e rt o o b j e c t i v ef u n c t i o n ap o s s i b l ed e s c e n td i r e c t i o ni so b t a i n e db yu s i n gt h ep i e c e w i s el i n e a r m o d e l a n dt h ep r o b l e mo fs e a r c h i n gd e s c e n td i r e c t i o nc a nb ec o n v e r t e di n t oaq u a d r a t i c p r o g r a m m i n g ，w h i c hd e c r e a s e st h ed l f f i c u l t yo ft h ep r o b l e m c h a p t e r3 ，4 ，5 ，6a r ew r i t t e n b a s e do nt h ec o n s t r u c t i o no ft h i sm o d e l 2 c h a p t e r3p r o p o s e sap r o x i m a lb u n d l em e t h o dw i t hi n e x a c td a t af o rn o n s m o o t hc o n v e x u n c o n s t r a i n e do p t i m i z a t i o n f i r s t l y , ap o s s i b l ed e s c e n td i r e c t i o ni so b t a i n e db ym i n i m i z i n g t h ep i e c e w i s el i n e a rm o d e l ，t h e ns o m ec o n d i t i o n sf o rs e r i o u ss t e p sa n dn u l ls t e p sa r eg i v e n c o n v e r g e n c ea n a l y s i sf o l l o w e dt h ep r o p o s e da l g o r i t h ms h o w st h a te v e nw eo n l yn s et h e i n e x a c tv a l u e so f o b j e c t i v ef u n c t i o na n ds u b g r a d i e n t s ，t h ea l g o r i t h mc o n v e r g e st ot h eo p t i m a l s o l u t i o n b a s e do nt h es ；9 1 n ea s s u m p t i o nm e n t i o n e da b o v e ，a ni n f e a s i b l eb u n d l em e t h o di s a l s op r e s e n t e df o rs o l v i n gn o n s m o o t hc o n v e xc o n s t r a i n e do p t i m i z a t i o np r o b l e m t h eo r i g i n a l p r o b l e mc h a n g e si n t ot h eu n c o n s t r a i n e dm i n i m i z a t i o no ft h ei m p r o v e d u n c t i o n b u tw i t h t h eg e n e r a t i o no fn e ws e r i o u ss t e p ，t h ei m p r o v e df u n c t i o nm u s tb ed e f i n e da g a i n t h e m e t h o de n s u r e st h ec o n v e r g e n c eo ft h ea l g o r i t h me v e nt h o u 【g ht h ef i r s to r i g i n a lp o i n ta n d t h es e r i o u sp o i n t sg e n e r a t e di ni t e r a t i o np r o c e s sa r ei n f e a s i b l e 3 c h a p t e r4g i v e s a ni m p l e m e n t a b l ea l g o r i t h mf o rn o n s m o o t hu n c o n s t r a i n e do p t i m i z a t i o n b yc o m b i n i n gt h er e g u l a r i z a t i o no fm o r e a u - y o s i d a ，b u n d l ei d e aa n dq u a s i - n e w t o nm e t h o d t h i sm e t h o df o c u s e so nt h es t u d yo ft h em i n i m i z a t i o np r o b l e mo fm o r e a u - y o s i d ar e g u l a r - i z a t i o n ，t h eb u n d l ei d e ai sa d o p t e dt oa p p r o x i m a t et h en o n s m o o t hf u n c t i o n q u a s i - n e w t o n 1 1 1 近似束方法及其应用 m e t h o di se m p l o y e dt og e n e r a t ei t e r a t i o np o i n t s t h ec o n v e r g e n c ea n a l y s i so ft h ea l g o r i t h m i sa l s og i v e n 4 m p e c s ，i e ，m a t h e m a t i c a lp r o g r a mw i t he q u i l i b r i u mc o n s t r a i n t s ，p l a y sa ni m p o r t a n tr o l e i ne c o n o m y , d e s i g no fm e c h a n i c a ls t r u c t u r e sa n do t h e ra p p l i c a t i o n8 x e s 。s ac o m b i n a t i o no f i m p l i c i tp r o g r a m m i n ga p p r o a c hw i t hb u n d l em e t h o df o rn o n s m o o t ho p t i m i z a t i o ne n a b l e s u st oh a n d l em p e c sw i t hv e r yc o m p l e xe q u i l i b r i u m i nc h a p t e r5 ，b yu t i l i z i n gt w ob u n d l e m e t h o d sw ep r e s e n tas e q u e n t i a lb u n d l em e t h o df o rs o l v i n gad a s 8o fm p e c sp r o b l e m s t h i sm e t h o df i r s t l yc o n s t r u c t sas e r i e so fa p p r o x i m a t ep r o b l e m st ot h eo r i g i n a lp r o b l e m t h e nf i n d sas e r i e so fs o l u t i o n sb yb u n d l em e t h o d s ，w h i c hc o n v e r g e st ot h eo p t i m a ls o l u t i o n o ft h eo r 哂n a lp r o b l e m 5 i ti sw e l lk n o w nt h a tv a r i a t i o n a li n e q u a l i t i e sh a v em a n ya p p l i c a t i o n si no p e r a t i o nr e s e a r c h 。 s y s t e ms c i e n c e ，e n g i n e e r i n gt e c h n o l o g y , t r a n s p o r t a t i o na n dm a n a g e m e n te t a 1 i nt h i sc h a p - t e r ，w ec o m b i n ea u x i l i a r yp r o b l e mm e t h o df o rg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t yw i t hb u n d l e m e t h o df o rn o n s m o o t ho p t i m i z a t i o n ，a n df i n daz e r op o i n to ft h es u mo ft w oo p e r a t o r sd e - f i n e do nar e a lh i l b e r ts p a c e ：t h ef i r s ti sam o n o t o n es i n g l e - v a l u e do p e r a t o r ；t h es e c o n di s t h es u b d i f f e r e n t i a lo fal o w e rs e m i c o n t i n u o u sp r o p e rc o n v e xf u n c t i o n 击t om a k et h es u b - p r o b l e me a s i e rt os o l v e ，w ec o n s i d e ro n ek i n do fl o w e ra p p r o x i m a t i o nt o 毋t h et e c h n i q u e u s e di st h ep i e c e w i s el i n e a ra p p r o x i m a t i o ni nb u n d l em e t h o d sf o rn o n s m o o t ho p t i m i z a t i o n f i n a l l y , w ep r o v et h ew e a kc o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h m k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ；n o n s m o o t ho p t i m i z i n g ；b u n d l em e t h o d ； m o r e a u - y o s i d ar e g u l a r i z a t i o n ；q u a s i - n e w t o nm e t h o d ；m p e c sp r o b l e m ；g e n e r - a l i z e dv a r i a t i o n a li n e q u a l i t y 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 近似束方法及其应用 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解。大连理工大学硕士、博士学位论文版权使 用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文 作者签套：。毒鸥婆l _ 一 7 1 rr ! 指导教师签砖贿f 1 绪论 本章简要地介绍了非光滑优化问题和束方法的历史背景与研究现状，包 括非光滑无约束优化问题的束方法与非光滑凸约束优化问题的束方法，并对 相关文献做了综述，概括了本文研究的内容以及取得的主要结果 1 1 非光滑优化问题的历史背景与研究现状 不可微优化( n d o ) 一词是由b a i l i n s k i 和w o l f e1 2 】在1 9 7 5 年首次提出的，它的提 出是为了解决一类极值问题，其中目标函数和约束函数都是连续的，但他们的导数是 不连续的这一名词在今天仍然广为沿用，尽管有时用非光滑优化( n s o ) 或不连续优 化( d c o ) 更恰当不可微优化是传统优化方法的自然产物众所周知的一些重要的不 可微优化问题，如，c h e b y s h e v 近似，对策论和数学统计等等，对他们的研究可以追溯 到很久以前 人们对于不可微优化的研究兴趣源于人们意识到了不可微优化技巧巨大的实用价 值这一数学规划的新领域为应用数学方面的专家提供了解决源于生活和工作的非传 统问题的工具，同时也为处理传统问题提供了新思想和新方法不可微优化关注的是 最优决策问题，这些问题的共同点在于目标函数与约束函数不可避免的具有较差的解 析性质好的解析性质在进行深刻的理论分析和构造有效算法方面是非常关键的，面 这些解析性质中最重要的就是各阶导数的存在性和连续性导数不存在会导致理论分 析上的困难和算法实际执行上的失败缺乏连续导数将会使精确地预测控制变量的微 小改变对系统所产生的影响变得十分困难这促使人们对不可微优化和非光滑优化问 题展开深入探讨和研究 在这一部分，我们考虑如下的非光滑优化问题： ，( z ) z g 其中目标函数，：舻一r m 不必具有连续导数我们只假设，在可行集gc 舻内是 局部l i p s c h i t z 连续函数 非光滑优化问题源于众多应用领域，如，经济【3 】、力学1 4 】、工程 5 】和最优控制 【6 】等方面非光滑问题的来源可以分成四类；与生俱来的、技术类的、方法类的和数 1 近似束方法及其应用 值非光滑的在与生俱来的非光滑闻题中，所考虑的原始现象包含各种各样的不连续 性和不规则性，这其中最典型的例子就是在钢的连续铸造中材料的阶段性改变问题 7 l 和经济学中的分片线性税收模型 8 】而技术类的非光滑问题通常是由某些额外的技术 上的约束造成的，尽管原始函数自身是连续可微的，但这些约束仍可以造成变量和函 数之间的非光滑依赖这方面具体例子有最优模型设计中所谓的障碍问题f 9 1 和生产 计划中的离散可行集另外，约束优化问题的一些求解方法也可以产生非光滑问题 方法类的非光滑问题的具体例子有精确罚函数方法和l a g r a n g e 分解方法产生非光滑 问题最后一种原因是，问题本身可能是解析光滑的，但获取的数值是不光滑的相应 的例子如，噪声输入数据和”s i t f f 问题”，它们是数值不稳定的，处理起来类似非光滑 问题 非光滑为我们解决问题带来许多困难，每前进一步都要做许多额外的工作我们 面临的第一个困难就是任一个次梯度方向的负方向不一定是下降方向，这使我们不得 不改变传统意义上的线搜索运算此外，终止准则是什么我们也不清楚 对于上述非光滑问题有许多方法去解决它们其中之一就是基于梯度的光滑化方 法它是一种简单易行的方法，但是却有可能导致在收敛性，最优检验及梯度近似方 面的失败【1 0 另一方面，一些直接方法，如，h o o k e 和j e e v e s 的方法及不使用导数信 息的多面体搜索等方法，它们会随着问题规模的增大而失效此外，各种各样的正则 化技术 9 】 1 1 】在解决非光滑问题方面给出了一些较满意的结果但一般来说，并不像 直接方法那样有效【1 2 】 总的来说，非光滑优化问题的解决方法可以分成以下几类：首先是以l e m a r c h a l 为代表的次梯度方法次梯度方法( 又称k i e v 方法) 源于上个世纪6 0 年代，主要在前 苏联得到较大发展次梯度方法的基本思想是用一个任意的次梯度代替梯度将光滑化 方法推广到非光滑情况由于其结构简单，尽管有许多严重缺陷，仍被广泛地应用于 解决非光滑优化闻题第一，该方法可能不产生下降方向，因而没有标准的线搜索准 则可以使用正因如此，步长不得不提前取定第二，没有可执行的终止准则和不理 想的收敛速度( 收敛速度比线性还慢) 为克服第二个缺陷，换言之，为取得线性收敛 速度，人们使用两个空间加速方法将变尺度思想引入到次梯度方法中为获取对次梯 度方法的进一步了解，见 13 解决非光滑问题的第二类方法是光滑化方法光滑化方 法是用一个光滑函数代替非光滑问题光滑后的函数含有参数，随着参数的变化，光 滑函数会逐渐逼近非光滑问题以m o r e a u - y o s i d a 正则化为例， f ( z ，a ) = 呼 坤) + z - x l l 2 叫做函数，的m o r e a u - y o s i d a 正则化当a 一+ 时，f ( z ，a ) 会趋向于原非光滑问题 第三类方法是u v 一分解方法u v 分解方法是由l e m a r c h a l ，o u s t r y 和s g a g s t i z h b a l 在2 0 0 0 年首次提出的，它的基本思想是将整个r n 空间分解成两个正交的子空间【，和 y 的直和，使函数在矿空间上的一阶逼近是线性的，而函数的不光滑性集中体现在y 空间上再借助一个中间函数，即，u l a g r a n g e 函数，以获得函数在切于u 空间的 某个光滑轨道上的二阶展示该方法只能处理某一类凸函数的优化问题，应用起来有 一定的局限性最后一类方法就是束方法开创性的束方法，即一最速下降法是由 2 大连理工大学博士学位论文 l e m a r 6 c h a lf 1 4 在1 9 7 6 年提出的，这种方法是在l e m 戚c h a l 1 5 和w o l f e 1 6 】1 9 7 5 年分 别提出的共轭次梯度方法的基础上提出来的众所周知并且有广泛应用的f o r t r a n 编 码m 1 f c l 和m 2 f c l 使用的就是这种s 最速下降法的思想 1 9 8 5 年，k i w i e l 【1 7 对束方法提出了一种新策略这种新策略基于k e u e y 【1 8 ( 1 9 6 0 ) 和c h e n e y ，g o l d 8 t e i n 【1 9 ( 1 9 5 9 ) 提出的经典切平面方法这种广义切平面方法的基本 思想是使用由次梯度产生的线性化函数形成的对目标函数的一个凸分片线性近似模 型k i 丽e l 同时给出了限制束存储次梯度数量的两个策略：次梯度选择和集技术不 考虑l e m 疵c h a l 和k i w i e l 提出的这两种方法的不同之处，二者每次迭代都是通过解二 次规划得到搜索方向的 l a a r 6 c h a l 方法的主要困难在于要提前选择一个近似参数，它控制一个球的半径， 在这个球内束模型被看作是对目标函数的一个好的近似反过来，k i w i e l 方法的最大 缺陷在于它对目标函数的规模( s c a l i n g ) 的敏感性，同时，不确定的线搜索有时可能要 求计算相对于迭代次数来说较多的函数值为克服上述困难，人们将束方法与f l e t c h e r 2 0 1 ( 1 9 8 7 ) 的经典信赖域方法相结合，又提出了柬信赖域方法，见s c h r e a m mf 2 1 】( 1 9 8 9 ) ， z o w e 【2 2 ( 1 9 8 8 ) ，s c h r a m m h e 和z o w e 2 3 ( 1 9 9 2 ) ，以及迫近柬方法，见k i w i d1 2 4 ( 1 9 9 0 ) 接下来，k i w i e l ( 2 5 1 在1 9 9 1 年又提出了倾斜迫近柬方法，该方法使用倾斜的线性化函 数，目的是切去目标函数上图中某些没用的部分，并且这种方法还试图使用了目标函 数的二阶信息 下面我们分别就非光滑无约束优化束方法与非光滑凸约束优化柬方法详细介绍一 下束方法的历史与发展现状 1 2 解决非光滑优化问题的束方法的研究现状 1 2 1 解决非光滑无约束优化问题的束方法的研究现状 在这一部分我们考虑如下问题； rm i 血i ， ) 1 8 t z r n ， 其中目标函数，：r ”一r 是凸的，换言之，v z ，y 舻，叭( 0 ，1 ) ，我们有 ，( h + ( 1 一a ) f ) a ，( z ) + ( 1 一 ) ，扫) ( c p ) ( 1 1 ) 假设对每一个z r n ，我们能计算出函数值f ( x ) 和一个任意的不指定的次梯度f ( z ) ，也 就是f ( 。) a ，( $ ) ， o ( x ) = ( z ) r “j ，( 口) ，( z ) + f ( z ) t ( 一。) ，v y r “) 是函数，在z 点的次微分 对于凸函数。我们有下面充分必要的最优性条件 定理1 2 ，1 一个凸函数，：舻一矗在矿达到全局最小当且仅当 0 0 i ( x 1 3 近似柬方法及其应用 证明；见【2 6 】 口 我们首先来看普通束方法普通束方法就是要产生一个序列 x 。 o 。o ：l ，如果，有全 局最小点，则该序列 z 耀l 收敛到，的一个全局最小点除了当前迭代点x k 之外， 我们假设还有一些源于以前迭代的试探点鲫r n 和相应的次梯度白o f ( y j ) ，j j 2 ， 这里是 1 ，2 ，磷的一个非空子集束方法的思想实际上是用一个分片线性函数 从下面对，进行近似，换言之，我们用所谓的切平面模型矗( $ ) 来代替f ，矗( $ ) 定义如 下： 厶 ) = 蚴 ，( 珊) + g 一蜥) ) ( 1 2 ) 上式可以等价地写成 五( $ ) = m j 。j x j , ，( 吼) + 学( x - - x k ) 一面) ， 其中线性化误差口定义为 哆= ( x k ) 一，( 纷) 一醪( x k 一如) ，j 。 注意到 九( 霉) ，( 。) ，v 。r ”；q ；0 ，v j j “ 下一个迭代点的候选点取成 y k + 1 2 茹k + d k ， 其中搜索方向也由下式计算得到， d k = a r g m i n d 舻 矗p k + d ) + 护尥d ， ( 1 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) ( 1 7 ) 稳定项( 1 2 ) d t m k d 用来保证( 1 7 ) 的解存在性，同时也使五( z ) 对，的近似在局部是足 够好的对称规范矩阵慨用来聚集在以为中心的球内，的曲度信息 如果纨+ 1 比巩足够好，换言之， f ( v k + 1 ) f ( x k ) + m l v k ， 其中m l ( 0 ，1 2 ) 是线搜索参数， ”k = 氕( + 1 ) 一( x k ) 是，在点的预期下降，则取下降步 x k + l2 y k + l ； 否则取零步 ( 1 8 ) ( 1 9 ) ( 1 1 0 ) x k + l = ( 1 | 1 1 ) 不管取下降步还是取零步，我们都设置以+ l = 以u k - k 1 ) ，目的是改善九+ 1 ( 。) 对，的 近似如果 一e s ， ( 1 1 2 ) 4 大连理工大学博士学位论文 则迭代停止，其中岛 0 是由使用者预先提供的一个最终精度允许 注意到( 1 7 ) 仍然是一个非光滑优化问题，然而由于它是分片线性的，它可以写成 一个光滑的二次规划问题 竺吡8 ：嚣三咄 ， 通过使用对偶定理，我们得到( q p ) 的等价问题，即，解下列( d p ) 问题，寻找乘子 峙，以， 血蛐e 踩 白】丁嵋1 e j e 以纠+ e j e 以b 。 ( d p ) 【s u b j e c t t oe j 如= 1 ，b 0 出于计算的考虑，有时求解( q p ) 要比求解( d p ) 有效得多下面的定理建立了( q p ) 和 ( d p ) 之间的关系 定理1 2 2 ( q p ) 和( d p ) 是等价的，并且他们分别有唯一解( 以，v k ) 和a ；，j 以，使得 证明：见【12 】 d k = 一芍嵋1 白， ( 1 1 3 ) 拒“ = 一d 暑嗨如一峙哆 ( 1 “) j 口 从计算角度来看，指标集以的选择很关键最简单的取法就是让以存储所有以 前迭代点的次梯度信息，换言之，取以= 1 ，2 ，女) 然而在经过多次迭代之后，这 种取法会给存储和计算带来很大困难k i w i e lf 17 】在1 9 8 5 年提出的次梯度选择技术和 集技术解决了这个难题下面我们介绍几种基本类型的束方法，它们都是在普通束方 法的基础上作了一些微小的改动得到的 对角变尺度束方法可以说是束方法发展史上的一个进步为了聚集，在z t 附近 的曲度的某些二阶信息，在( q p ) 或( d p ) 目标函数的二次项里加入一个权参数，因而 变尺度柬方法中变尺度矩阵m k 取成 m i p t j ( 1 1 5 ) 其中凤 0 是权数基于迫近点方法 2 7 】， 2 8 j ，k i w i e l 【2 4 】在1 9 9 0 年首先提出了迫近束 方法，同时引入了一种校正p k 的改造防护二次插值技术s c h r a m m 和z o w e 【2 3 】在1 9 9 2 年将束方法与信赖域方法相结合得到了一种束信赖域方法进一步还有”p o o rn m s ” 拟牛顿方法，建立在m o r e a u - y o s i d a 正则化基础上的迫近束算法这些方法都是围绕着 如何校正权数肌展开研究的2 0 0 0 年k i w i e l1 2 9 证明了这些方法最多经过o ( 1 e 3 ) 个 目标函数值和次梯度的计算就可以得到一个e 一最优解 水平束方法是束方法的一种新交形它的产生是由于人们注意到切平面模型( 1 2 ) 的水平集的变化相当有规律因而l e m a r , 白h a l 3 0 i 在1 9 9 5 年首先提出了水平柬方法， 5 近似束方法及其应用 该方法实际上是求将切平面模型的水平集作为约束的一个稳定的二次项的最小寻找 搜索方向出的问题( 1 7 ) 转变成 咄= a r g n ：1 i n d 舻 ；d t 地d i k + d ) 舻) ， ( 1 1 6 ) 其中目标水平偿”( 0 ，我们可以计算出，的一个近 似函数值矗( z ) 满足 ，( ) 一丘 ) ， ) ，( 1 ，1 7 ) 以及一个乒次梯度靠馥，( z ) ，其中 良，( z ) = r “i ( v ) 2 ( x ) - i - f r ( f 一。) 一，v y r “) ( 1 1 8 ) 是，在点z 的乒次微分于是切平面模型( 1 2 ) 被追近切平面模型替代 元p ) 2 翼簿 丘( 蜥) + 锈p 一的) ) ， ( 1 1 9 ) - x - 牛 v j ，岛以，f ( y a ，并且勺一00 一+ ) 在1 9 8 5 年k i w i e l 【3 4 】将广义切平面 方法推广到了使用非精确数据的情况接下来，k i w i e l 3 5 ，【3 6 】又在1 9 9 1 年和1 9 9 5 年 将迫近束方法推广到了使用非精确数据的情况 1 2 2 非光滑凸约束优化问题的束方法的研究现状 在这一部分，我们考虑如下约束优化问题： fs：tg “i ( x ：0 ，i 12 m p ， 【 ) ， = ，m ， 其中，：r n r 和g i ：舻一r ，i = 1 ，2 ，是凸函数 定义1 2 1 我们称问题( c c p ) 满足s l a t e r 约束规范，如果存在一个y 舻，使得 g ( y ) 0 ，( 1 2 0 ) 其中g ：舻一r 是定义如下的总约束函数 9 ( 。) 2 忙黔。g i ( x ) 对于问题( c c p ) ，我们有如下充分必要的k a r u s h - k u h n - t u c k e r 最优性条件 6 ( 1 2 1 ) 大连理工大学博士学位论文 定理1 2 ，3 如果问题( c c p ) 是凸的，并且满足s l a t e r 约束规范，那么，在r 处达到全 局最优当且仅当存在l a g r a n g e 乘子0 p r ”，使得m g i ( x ) = 0 ，i = 1 ，2 ，m ，并且 证明；见 3 7 】 m 0 a ( x ) + p t 鲰( 矿) ( 1 2 2 ) i = 1 口 形如( c c p ) 的凸约束优化问题的解决方法大致分成两类，一是约束线性化方法， 二是精确罚函数方法先来看第一种方法，约束线性化方法是处理( c c p ) 中约束比较 流行的方法，即求一个无约束改进函数的最小值，改进函数定义如下 h ( z ，y ) = m a x ，( 善) 一，( f ) ，9 p ) ) ( 1 2 3 ) 使目标函数和约束函数均线性化的改进函数的切平面模型定义成 矗i ( 。) = ：m a x ，( z ) 一，( z k ) ，口i ( z ) ) ( 1 2 4 ) 其中彘p ) = m a x j 以d ( 如) + 9 7 p 一约) ) ，g o g ( u j ) 寻找搜索方向的问题( 1 7 ) 变成 如= a r g n l i n d 舻 鼠( 吼+ d ) + d r m k d ( 1 2 5 ) 在许多类型的束方法中人们借鉴了这种思想，如，【1 2 】就是将该方法应用于迫近束方 法下面再来看精确罚函数方法为求解问题( c c p ) ，p s h e n i c h n y i 和d a n i l i 【鲳】使用了 形如 l e p ；c ) = ， ) + c f m a x g i ( x ) ，o ) ( 1 2 6 ) i = 1 的精确罚函数相应的切平面模型定义为。 其中 劈( z ) 2 衢蚴) + ( ) t ( z 一劬) ) ， a 吼( 砌) 搜索方向由下式计算获得 ，d k = a r 眦舻t 缸p k + d ) + ；d r 帆d ) ( 1 2 7 ) ( 1 2 8 ) ( 1 2 9 ) 上述精确罚函数方法同样也被应用于各种类型的柬方法中，如广义切平面方法【3 9 】 【如】，迫近束方法【4 1 】 7 吣叻比陋 瓤m 砖 m 汹 + 磊 f 1 缸 近似束方法及其应用 1 3 本文主要研究结果 1 第二章中，基于某些函数值不易求得的事实，利用目标函数的近似函数值和近似次 梯度构建了一种对目标函数的分片线性近似模型，该模型位于目标函数的下方 通过与前人给出模型的比较，我们的模型更接近于真实函数，也就是对目标函数 的近似程度更好利用构建的近似模型可获得一个可能的下降方向，而寻找下降 方向的问题又可以转化成一个二次规划来研究，大大降低了问题的难度本论文 的三，四，五，六章均是在这类模型构建的基础上展开研究的 2 在第二章的基础上，提出了一种解决非光滑无约束优化问题的迫近束方法首先 应用构建的近似模型找到可能的下降方向，之后给出保证内循环有限步终止的下 降步条件和零步条件，使迭代或者产生下降步或者产生零步算法后的收敛性分 析证明了即使每次迭代使用的均是非精确函数值和次梯度值，所给算法仍会收敛 到原问题的最优解同样基于上述假设，对于非光滑凸约束优化问题又提出了一 种不可行束方法该方法将原始凸约束优化问题转化成对改进函数的无约束优化 问题的研究但是随着新的下降步迭代点的产生，改进函数需要重新定义该方 法保证即使选取的初始点和迭代过程中产生的下降步迭代点不可行，所产生序列 仍会收敛到原问题的最优解 3 第四章中，将函数的m o r e a u - y o s i d a 正则化，束思想与拟牛顿方法相结合提出了一种 解决非光滑无约束优化问题的可执行算法该方法首先将非光滑无约束优化问题 转化成m o r e a u - y o s i d a 正则化函数的最小化问题