（运筹学与控制论专业论文）求解非线性约束优化问题的精确罚函数方法.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 本文针对非线性约束优化问题的精确罚函数方法展开研究首先对罚函数方 法的发展作了简要的介绍，特别地，对几种典型的精确罚函数进行了阐述然后在 已有的非线性优化问题的精确罚函数基础上，我们提出一种新的精确罚函数，并 且对其精确性给出了理论证明经过分析发现该罚函数具有分段可微的性质若 当前迭代点位于可行域的外部或内部，罚函数是可微的，这时可以用传统的无 约束优化方法进行求解；当迭代点在可行域边界时，该罚函数不可微，此时我 们不能直接应用涉及到梯度的下降方法求解 利用该罚函数分段可微的特点，结合t e c o l e m a n ，a r c o n n ( 1 9 8 2 ) 的思 想，我们设计了如下数值算法：取定8 一积极区域，若当前迭代点在s 一积极区 域的外部，则直接利用拟牛顿步进行数值迭代( 其中海色阵墩用b f g s 公式进行 修正) ；若当前迭代点落在8 一积极区域内部，则可用l l 精确罚函数来替代原 罚函数，将l 精确罚函数分成两部分：可微部分和巧可微部分，然后通过使得可 微部分的函数值下降，而尽量保持不可微部分的函数值不变，从而得到一个下降 方向，对新得到的迭代点“重复上述过程，直到满足终止条件为止 最后，我们对本文提出的数值算法进行理论分析，证明了该算法具有全局收 敛性数值实验的结果表明该算法能够满足非线性优化问题求解的需要，且具有 良好的数值稳定性和收敛性 关键词：非线性优化；精确罚函数；全局收敛性；分段可微 分类号：0 2 2 1 2 北京交通大学硕士学位论文 a b s t r a c t i nt h i sp a p e r w es t u d yt h ep e n a l t yf u n c t i o nm e t h o df o rs o l v i n gn o n l i n e a rc o n s t r a i n e dp r o g r a m m i n gp r o b l e m s f i r s to fa l l ，w ei n t r o d u c et h ed e v e l o p m e n to fp e n a l t y f u n c t i o nm e t h o d sb r i e f l y , e s p e c i a l l ys o m et y p i c a le x a c to n e s t h e nw i t ht h ek n o w l - e d g eo fp e n a l t yf u n c t i o n sw h i c hh a v eb e e ns t u d i e d ，w ep r o p o s ean e wp e n a l t yf u n c t i o n ， w h i c hi sa l le x a c to n e t h r o u g ha n a l y s i sw ef i n dt h a tt h i se x a c tp e n a l t yf u n c t i o ni sa p i e c e w i s ed i f f e r e n t i a b l eo n e w h e nt h ec u r r e n ti t e r a t i v ep o i n t 叠l i e si nt h ee x t e r n a lo r i n t e r n a lp a r to ft h ef e a s i b l er e g i o n ，t h ee x a c tp e n a l t yf u n c t i o ni sd i f f e r e n t i a b l e t h e r e f o r ew ec a nu s et h et r a d i t i o n a ln o n l i n e a rp r o g r a m m i n gm e t h o d st om i n i m i z et h ep e n a l t y f u n c t i o ni nt h a ta r e a b u ti ft h ep o i n to fi t e r a t i o nl i e sn e a rt h eb o u n d a r yo ft h ef e a s i b l e r e g i o n ，t h i sp e n a l t yf u n c t i o ni sn o n d i f f e r e n t i a b l e ，s ow ec o u l dn o tu s et h et r a d i t i o n a l n o n l i n e a rp r o g r a m m i n gm e t h o d sd i r e c t l y u s i n gt h ep r o p e r t i e so fp i e c e w i s ed i f f e r e n t i a b l ef u n c t i o n ，t o g e t h e rw i t ht h ei d e a i nt e c o l e m a na n da r c o n n ( 19 8 2 ) ，w ed e s i g nt h ef o l l o w i n gn u m e r i c a la l g o r i t h m ： l e tsb eas m a l lp o s i t i v en u m b e ru s e dt oi d e n t i f yt h e8 一a c t i v er e g i o n i ft h ec u r - r e n ti t e r a t i v ep o i n txl i e so u t s i d et h e8 一a c t i v er e g i o n ，w ec a nu s eq u a s i n e w t o n m e t h o dd i r e c t l y ( w h e r et h ea p p r o x i m a t eh e s s i a nb ki su p d a t e d u s i n gb f g se q u a t i o n ) w h e nx kl i e si nt h es a c t i v er e g i o n ，w eu s et h el 1e x a c tp e n a l t yf u n c t i o ni n s t e a d t h e nw ec a ns e p a r a t et h el te x a c tp e n a l t yf u n c t i o ni n t ot w op a r t s ：t h ed i f f e r e n t i a b l e p a r ta n dt h en o n - d i f f e r e n t i a b l ep a r t au s e a b l ed e s c e n td i r e c t i o ni st h e nd e r i v e db ya t - t e m p t i n gt od e c r e a s et h ed i f f e r e n t i a b l ep a r tw h i l et r y i n gt om a i n t a i nt h ev a l u eo ft h e n o n d i f f e r e n t i a b l ep a r t t h ep r o c e s si sr e p e a t e du n t i lt h et e r m i n a lc o n d i t i o ns a t i s f i e d i ti ss h o w nt h a tt h i sa p p r o a c hh a sg l o b a lc o n v e r g e n c ep r o p e r t i e su n d e rc e r t a i nc o n - d i t i o n s n u m e r i c a lr e s u l t so ft h ea p p r o a c hs h o wt h a ti ti ss u i t a b l ef o rn o n l i n e a rc o n s t r a i n e dp r o b l e m sa n dh a sg o o dn u m e r i c a ls t a b i l i t y k e y w o r d s ：n o n l i n e a ro p t i m i z a t i o n ；e x a c tp e n a l t yf u n c t i o n ；g l o b a lc o n v e r g e n c e ； p i e c e w i s ed i f f e r e n t i a b l e c l a s s n o ：0 2 21 2 i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名： 王娩签字日期：泐歹年7 月墨日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：王桃 签字日期：为哆年7 月多r 导师签名： 孵 签字日期：妒。7 年1 月譬日 致谢 本论文的工作是在我的导师王周宏副教授的悉心指导下完成的王周宏副教 授严谨的治学态度和科学的工作方法对我有极大的帮助和影响，是我学习的榜 样借此论文完成之际，谨向我的导师表示最衷心的感谢，感谢王老师两年来对 我无微不至的关怀以及在学习和生活上给我的悉心指导，无论是在理论学习阶 段，还是在论文的选题、资料查询、课题研究、论文写作等阶段，王老师都悉心 指导，严格要求，在此衷心感谢两年来王老师对我的关心和帮助 在撰写论文期间，宫静、耿忠娟、张敏、侯瑞娜等同学对我论文中的研究工 作给予了热情的帮助另外，陈冲同学在本文进行数值实验的过程中给我诸多的 建议与帮助，使我深受启发，在此向他们表达我的感激之情另外，要特别感谢我 的父母以及众亲友，他们的理解和支持使我能够在学校专心完成我的学业 最后，感谢各位专家学者在百忙中审阅我的论文，并给出批评意见回首两年 的研究生生活，自己的每一个进步都离不开老师和同学的支持与帮助，在此表达 我对他们最衷心的感谢! 北京交通大学硕士学位论文 1 1背景介绍 第1 章引言 第1 章引言 最优化理论与方法是一门应用性很强的学科，它研究人们在工程技术、科学 研究、经济管理、交通运输和国防等诸多领域中经常遇到的问题随着科学技术 的发展，特别是电子计算机技术的飞速发展，这门学科在各领域都得到了广泛的 应用，最优化理论与方法已经成为许多工程技术人员、管理工作者和研究人员的 必备工具 非线性优化问题从上个世纪七十年代起就是最优化问题中最受重视的分支 之一，它是在有限维空间上求单值函数的极值问题，函数的自变量可能受限制于 有限个等式或不等式约束近些年来。关于非线性优化问题的理论和算法不断出 现，几乎其每一个研究分支都有相应的专著 对于一般的非线性优化问题，一个直接的想法是借助于微分学、变分法 和l a g r a n g e 乘子法等数学工具，通过逻辑推导和分析计算得到问题的解或解的 表达式，就是所谓的解析方法这种方法仅对一些具有特殊结构的非线性优化问 题有效求解非线性优化问题的第二类方法是图解法和实验法这类方法虽然操 作简单，但仅能处理低维的情况鉴于上述两类方法的局限性，对于一些实际问 题，人们尝试利用目标函数和约束函数在某局部区域上的函数值信息或导数信 息，构建迭代型数值解法，即从当前的一个近似解点，逐步调优来产生新的更好的 近似解点，直到不能再次改进为止 对于工程技术中的非线性优化问题，它们的求解方法以迭代形式的数值解法 最为典型和常见这种类型的算法大多与计算机结合，它们不仅能够计算比较复 杂的非线性优化问题，而且求解速度快，效率高 对于无约束优化问题，已经提出了很多有效的数值计算方法，如最速下降法、 共轭梯度法、牛顿法和拟牛顿法等：对于约束优化问题，也有不少计算方法，如罚 函数法、s q p 方法、可行方向法和信赖域法等 早期的求解非线性规划问题的方法是罚函数法，其基本思想是将约束问题非 约束化，将对约束条件的违反作为一个惩罚项而加入到目标函数中，从而将原问 题转化为一个无约束优化问题在求解新的优化问题过程中，随惩罚因子的不断 调整，最优解也在不断变化，最后趋于原问题的最优解，因此该方法又称为序列无 约束极小方法罚函数分为外点罚函数、内点罚函数以及混合罚函数如果罚函 数的极小解与原问题的极小解吻合，我们称该罚函数为精确罚函数罚函数法简 北京交通大学硕士学位论文 第1 章引言 单实用，它直接利用无约束优化的算法来求解约束优化问题但是罚函数法一般 要求惩罚因子趋于无穷或者需要求解非光滑优化，所以调用一般的无约束优化算 法时常有一定的困难，而精确罚函数则不需要惩罚因子趋于无穷大，即可使求解 罚函数极小和求解原问题等价由于k a r m a r k a r ( 1 9 8 4 ) 提出的一个求解线性规划 的内点法实质上等价于一个罚函数法，人们又开始重新审视罚函数法，所以对罚 函数方法的研究对于求解约束优化问题有着重要的作用 1 2 预备知识 非线性优化问题的模型一般可以表示为如下形式 m i n1 s t f ( 曲- - 0 ，i = 1 ，2 ，m 。， e l ( x ) 0 ，1 = m 。+ 1 ，m ， ( 1 1 a ) ( 1 1 b ) ( 1 1 c ) 其中，x 掣为决策变量，目标函数，( 曲和约束函数办( 力，i = 1 ，2 ，m 均为定 义在n 维空间上的实函数，m 。和m 为非负整数，且满足m m 。，( 1 1 b ) 和( 1 1 c ) 称 为约束条件，满足约束条件的点称为可行点，所有可行点的集合称为可行域，记 为q 显然， q = xi 咖( 曲= 0 ，i = 1 ，2 ，m 。；办( 曲0 ，i = m 。+ 1 ，m j 利用这一定义，我，f f n - - f 以把问题( 1 1 a ) ( 1 1 c ) 写成如下简洁的形式： m 触i n ，( 曲 当m = 0 时，问题( 1 1 a ) ( 1 1 c ) 是无约束优化问题，否则，是约束优化问题在约 束优化中，如果只有等式约束，即m = m 。 0 ，则称为等式约束优化问题另一种特 殊情形是所有的约束函数都是线性函数，这时问题( 1 1 a ) ( 1 1 c ) 是一个线性约束 优化问题 最早的罚函数是由c o u r a n t ( 1 9 4 3 ) 提出的，它只是针对等式约束优化问 题( 1 1 a ) 和( 1 1 b ) 提出的，其形式如下 旦_ p ( x ，矿) = ，( 神+ 矿 ：i ( x ) 2 ， ( 1 2 ) 百 其中矿是一个惩罚因子它可以推广到一般的约束优化问题，即 p 力= 删+ 矿 m e 触) 2 + m ( m ) 诃 ( 1 3 ) f - 1i = m ，+ l 2 北京交通大学硕士学位论文 第1 章引言 其中 妒i ( 曲一= m i n o ，多i ( 曲l ，f = m 。+ l ，m ( 1 4 ) 定义 c b ( x ) = ( ( 而( 曲，而( 力，而( 石) ) 。 ( 1 5 ) 其中 弧加雠一三：j 黑， m 6 ， 那么( 1 3 ) 式可写成 p ( x ，= ，( 曲+ o l l 西( x ) 1 1 2 ( 1 7 ) 显然，j 是问题( 1 1 a ) ( 1 1 c ) 的可行点当且仅当 所以西( 工) 称为约束违反度 记工( 矿) 为问题 r n i np ( x ，c r ) = ，( 的- i - 矿i l ( 曲崦 ( 1 9 ) 的解下面给出利用c o u r a n t 罚函数的罚函数算法 算法1 2 1 步l ：给出x l ，矿l 0 ，k ：= 1 ，s 0 ， 步2 ：利用初值敏求解m i nf ( x ) + 叽l l 西( 曲旧得到解缸吼) ， 步3 ：如果| l 西( x ( 叽) ) 1 1 2 s ，则停； 否则，x k + l - x ( 吼) ，o k + l = 1 0 0 - k ，k ：= k + 1 ，转步2 如果上述算法的误差界8 满足 8 m i ni i c d ( x ) 1 1 2 ， x e r ” 则算法必有限终止 c o u r a n t 罚函数的缺点是需要惩罚因子趋于无穷大，才可使求解罚函数极小和 求解原问题等价，而乘子罚函数( s l 称增广l a g r a n g e 罚函数) 利用近似l a g r a n g e 乘 子，从而不需要惩罚因子趋于无穷大增广l a g r a n g e 罚函数的思想是构造增广极 值问题的外点罚函数作为原问题的无约束优化子问题 对于问题( 1 1 a ) 一( 1 1 c ) ，r o c k a f e l l a r ( 1 9 7 3 ) 提出如下罚函数 贴，a ，o - ) = 厂( 曲一( 垆告毋纵工) 2 】 一，耋。 三；兰：_ ；矿f f ( 工) 2 姜暑 0 ，k ：= 1 ， 步2 ：求解问题( 1 1 2 ) ，得到解敢，x k + l ：= 氟，如果i i 多( x k + 1 ) | l ，则停， 步3 ：如果i i ( x k + 1 ) 1 1 2 1 1 ( x d i h ，转步4 ；否则，o k + 1 = 1 0 0 - k ，转步2 ， 步4 ：用( 1 1 3 ) 一( 1 1 4 ) ，计算以+ l ，o r k + l = l o o k ，k ：= k + l ，转步2 如果问题( 1 1 a ) ( 1 1 c ) 有可行点，则对任意8 0 ，算法1 2 2 必有限终止增 广l a g r a n g e 函数( 1 1 0 ) 有一个缺点：它仅是一次连续可微函数，所以在求解问 题( 1 1 2 ) 时，在数值上可能存在一定的困难 f l e t c h e r ( 1 9 7 3 ) 针对等式约束问题提出了第一个光滑精确罚函数为 p ( 0 9 = 八曲一a ( 力7 ( 力+ 去( 力r d ( 神， ( 1 1 5 ) 其中( 工) = ( l ( 曲，( 功) 7 ，a ( 曲= ( v ( 力) r ，g ( x ) = v f ( x ) ，a ( 曲= ( a ( 工) ) + g ( 曲， d = d i a g ( o l ，口k ) 在一e 式中，令所有的o i 都相等，则得到简单形式的f l e t c h e r 光滑精确罚函数 p ( x ，o - ) = ，( 曲一l ( x ) 丁( 力+ i 1 圹i i l j 【川2 2 ( 1 1 6 ) 针对问题( 1 1 a ) ( 1 1 c ) ，最常见的精确罚函数是l l 精确罚函数 p o - ) = ，( 力+ 矿【愀) l + 纵工) 一i 】， ( 1 1 7 ) 4 北京交通大学硕士学位论文第1 章 但由于该罚函数不可微，而且在一般情况下，它在解r 处是不可微的，从而不能直 接利用一些收敛较快的利用导数的方法因此，对于厶精确罚函数，关于其“近似 微分”的处理方法在很多文献中被提出【1 9 ，2 0 ，2 1 在文献 1 4 】中，f l e t c h e r 针对不等式约束问题( 1 1 a ) 和( 1 1 c ) 提出通过求解原 问题的一个二次规划子问题，得到子问题的l a g r a n g e 乘子，在其局部最优解的附 近构造一个精确罚函数，该罚函数的优点是光滑的，这使得求其无约束优化问题 具有很快的收敛速度，但是其缺点是a ( 曲的表达式中出现了目标函数和约束函数 的梯度，以至于使罚函数值的计算都不是很轻松，如果用梯度型算法求罚函数的 极小点，则需要计算目标函数和约束函数的海色阵，计算量就会变得更大 针对不等式约束问题( 1 1 a ) 和( 1 1 c ) ，文献【9 】9 提出了一种具有全局收敛性的 算法：在当前迭代点处，将罚函数分成两部分，即可微的一部分( 包括目标函 数和非积极约束) 和不可微的一部分 积极约束) 通过使可微部分的函数值下 降，而保持不可微部分的函数值不变，得到一个下降方向虽然该方法具有全局收 敛性，但是由于文献【9 】仅仅利用了罚函数和约束函数的一阶信息，因此该算法仅 具有线性收敛速度用同样的思想，文献 3 】给出了一种具有2 步超线性收敛速度 和全局收敛性的算法 z h i q i n gm e n g ，c h u a n g y i nd a n g 和x i a o q iy a n g 【2 2 】中针对不等式约束优化问 题 m i n s t 妒f ( 力0 ，f = 1 ，2 ，m 的不可微精确罚函数问题 m i n ，( x ，p ) = 厂( x ) + p 俪丽而而， f = l 提出了两种不同的光滑罚函数来逼近，其中一个为一阶连续可微函数 ，( 石，p ，g ) = 八曲+ p 仇( 班( x ) ) ， 扛l 其中 则可通过求解问题 得到问题( 1 1 9 ) 的近似解 p s ( f ) = 0 ， 1f ； 五“ f 一挣i ， t 0 。 0st 8 t s ， m 。i n 。f ( x ，p ，功 j r ” 。 5 ( 1 2 1 ) 砷 l l 2 o o 0 北京交通大学硕士学位论文 其中 第1 章引言 另外一个为二阶连续可微函数 g ( 五p ，g ) = 八曲+ p 如( 卉( 曲) ， ( 1 2 2 ) f ：l ( f ) = t p 6 ( q b i ( x ) ) ， ( 1 2 5 ) 百 来近似( 1 2 4 ) ，其中 p 8 c 。= 翥二一；，：至三： 文章给出并证明了光滑近似罚函数( 1 2 5 ) 的极小值与( 1 2 4 ) 的极小值和原问题的 最优值之间的误差估计，而且利用近似的光滑罚函数提出了一种具有全局收敛性 的算法 本文将在上述的文献资料研究结果的基础上，进一步针对非线性约束优化问 题进行探究，并对已有的方法进行适当的改进，以期能够在目前对于这个问题已 经存在的算法上提出改进，使得算法的效率得剑进一步的提高 本文针对非线性优化问题的罚函数方法的论述将按照如下结构展开：论文的 第二章将从非线性优化问题的l 1 精确罚函数的最优性条件和已有的罚函数方 6 l | s 8 5 一 i 厂 ，一扣 q 一陛“ ，i_-_l 北京交通大学硕士学位论文第1 章引言 法展开详细的论述，并在此基础上形成新的求解约束优化问题的精确罚函数方 法；第三章在提出一定的假设条件的基础上，对第二章中所提出的算法的收敛性 质展开分析，通过理论分析证明所提的算法具有全局收敛性；第四章列出了针对 所提算法进行的大量的数值实验结果，通过数值结果表明算法的有效性，并且对 结果进行分析说明，从而对所提方法的数值表现建立一个客观的评价；第五章就 算法的结构以及具体实现方面可进一步完善之处作了简要的说明 7 北京交通大学硕士学位论文第2 章求解非线性约束优化问题的精确罚函数方法 第2 章求解非线性约束优化问题的精确罚函数方法 在这一章，我们将从非线性优化问题的l l 精确罚函数的最优性条件和已有的 罚函数方法展开详细的论述，并在此基础上提出一种新的精确罚函数，然后结合 现有的方法形成新的求解约束优化问题的罚函数方法 2 1l l 精确罚函数的最优性条件 对于一般的非线性约束优化问题 其中，尬，尥是下标集，工卉，f m lum 2 是一r 1 的连续函数，对于问 题( 2 1 ) ，构造如下精确罚函数 p ( 五) = 1 t f ( x ) 一 ：m i n o ，妒i ( 工) l + i f ( 砷i ( 2 2 ) 1?1 i e m li m 2 文献【1 3 】表明，在一定条件的假设下，对于任意充分小的p ，问题( 2 1 ) 的最优 解即是p 的一个极小解关于求p 的极小解的算法，已经有很多学者做过研究通 过在每一个迭代步使得p 充分下降，可以得到全局收敛性 设，是p 的最优解，记 a l = ( f m l i 办( x o ) = 0 1 ，a 2 = f m 2 i 咖( x o ) = o ) ， v l = i m l l f ( ) 一 = 力对托讯纵 u 六 m 吖 北京交通大学硕士学位论文 第2 章求解非线性约束优化问壁的精确跑圈塾方选 定义2 1 如果点p 满足定理2 1 中的条件( i ) ，则称p 为p 的一个稳定点，若妒同 时满足定理2 1 中的条件( i ) 和( i i ) ，则称p 为p 的一阶点 文献 6 1 中还给出了尸的二阶必要性条件和二阶充分性条件，主要结论由以 下两个定理给出 定理2 2 ( 二阶必要性条件) 设八工) ，咖( 曲，i m lu 均为二阶连续可微函 数，且i v 妒i ( p ) li a lua 2 l 线性无关，若p 为p 的局部最优解，那么存在向 量a ，山，满足 ( i ) p v f 一f nv 驴f + i 耽j g ，l ( 妒i ) v f = 拒a ia i v 矿i 一f a 2t o i v ( 多i ； ( i i ) 0 a i 1 ，i a l ，一1 o ) i 1 ，i a 2 ； ( i i i ) 对于任意的y 满足y 7 v 咖= 0 ，i a lua 2 ，均有 y r 0 v 2 厂一v 2 咖+ 昭，z ( 妒2 卉一也v 2 办+ z t o i v 2 咖y 0 定理2 3 ( 二阶充分性条件) 设，( 功，咖( 曲，f m lu m 2 均为二阶连续可微函数，那 么p 为p 的唯一最优解的充分条件是存在向量a ，满足 ( i ) p v f 一i ，lv 妒f + i y 2s g n ( d p i ) v 妒i = f “la i v i 一麒20 3 i v 妒i ； ( i i ) 0 a i 1 ，i a i ，一1 蚴1 ，i a 2 ； ( i i i ) 对于任意y 满足 i y r v r 多f = 0 ，i a 2 ， y t v b i = 0 ，i a i ，a i 0 ， i y r v b f 0 ，i a 1 ，, l i = 0 ， 均有 y 丁0 v 2 厂一v 2 办+ s g n ( 咖) v 2 办一 v 2 蛾+ 铆v 2 办) y 0 设 v f ( p ) if a iu a 2 线性无关，则在凸规划的情况下，j l f 的一个阀值为【1 1 】： 一 ! ( 2 3 、 m a x a ；，i u m 、 其中 和满足 v ，( p ) = l ；v ，一u ；v ， i e a li c c a 2 文献 4 ，5 】表明，若p 满足二阶充分性条件，则不需要凸性和线性无关性的假 设，阀值( 2 3 ) 也是成立的 9 北京交通大学硕士学位论文 第2 章求解非线性约束优化问题的精确罚函数方法 2 2 现有的l l 精确罚函数方法 为表述方便起见，我们仅考虑含有不等式约束的非线性优化问题 i i l i n ，( x ) ( 2 4 ) j t 咖( 力0 ，i = 1 ，2 ，m 类似于( 2 2 ) ，问题( 2 4 ) 的l i 精确罚函数问题如下 面np ( 五p ) = 厂一五1 l | = l m i n o ，咖( 曲 ， ( 2 5 ) 在一定条件的假设下，问题( 2 5 ) 的最优解也是问题( 2 4 ) 的解【4 ，5 ，6 】在求 解p 的极小解时，主要的困难在于如何克服其在约束边界上的不可微性介绍已 有的有效算法之前，我们先给出一个s 一积极约束的定义 定义2 2 设s 是一个充分小的正数，如果有( x b i 岛我们称咖( 曲在，处 是s 一积极约束 下面我们从细节方面介绍文献 3 】中使用的算法思想 2 2 1 水平下降方向h 对于问题( 2 4 ) ，不妨设前t 个约束在，处是s 一积极约束，即 ( x k ) l 岛i = 1 ，2 ，t ， ( 2 6 ) 办( ) 8 不影响讨论，因此，为表述方便，目前假设没有可行约束) 现 在，可以把p ( 五l , t ) 分成两部分，记可微的一部分为 州曲嘲曲一三静， 因此，在的邻域内，有 地) = 州力一去血n ( o 砌( 埘 ( 2 8 ) 鲁 文献【3 】中考虑对p ( x ) 的二阶变化量求极小，即 m i nv p 办+ l h r v 2 p l h - ，1 扛l “v 妒歹庇+ 芝1 7 v 2 f j l ”， ( 2 9 ) 其中，引号部分表示具有类似形式的项，即“a 取值为0 或者一m 1 0 北京交通大学硕士学位论文第2 章求解非线性约束优化问题的精确罚函数方法 由于p ( 曲在约束边界的不可微，导致了引号部分的不可微性，这使得求解问 题( 2 9 ) 的一个下降方向变得相当困难因此，文献【3 】考虑限制h ，使得 v j i l + 石1 矿v 2 咖h = 0 ，i = 1 ，2 ，f 这样就可以得到一个容易计算的问题因此可以通过求解在s 一积极约束的一i 阶 变化量为0 的条件下极小化p ( 曲的二阶变化量，从而得到下降方向h ，即 m i nv p r h + i 1 r v 2 p l h f( 2 1 0 ) 1 、一一7 s f v 妒 j l + 去j l z r v 2 f h = 0 ，i = 1 ，2 ，f 问题( 2 1 0 ) 等价于 卿n 叩l ( h = v p ； + l h r v 2 p l h - - 善t l i ( v l h r v 2 驴i h ) ， ( 2 1 1 ) 而问题( 2 1 1 ) 可以用下列问题近似 m 。i nm 。a xl 加拟v 2 p 1 - 酗v 2 ，) m 一酗v 妒，) ， ( 2 1 2 ) 其中夏是a 的一个近似，文献【3 】中给出了这种近似方法 l ( h ，a ) 关于a 求导可得 v 妒r h = 0 ，i = 1 ，2 ，t ( 2 1 3 ) 记a = ( v 妒l ( ) ，v 妒2 ( ) ，v 办( ) ) ，矩阵乙蚴卅满足 a 下z = 0 ，( 2 1 4 ) z 丁z = 厶- f ( 2 1 5 ) 由( 2 1 3 ) 式可知，可对h 作如下变换：h _ z w ，则( 2 1 2 ) 式变为 呼妒z r ( v 2 即酗v 2 妒乒w + v p j z m ( 2 1 6 ) 如果z 7 ( v 2 p l 一名l 兔v 2 咖) z 正定，那么问题( 2 1 6 ) 的解可通过求解下式得到 f z 丁( v 2 p 1 一驴j ) z w = 一z 7 v p l ( 2 1 7 ) 诗l 记问题( 2 1 7 ) 的解为w ，则问题( 2 1 0 ) 的一个近似解为h 卜z w 假设z r v p i 0 ，那么h 就是p 在处的一个下降方向，且h + 是文献 9 】中 使用的一阶投影方向的一个二阶近似 北京交通大学硕士学位论文第2 章求解非线性约束优化问题的精确罚函数方法 定理2 3 表明，在局部最优解的附近，真正的投影海色阵是正定的因此，在 实际计算中，投影海色阵并不需要精确求出，而是通过一个正定矩阵z r b z 来近 似当i i m r v p l ( 除特别注明外，本文所使用的范数均是指二范数) 不够充分小 时，离p 的稳定点较远，此时对偶估计仉) 几乎没有什么意义，因此可以直接用正 定矩阵矽b z 来近似z 丁v 2 p l z ，夏不需要计算 2 2 2 对偶估计夏 设 ) 一j ，其中元是p 的一个稳定点，由定义2 1 知，存在向量夏满足 v 八动一三否v 纵习2 争v 纵动， 亿 其中，l e = l fl f ( 习 0 ，则仇卜仇圳转步5 ， 步3 ：确定改，使得对任意的i 厶，有仇sn ， 口m 一吼+ l o l 。v 蛭矗，矿“= j g ，l ( v 庇) ， 步4 ：如果a k + l 0 ，转步5 ； 否则，厶+ l 卜厶一 ? 七l ，k 卜k + 1 ，转步2 ， 步5 ：+ 1 卜+ 仇7 z ，如果p ( + 1 ) 0 ) 之间做一个三次插值极小化，算法停止 借助于上述线搜索策略，文献【3 】中给出了求解p 的最优解的算法 算法2 2 2 初始步：给定初始点p r n ，勖，a o ，五t o l ，七卜0 ， 步l ：k4 - - - - - k + 1 ，确定学，如果i l 虿v p i i ，转步2 ； 否则，转步3 ， 步2 ：胪卜一磊( 刁晚z 七) 一1 刁审p ，通过算法2 2 1 确定鲰，令+ 1 = + 吼胪， 1 4 北京交通大学硕士学位论文第2 章求解非线性约束优化问题的精确罚函数疗法 返回步l ， 步3 ：解a k a k 亏p ，如果存在j 使得剪k 芒【o ，丢】，则胪一噶磊u j v j ( x t ) ， 转步4 ；否则，转步6 ， 步4 ：如果( 亏p + m i n ( o ，t ) v 妒舻 0 ，f 0 ， ( i i i ) o o a ( o + ) = l i 峰o + 挈 0 定义2 3 设妒( 贾) 0 ，办( 动= 0 ，记i = fl 破( 贾) = 0 ，f = 1 ，2 ，l 如 果妒( 曲在j 处可微， ( 功在贾处连续可微，v 庇f ( j ) ，f = 1 ，2 ，k ，线性无关，且 存在z r y 使得v f ( 劝丁z o m 乙 i = 仉 一 ，咖 n罾 赋 北京交通大学硕士学位论文第2 章求解非线性约束优化问题的精确罚函数方法 任选一个可行点戈，且满足j y ，记 口 一 衰器，厅 那么，我们有 ，( 幻= p l ( x ，口) p l ( 曩口) = ，( 贾) + 口 ，( 动， 矛盾，因此j 是问题( 2 2 7 ) 的可行点下面证明元是问题( 2 2 7 ) 增加一个约束工 y 的最优解，设x 为问题( 2 2 7 ) 的任意一个不同于j 的可行点，且j x 口厅，则 ，( 劝- - p i ( 贾，口) p 1 ( x ，口) = 厂( 曲， 因此元是问题( 2 2 7 ) 新增加一个约束x y 后的非线性优化问题的解 口 定理2 5 设工妒在问题( 2 2 7 ) 的严格局部最优解j 的某一邻域内连续可微，并设 在j 处的m f 条件成立，那么存在一个画0 ，使得对任意的口 厩j 为p l ( x ，a ) 的 一个局部最优解 证明设元为问题2 2 7 的严格局部最优解如果i = f i 咖( 动= 0 ，i = 1 ，2 ，m 为空集，则定理是成立的假设j 饥由引理2 2 知，对于任意充分大的口，存 在8 ) 0 ，z ( 口) ，使得在 ；e ( a 0 ) 内x ( a 0 是p l ( 工，口) 的一个局部最优 解，且l i n l c r - + 。s ( 口) = 0 设口充分大，从而使得文口) 否下面我们只需要证明对任意充分大 的口，x ( a ) 是问题( 2 2 7 ) 的可行点即可假设不可行，则存在一个正序列 啦l _ o o ，使得顶口f ) 不可行，根据引理2 1 ，存在一个有界函数d ( x ) ：辑，功一，使 得v 工( 贾，8 ) 有 v f ( 曲。吠曲1 ，i i 取s 1 ( 0 ，叫，使得j ( 曲 0 ，x ，8 1 ) ，f 垡i ，因此当工 ，1 ) 且x 不可 行时，若啦充分大，v p l ( x ( a f ) ，a f ) 7 d ( 工( 啦) ) 时对p p ) 没有任何影响，为方便表述起见，对于( 2 3 1 ) 中的情况 我们暂且小予考虑 若点属于情况( i i i ) ，此时p ( x ，) 整体上不可微，但是f ( x ) 是可微的，我们 借助于2 2 节中介绍的文献【3 】中的方法，可将p ( x ，) 分成两部分：可微部分和不 可微部分，即 -i_1 p ( x ，p ) = 厂( 曲+ 二 ：im i n 0 ，f ( 工) i ， ( 2 3 3 ) l l - j 括l 其中八力为p ( x ，p ) 的可微部分，而：i ；：l im i n 0 ，咖( z ) ) i 为不可微部分我们 称v f ( x ) 为以五j l l ) 的伪梯度 与( 2 1 0 ) 式相对应，( 2 3 3 ) 式的水平下降方向h 可以通过求解下列问题得到 埘nv f r h +