（运筹学与控制论专业论文）非线性规划中的精确罚函数.pdf

摘要 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域求解约束非 线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和 拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法罚函数方法通过求 解一个或多个罚阔题来得到约束规划问题的解如果罚问题的极小点是原约束规划 问题的极小点，则称此罚问题中的罚函数为精确罚函数本文研究了f 1 精确罚函数 的全局精确罚性质及其光滑化，低次罚函数的局部、全局精确罚性质低次罚函数的 光滑化，k c a l m 条件与精确罚性质的关系，以及整数规划中的精确罚函数 本文结构安排如下第一章，我们简要介绍了目前国内外关于精确罚函数的研 究工作第二章，我们研究了f 。精确罚函数的全局精确罚性质及其光滑化在1 目 标函数满足强制性条件；2 原约束非线性规划问题只有有限个全局极小点；3 原约 束非线性规划问题在其任何全局极小点处都满足k k t 二阶充分条件的假设下，我 们给出了f 1 精确罚函数的全局精确罚性质，即当罚参数充分大时，原约束非线性规 划闯题的全局极小点集与z 。罚问题的全局极小点集相同由于? i 精确罚函数的不可 微性，一般不能直接采取利用导数的最优化方法去求解f t 罚问题为了克服这一缺 陷，我们给出了f l 精确罚函数的一种二次函数光滑逼近，并证明了如果在可行域的 拟内部至少存在一个原问题的全局极小点，那么当罚参数充分大时，任何光滑后的 罚问题的全局极小点一定是原问题的全局极小点如果原问题可行域是拟强壮集， 那么当罚参数充分大时，任何光滑后的罚问题的全局极小点一定是原问题的可行近 似全局极小点，且近似程度可以预先给定我们给出的数值例子说明通过解光滑化 后的罚问题以求解原问题的方法是切实可行的第三章，我们首先引进低次罚函数 在k k t 二阶充分条件成立下，我们得出低次罚函数的局部精确罚性质，即任何原问 题的满足k k t _ 阶充分条件的局部极小点都是低次罚函数的严格局部极小点，而且 这里的罚参数可以取任何正数然后，在上述第二章的三个假设下，我们得出了低次 罚函数的全局精确罚性质，即当罚参数充分大时，原约束非线性规划问题的全局极 小点集与低次罚问题的全局极小点集相同由于低次罚函数同f l 精确罚函数一样具 有不可微性，我们接下来给出了关于低次罚函数的一个二次函数光滑逼近，并得到了 与上述第二章中对z 。精确罚函数进行光滑逼近所得到的相关结论相类似的结果第 四章，我们首先给出了原问题在一点的k - c a l m 条件的定义，并给出了原问题局部极 小点满足k c a l m 条件的充要条件接着，引入了原问题的摄动问题在( o ，0 ) 兄m r 。 的k c a l m 条件的定义，这里m ? 分别表示原规划问题的不等式约束及等式约束的个 i 数并证明了原问题在任何全局极小点都满足k c a l m 条件当且仅当原问题的摄动问 题在( 0 ，0 ) r ”r 满足k c a l m 条件我们证明了对任何给定的 0 ，如果存在 满足k k o 的k ，使得原规划问题在z + 是k c a l m 的，那么对任何罚参数q 0 ，z + 都是 罚问题m i n 。x 磺o ( z ) ( 参见( 4 3 2 ) ) 的局部极小点此外，我们还证明了原问题的摄 动问题在( o ，0 ) r ”冗“是k - c a l m 的，当且仅当存在q o 0 ，使得当q 譬。时，原问 题与罚问题m i n 。x 礞( z ) ( 参见( 4 3 2 ) ) 的全局极小点集相同最后，我们给出了精 确罚函数砑( o ) ( 参见( 4 3 1 ) ) 的二次光滑逼近，从而得到了光滑罚问题，并证明了当 罚参数q 充分大时，该光滑罚问题的全局极小点是原问题的近似全局极小点，且近 似程度可以预先给定第五章，我们考虑整数规划中的精确罚函数首先我们讨论 了一种对数指数非线性函数的浙近强对偶性及精确罚性质，指出不需要进行对儡搜 索，而可以通过精确罚来解原规划问题然后我们讨论了另一种对数一指数非线性函 数的精确罚性质，并由精确罚性质得到了渐近强对偶性接着我们讨论了含两个参 数的几种光滑精确罚函数最后，我们给出了整数规划中精确罚函数的一般形式 关键词非线性规划精确罚函数光滑逼近k - c a l m 条件整数规划 i i a b s t r a c t c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n gp r o b l e m sa b o u n di nm a n yi m p o r t a n tf i e l d s s u c ha se n g i n e e r i n g ，n a t i o n a ld e f e n c e ，f i n a n c ee t c o n eo ft h em a i na p p r o a c h e sf o r s o l v i n gc o n s t r a i n e dn o n l i n e a rp r o g r a m m i n gp r o b l e m si st ot r a n s f o r mi ti n t ou n c o n s t r a i n e dn o n l i n e a r p r o g r a m m i n gp r o b l e m p e n a l t yf u n c t i o n m e t h o d sa n d l a g r a n g i a n d u a l i t ym e t h o d s a r et h et w o p r e v a i l i n ga p p r o a c h e st oi m p l e m e n t t h et r a n s f o r m a t i o n p e n a l t yf u n c t i o nm e t h o d ss e e kt oo b t a i nt h es o l u t i o n so fc o n s t r a i n e dp r o g r a m m i n g p r o b l e mb ys o l v i n go n eo rm o r ep e n a l t yp r o b l e m s i fe a c hm i n i m u mo ft h ep e n a l t y p r o b l e mi sam i n i m u mo ft h ep r i m a lc 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 ，t h e nt h e c o r r e s p o n d i n gp e n a l t yf u n c t i o ni sc a l l e de x a c tp e n a l t yf u n c t i o n i nt h i st h e s i s ，w e d i s c u s sg l o b a le x a c tp e n a l t yp r o p e r t yo fl le x a c tp e n a l t y f u n c t i o n ，s m o o t h i n go fz l e x a c tp e n a l t yf u n c t i o n ，l o c a le x a c tp e n a l t y p r o p e r t ya n dg l o b a le x a c tp e n a l t yp r o p - e r t yo fl o w e ro r d e rp e n a l t yf u n c t i o n ，s m o o t h i n go fl o w e ro r d e rp e n a l t yf u n c t i o n ，t h e r e l a t i o n s h i pb e t w e e nk - c a l mc o n d i t i o n sa n de x a c tp e n a l t yp r o p e r t y , e x a c tp e n a l t y f u n c t i o n si ni n t e g e rp r o g r a m m i n g t h ep r e s e n tt h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r1 w eg i v eab r i e fi n t r o - d u c t i o nt ot h ee x i s t i n gr e s e a r c hw o r ko ne x a c tp e n a l t yf u n c t i o n s i nc h a p t e r2 ， w ed i s c u s st h e 斟o b a le x a c tp e n a l t yp r o p e r t yo f f 1 e x a c tp e n a l t yf u n c t i o na n di t s s m o o t h i n g u n d e rt h ef o l l o w i n ga s s u m p t i o n s ：1 t h eo b j e c t i v ef u n c t i o ns a t i s f i e st h e c o e r c i v ec o n d i t i o n s ；2 t h e r ea r eo n l yf i n i t eg l o b a lm i n i m ao ft h e p r i m a lc o n s t r a i n e d n o n l i n e a rp r o g r a m m i n gp r o b l e m ；3 k k ts e c o n do r d e rs u f f i c i e n c yc o n d i t i o no ft h e p r i m a lc o n s t r a i n e dn o n l i n e a rp r o g r a m m i n gp r o b l e mh o l d sa ti t sa n yg l 【o b a lm i n i - m u m ，w ee s t a b l i s ht h eg l o b a le x a c tp e n a l t yp r o p e r t y i e t h es e to fg l o b a lm i n i m a o ft h ep r i m a lc o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g p r o b l e mi si d e n t i c a lt ot h es e to f g l o b a lm i n i m a o f t h e le x a c tp e n a l t yp r o b l e m s i n c et h ez ie x a c tp e n a l t yf u n c t i o ni s n o td i f f e r e n t i a l ，g e n e r a l l ys p e a k i n g ，o p t i m i z a t i o nt e c h n i q u e s e m p l o y i n gg r a d i e n tc a r l n o tb eu s e dd i r e c t l yt os o l v et h e1 1e x a c tp e n a l t y p r o b l e m t oa v o i dt h i sd r a w b a c k ， w ep r o p o s eaq u a d r a t i cs m o o t h i n g a p p r o x i m a t i o nt ot h ez l e x a c tp e n a l t yf u n c t i o n i ti ss h o w nt h a ti ft h e r ee x i s t sa tl e a s to n eg l o b a lm i n i m u mo ft h ep r i m a lp r o b l e m i nt h eq u a s i - i n t e r i o ro ft h ef e a s i b l er e g i o no ft h ep r i m a lp r o b l e m ，t h e na n yg l o b a l m i n i m u mo ft h es m o o t h e d p e n a l t yp r o b l e m i sa g l 【o b a lm i n i m u m o ft h ep r i m a lp r o b - i e mw h e nt h ep e n a l t yp a r a m e t e ri ss u f f i c i e n t l yl a r g e i ft h ef e a s i b l er e g i o no ft h e p r i m a lp r o b l e mi sq u a s i r o b u s t ，t h e na n yg l o b a lm i n i m u mo ft h es m o o t h e dp e n a l t y p r o b l e mi saf e a s i b l ea p p r o x i m a t eg l o b a lm i n i m u mo ft h ep r i m a lp r o b l e mw h e nt h e p e n a l t yp a r a m e t e ri ss u f f i c i e n t l yl a r g e ，a n dt h ep r e c i s i o no ft h ea p p r o x i m a t i o nc a n b es e ti na d v a n c e t h ef o l l o w i n gn u m e r i c a le x a m p l e ss h o wt h a ti t i sa p p l i c a b l et o s o l v et h es m o o t h e dp e n a l t yp r o b l e mi no r d e rt os o l v et h ep r i m a lp r o b l e m i nc h a p t e r3 ，w ef i r s t l yi n t r o d u c el o w e ro r d e r p e n a l t yf u n c t i o n u n d e rt h ek k t s e c o n do r d e rs u f f i c i e n c yc o n d i t i o n ，w eo b t a i nt h el o c a le x a c tp e n a l t yp r o p e r t y i e a n yl o c a lm i n i m u ms a t i s f y i n gt h ek k ts e c o n do r d e rs u m c i e n c yc o n d i t i o ni sas t r i c t l o c a lm i n i m u mo ft h el o w e ro r d e rp e n a l t yf u n c t i o n ，a n dt h e p e n a l t yp a r a m e t e rc a n b ea n yp o s i t i v en u m b e r t h e n ，u n d e rt h es a m et h r e ea s s u m p t i o n sa si n c h a p t e r 2m e n t i o n e da b o v e ，w eo b t a i nt h eg l o b a le x a c tp e n a l t yp r o p e r t y i e t h es e to f i i i g l o b a lm i n i m a o ft h ep r i m a lc o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g p r o b l e m i si d e n t i c a l t ot h es e to fg l o b a lm i n i m ao ft h ei o w e ro r d e re x a c tp e n a l t yp r o b l e m a st h e ，1 e x a c tp e n a l t yf u n c t i o n t h el o w e ro r d e re x a c tp e n a l t yf u n c t i o ni sn o td i f i e r e n t i a l t h u sw ep r e s e n taq u a d r a t i cs m o o t h i n ga p p r o x i m a t i o nt ot h el o w e ro r d e r e x a c t p e n a l t yf u n c t i o n ，a n do b t a i ns i m i l a rr e s u l t s t ot h e s eo b t a i n e di nt h es m o o t h i n g a p p r o x i m a t i o ni nc h a p t e r2 i nc h a p t e r4 ，w ef i r s t l yg i v et h ed e f i n i t i o no fk - c a l mc o n d i t i o na tap o i n tf o rt h e p r i m a lp r o b l e m ，a n dt h e no b t a i nt h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o ral o c a l m i n i m u mo ft h ep r i m a lp r o b l e mt ob ek c a l m n e x tw eg i v et h ed e f i n i t i o no fk c a l mc o n d i t i o na t ( 0 ，0 ) r ”r f o rt h ep e r t u r b a t i o np r o b l e m ，w h e r e 仇，? d e n o t e t h en u m b e r so fi n e q u a l i t y a n de q u a l i t yc o n s t r a i n t sr e s p e c t i v e l y ，a n ds h o wt h a tt h e p r i m a lp r o b l e ms a t i s f i e sk c a l mc o n d i t i o na ta n yg l o b a lm i n i m u mi fa n do n l yi ft h e p e r t u r b a t i o np r o b l e ms a t i s f i e sk - c a l mc o n d i t i o na t ( 0 ，0 ) r “r t h e nw es h o w t h a tf o ra n y 0 ，i ft h e r ee x i s ta k 0s u c ht h a tt h ep r i m a l p r o b l e m i sk c a l ma t z + ，t h e nz i sal o c a lm i n i m u mo ft h ep e n a l t yp r o b l e mm i n 蚝x 砖o ( z ) ( s e e ( 4 3 2 ) ) w i t ha n yp o s i t i v ep e n a l t yp a r a m e t e rq m o r e o v e r ，i ti ss h o w nt h a tt h ep e r t u r b a t i o n p r o b l e mi sk c a l ma t ( 0 ，0 ) r “r “i fa n do n l yi ft h e r ee x i s t saq o 0 ，s u c h t h a tt h es e to fg l o b a lm i n i m ao ft h ep r i m a lp r o b l e mi d e n t i c a lt ot h a to ft h ep e n a l t y p r o b l e mr a i n 。x 露( x ) ( s e e ( 4 3 2 ) ) w h e nq 卯f i n a l l y ，w ep r o p o s et h eq u a d r a t i c s m o o t h i n ga p p r o x i m a t i o nt ot h ee x a c tp e n a l t yf u n c t i o n 砰( x ) ( s e e ( 4 3 1 ) ) a n dt h e c o r r e s p o n d i n gs m o o t h e dp e n a l t yp r o b l e m w e s h o wt h a ta n y g l o b a lm i n i m u m o ft h e s m o o t h e dp e n a l t yp r o b l e mi saa p p r o x i m a t eg l o b a lm i n i m u mw h e nt h ep a r a m e t e r 口i ss u f f i c i e n t l yl a r g e ，a n dt h ep r e c i s i o no ft h ea p p r o x i m a t i o nc a nb es e ti na d v a n c e i nc h a p t e r5 ，w ec o n s i d e re x a c tp e n a l t yf u n c t i o n si ni n t e g e rp r o g r a m m i n g f i r s t l y w ed i s c u s st h e a s y m p t o t i cs t r o n gd u a l i t yp r o p e r t ya n de x a c tp e n a l t yp r o p e r t yo f al o g a r i t h m i c e x p o n e n t i a ln o n l i n e a rf u n c t i o n a n dw es h o wt h a ti ti sn o tn e c e s s a r y t oi m p l e m e n td u a ls e a r c ht os o l v et h ep r i m a lp r o b l e m i n s t e a dt h ep r i m a lp r o b l e m c a l lb es o l v e db ye x a c tp e n a l i z a t i o nt h e nw ed i s c u s st h ee x a c tp e n a l t yp r o p e r t yo f a n o t h e rl o g a r i t h m i c e x p o n e n t i a ln o n l i n e a rl a g r a n g i a nf u n c t i o n ，a n dw eo b t a i nt h e a s y m p t o t i cs t r o n gd u a l i t yp r o p e r t y b yt h ee x a c tp e n a l t yp r o p e r t y n e x tw eg i v e s o m es m o o t hp e n a l t yf u n o t i o n sw i t ht w op a r a m e t e r sa n ds h o wt h e i re x a c tp e n a l t y p r o p e r t i e s f i n a l l yw ep r o p o s eg e n e r a le x a c tp e n a l t yf u n c t i o n si ni n t e g e rp r o g r a 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 e x a c tp e n a l t yf u n c t i o n s m o o t h i n ga p p r o x i m a t i o n k - c a l mc o n d i t i o n i n t e g e rp r o g r a m m i n g i v 上海大学媾士学位论文 第一章预备知识 l 。1 问题的提出 考虑下述约束最优化阉题： ( p ) m i nf ( x ) s t t 热茹) s0 对 - l 一4 ，粥 1 ) 玛( z ) 一0 对j 一1 ，z 鬈x 这里“m i n ”是茨文“m i n i m i z e ”的缩写，表示“求极小”，s t 。”悬英文“s u b j e c tt o ”的 缩写，表示“受隈希l 子”，f ，g l ，g m ，h l ，。，毛楚定义程舻上麴函数，x 是舻的一 个子集合，。= ( 茹l ，) 是n 维向量 瓣数，通常称为羁标函数簿一个豹束历( 茹) 0 ，i l ，m ，称为一个幂等 式约束，每一个约束砖( 聋) = o ，j 1 ，i ，称为一个等式约柬，x 称为集合约柬， 如对变量给出的上下界约束等当目标函数和所有的约束函数怒线性的，而且熊合 约束能表示成线性等式或f 昶) 线性不等式时，上述问题称为线性规划阀题，否则稼为 非线性规划问题 集会 l 盈( 鬈) o ，i = 1 ，m ，屯( 鬈) = 0 ，j = 1 。，z ，。x ) 称麓闯题妒) 的可行域，记为s s 中的元素称为可行点设茔s 如果存在主的某个空心邻 域a r 涵6 ) = 如重酬善一重 母，使缚薄任键落s n a 卜( 雪，甄或立，s ，( z ) ， 则称2 为问题( p ) 的局部极小点如果邂一步成立，( 牙) o ， 虫扛) 0 ， 此外，设在互严格互补条件成立，即 峨 0 ，对所有i 而( 童) 翅雪为f 鳓砖严舔局毒掇，l 、点。 命题1 2 3 俾k 仁阶充分祭件，参见文献脚中定理彳彳，纠设，g i ，i l ，m ， b ：j 一1 ， 二泠连续可擞，霪为蜀绣k k z 奏，辱，为每叠勰霹燕秘器褡葫霉 乘子向量令璐( 。) = 0 矗( 。) i 啦 o ) ，露( 盘) = i o ( z ) i 吼一o 进一步 设v 羔玉谚，露，在雄 9 0 斟降麓耄婴，蛞0 婕碳习 上正定，即对 意寥g y 0 ，成立 ”t 屹l ( 茧，西，o ) 鲈 0 则牙为( p ) 的严裕局部极小点 螽越1 2 4 陪见史献磐彰申定理基嫂) 设牙建问题( 聊的局部极小点，且满足嬲彤q 那么雷为( p ) 的暂z 最 1 3 罚函数方法 羲蕊数方涤遴过褥瓣趣f 霸转纯灸今无约慕最镶纯辩蘧或多个无数束曩後亿 问题来进行求解，是求解问题( p ) 的主要方法之这里的无约柬蠼优化问题称为罚 问题辩一个罚闯题，若其任鹰全局极小点酃是潦约束簸潮问题的全局檬小点，躐联 约束规划问题的任何局部极小点都是此罚问题的局部极小点，则称此罚问题中的罚 泊数为精确罚函数，诧阏题称为精确罚阔题 用镄函数方法来解约束最优化问题通常认为由c o u r a n t 提出后来，c a m pf 1 2 1 和p i e t r g y k o w s k if 6 4 1 讨论了罚函数方法在解非线性黼划问题中的应用f i a c c o j 和m c c o r m i c kf 2 4 j 一【2 9 】在利用罚涵数方法方面取褥了重太进展，他们提出了s u m t ( s e q u e n t i a lu n c o n s t r a i n e dm i n i m i z a t i o nt e c h n i q u e ) 3 上海大学博士学位论文 惩罚，我们茵先对问题( 功定义罚项函数如下： o ( 茹) = 多陕( z ) j + 妒( 刮， ( 1 3 1 ) 这飘妒：r _ 皿和妒：r _ r + 是满足下述条件的连续函数： 曲( 掣) o 髁u 0 ，存在一点x 使碍p ( 瑚= f ( x ，) + t t a ( x 。) ，那么下述结论成立： j i n f f ( x ) ：g i ( x ) 0 ，i = 1 ，m ，h i ( x ) 一0 ，i = l ，f ，茁x ) 乏s u p 。 o 口( p ) ； 2 ，( 勘) 起关于弘的单调不减函数，口( 弘) 是荚于弘的尊调不减函数，a ( 茹。) 是荚于封的 单调不增函数 4 上海大学博士学位论文 定理1 3 1 圆文献阿中定理垒害。夥设，g i ，i = l + ，湃，玛，j = l ，为秽上 的连续函数，x 为r n 中的非空集合设问题( p ) 至少有一个可行解，口为由一7 纠髭义 的连续蕊数如幕对话傍p 0 ，存在一点翰x 使得# 和) = 芦( 。p + 芦8 ( ) ，而 且 ) 包含于x 中的一个紧子柴，那么成立 1 i n f f ( x ) ：热f 霉) 兰0 ，i = 1 ，m ，趣( 童) 0 ，i = 1 ，z ，茹x ) = s u p 8 ( 芦) 弘0 = l i m 口( 肛) “ + 磐 钆) 的任何收敛予列的极限点是原问题( p ) 的一个藏优解j ， 1 1 m 肛盘( z “) = 0 ， “t 十 显然，蛰暴簿菜令垫浅立( ) = g ，鄹么鬈，爨骧漓怒秘赘簸饶解， 从定理1 _ 3 1 得知，溻取罚参数卢充分太肘，问题( b ) 的最优解可以任意逼避原 游题( p ) 的最饶解，霹辩，( ) + p 口( 筲辍任意逼近霖翊遂( 蜀的最优值毽是，鼯 果我们选取了非常大的罚参数地可能会出现由于病态条件而导致的计算困难因此， 大多数剥庵嚣巍数方法寐求解豹索最饶纯闻疆豹算法都辩要解蕊有递增鞠参鼗鹃 系列罚闯题其中当解一个具有新参数的蹄问题时，初始点选取为解前一个罚问鼷所 褥至的全局极小点这释算法称为s u m tfs e q u e n t i a lu n c o n s t r a i n e dm i n i m i z a t i o n t e c h n i q u e ) ，由予要解系列无约束最优化问题，利用s u m t 来解原问题所需的计算 鼙是比较大的， 1 4 精确罚函数方法 精确罚函数缓念首先由e r e m i nf 2 2 】；l i 鼙z a n g n v i l l 9 2 】予上毽纪六十年代后翳掇疆 这是线性规划中大m 法在非线性规划中的自然推广从邪时起，精确罚函数一蠢在 数学趣划理论与方法串扮演根鬟要静角色f l 】1 4 f 7 】f 1 1 】f l 司f 1 5 lf l 一】f 2 胡 2 3 】f 3 2 】 f 3 3 35 f 3 7 】1 4 3 】 4 5 】f 47 f 5 0 jf 5 剐【5 9 】【6 5 】【7 0 7 2 】f 9 4 在算法方面，尽管使用精 确罚函数的历受已经缀长，但是直存畿着争论争论静根源在乎糟确罚函数静不 可微性从算法的兔度来看，这葺中不可微性能够引起所谓的“m a r a t o s 效应”，即引 越阻止快速局部收敛的现象为了克腋m a r a t o s 效应，人们发展了所谓的 w a t c h d o g t e c h n i q u e ” 1 3 和“s e c o n d o r d e rc o r r e c t i o nt e c h n i q u e s ”f 1 6 3 2 】f a 4 l a 6 另外， 些学者弓l 入了与上述精确罚函数完全不黼类的w 微精确镯函数 8 i 3 1 lf 4 4 】瞄5 l 6 6 l 甚 上海大学博士学位论文 f 6 7 f 6 8 f 7 l l + 这类可微精确疆瓣数出于其表达式包含有匿标函数及约束缀数的梯 度，在实际计算中过于复杂，大大限制了其实际应用从上世纪九十年代詹期开始， 非线性精确罚函数 4 8 】 7 3 【7 7 】 9 1 和低次罚函数 5 6 】 6 2 】得到了较广泛的研究，开 辟了关于精确罚基数兹新的研究领域，至今不断有薪的研究成果阋世， 下面我嚣l 绘窭发震最葱成熟戆羲耩礁嚣遗数方法熬囊要理论结集。设愿瓣麓固中 集合x 为开聚令( 1 3 4 ) 中p = 1 ，褥掰问题 ( 曩) 骢m ) + 肛( m 积 0 1 9 t ( z ) ) + 眦删) mf 称p l ( 墨努) 一，嚣) + 秘m a x o ，承( 。 + l 瓠z ) 1 ) 秀t 精确罚添数。l t 精 确罚函数又称为经典精确罚函数 定理1 4 1 r 见文献，v 中定理n 只j ，设叠为问题( p ) 的k 暂t 点，( 西，o ) 为与牙相 对应的脒硼t 子+ 避一步，设，和9 i ，i 如( i ) = 川9 “_ 茔) = 0 ，i = l ，m 是 凸函数，而且岛，j = 1 ，是仿龄最数，鄂么对芦m a x 每，f 而( 动，| 吗| ，j = 1 ，f 孟巍楚问题( 露) 姆解。 定理1 4 2 伶见文献口酊中匙埋 # j 设置为问题( p ) 的一个严格崩郎极小 最，f ，仇，i 一1 ，m ，i = 1 ，l 在牙的一个邻城内连续可微，进一步，设牙满 f 1 m a n g a s a r i a n 。f r o m o v i t z 约束品性那么存在口 0 ，使得对所有卢声，奎是问 题( 器) 的局部极小点 定理l 。碡3 。缪晃文献廖彩审定理# 彩设命题1 。袭3 戆条传成立，砖对经侮满 足p m a x 话i 、i 如( 童) ，f 吗 ，一1 ，f ) 的罚参数，童是罚问题( 只1 ) 的严格 局部极小点 8 上海大学懿士学袋论文 第量章 1 1 精确羁函数的光滑 乏 2 1 雩l 言 本襄我蠢】考虑如下不等式约寐 # 线燃趣划翊题： m i n 歹妇) s t 斯扛) 0 ，i = l ，m ， ( 2 1 1 ) x 舻。 这里，：r “_ r ，g i ：舻一r ，i 一1 ，m 二阶连续可微令s 为问题( 2 1 1 ) 的可行 域秘 s 一 士lz 匠r “，吼( 搿) o ，i = 1 ，m ( 2 1 2 ) 黻g ( 2 1 i ) 表示闷遂( 2 1 ，1 ) 的全筋极小患集。 闯蹶( 2 1 1 ) 的z 1 精确罚函数如下： ”t ( 。) ：= m ) + 口对( 。) ( 2 1 ，3 ) i = 1 这里 菇警) = m a x 0 ，热( 尘) ，一1 。，燃2 1 ，4 ) h a n 和m a n g a s a r i a n ( 见f 4 5 】，定理4 4 和4 6 ) 证明了可以由m a n g a s a r i a m f b m o v i t z 约束晶靛竣k k t z i i 奔充分条件褥出一类罚邈数斡精确罚槛质，冀中包含z l 稽确罚遁 数( z ) 参见命题1 4 2 ，1 , 4 3 f t 精确罚函数在那魑使得对巢个 l ，m ) 成立魏( z ) = o 的z 处不可微而 a # 线性趣划中绝大部分效果好的算法都要求目标滋数具露可微性，这促使人们去考 虑目标函数的光滑化【6 】 6 9 】f 8 4 j 【9 3 】p i n a r 和z e n i o s 【6 9 】针对髓规划问题提出了 对f l 糖确罚函数鹃二次瞒数光潺湛近。文献9 6 9 4 迁明了通过鼹光涝化嚣熟罚翘题，掰 以得到s w 行和犀近似全局极小虑，这里是某常数本章将针对般不等式约束问 题 2 ，1 1 ) 提出薪弱辩：l 糖礁毳函数豹二次涵数光瀵逼近 我们做如下假设 援设2 1 。1 歹f 甸满熙强刳挂务待，姆 1 i m 抽m ) _ + 。 上海大学博士学位论文 在程设2 1 1 下，存在一个紧爨x 辅搬、籍子集 ，使褥g ( 2 1 1 ) c i n t x 这 里i n t x 表示集合x 的内部如果我们只考虑全局极小点的话，那么原问题( 2 ，1 1 ) 等 谕予 m i n ( x ) s t 矾( 茹) 0 ，i = 1 ，m ( 2 1 5 j o x ， 即g ( 2 、1 1 ) = c ( 2 ，1 5 ) ，这里g ( 2 1 5 ) 表示问题( 2 1 5 ) 的全局极小点集 瑕设2 1 2 。c ( 2 1 1 ) 是非空有限集。 假设2 1 3 对任何矿a ( 2 1 1 ) ，存在”r m ，使得( 扩，”) 满足删瞄阶充 螽繁侮f 参瓤夸题i 2 s ： v 。l ( x 4 ，a 4 ) = 0 誓翟汪1 ，m6 ) 砖蠡( 矿) = 0 口r v 2 l ( x ，a ) 0 ，时任何y y ( 搿。) 这里五( z ，a 卜，( z ) 十a 舰( z ) ， i = l y e ，= 爷帮 善：耋篆：舅雪：三 ； ， e 。，z ， a ( 茹) = i