（运筹学与控制论专业论文）简单光滑乘子精确罚函数的理论和方法.pdf

摘要 现代科学、经济和工程的许多问题有赖于相应约束非线性规划问 题的全局最优解的计算技术。约束非线性规划问题已广泛涉及到许多 重要的邻域，其中包括经济模型，金融，网络与运输，数字集成设计， 图像处理，化学工程设计与控制，分子生物学，环境工程及军事科学等 等。然而，在过去的几十年间，由于约束非线性规划在许多邻域的重要 应用，其理论和方法已得到了很大的发展。求解约束非线性规划重要途 径之一是把它转化为无约束问题求解。而罚函数方法是将约束规划问题 无约束化的一种主要方法，它是通过求解一个或多个罚问题来得到约束 规划问题的解。如果单一一个罚问题的最优解是原约束问题的最优解， 则称此罚问题中的函数为精确罚函数，否则称为序列罚函数。若罚函数 p ( x ) 是x 的光滑函数，称p ( x ) 为光滑的。若罚函数p ( z ) 只是由目标函数 和约束函数组成，而不包含它们的梯度称p ( z ) 为简单的。若罚函数p ( 。) 既是光滑的，又是简单的，则称它为简单光滑罚函数。而传统罚函数是 精确的、简单的，则一定非光滑的，为此要使罚问题既简单、又光滑且 精确，则必须改变传统罚函数的定义，且要引进有关的乘子。传统罚函 数的定义为：p ( z ) = 0 甘。s 改造后的罚函数的定义为：z s = p ( x ) 芝0 ，甚至于p ( x ) 0 且远大于当x s 时的值 我们将定义一类简单光滑乘子精确罚函数。本文构造和研究了指数型和 对数型两类简单光滑乘子精确罚函数，我们用比较初等的方法证明这两 类简单光滑乘子精确罚函数问题的简单光滑精确性质，以及与原问题局 部最优解、全局最优解的关系。找出了原问题的k k t 乘子与罚问题的 乘子参数、罚参数间的关系，并对原问题的k k t 乘子进行了估计，给 出了计算原问题的种牛顿算法，并把它们应用于某类凸规划问题，数 值试验表明所给方法是有效的此外我们还研究了混合整数规划中的精 确罚函数。 本文结构如下： 第一章，我们简要介绍了目前国内外关于罚函数的研究工作状况和简单 光滑乘子精确罚函数的概念。第二章，我们研究了指数型简单光滑乘子 精确罚函数以及它的全局近似精确罚性质，并得出了原问题的k k t 乘 子与指数型乘子精确罚问题的乘子罚参数间的近似关系，当满足一定的 约束品性条件下，对原问题的k k t 乘子进行摄动，我们得出了相应罚 问题的全局最优解。对此我们引入简单光滑指数型乘子精确罚函数把一 个光滑凸规划的极小化问题化为紧集x 上强凸函数的极小化问题，然 后在给定的x 上用牛顿法对此强凸函数进行极小化。数值例子表明我 们给出的求解一类凸规划的算法是行之有效的。第三章，我们构造了对 数型简单光滑乘子精确罚函数。首先我们证明了原问题和相应的罚问题 全局最优解的近似等价性在二阶最优性充分条件下，我们给出了对数 型乘子精确罚函数的局部精确罚性质，即当罚参数充分大时，原问题满 足二阶最优性充分条件的局部极小点是对数型乘子精确罚函数的严格 局部极小点。进一步，根据得出的解的近似等价性，我们给出了原问题 的k k - t 乘子与相应罚问题中的乘子参数之间的关系。然后，我们又分 别给出了对数型乘子精确罚函数的弱对偶和强对偶定理并对乘子进行 有效的估计，最后，我们设计了一个对数型简单光滑乘子精确罚函数的 简单算法。我们给出的数值例子说明通过解对数型乘子罚问题以求原问 题的方法是切实可行的。第四章，我们考虑混合整数规划中的精确罚函 数，并给出了原问题与其相应的罚问题全局最优解的等价性的几个充分 条件，此外对于线性混合整数规划，我们找出了和k k t 乘子罚参数之 间的关系式。 关键词非线性规划，乘子精确罚函数，k k t 乘子，牛顿法，混 合整数规划 i i a b s tr a c t m a n yp r o b l e m si ns c i e n c e ，e c o n o m i c sa n de n g i n e e r i n gr e l yo nn u m e r i c a lt e c h n i q u e sf o rc o m p u t i n go p t i m a ls o l u t i o n st oc o r r e s p o n d i n gc 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 m s 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 s a b o u n di nm a n y i m p o r t a n t f i e l d sa n dt h e yi n c l u d ee c o n o m i cm o d e l l i n g ，f i n a n c e ，n e t w o r k sa n dt r a n s p o r t a t i o n d a t a b a s e sa n dc h i pd e s i g n ，i m a g ep r o c e s s i n g ，c h e m i c a le n g i n e e r i n gd e s i g na n dc o n t r o l ，m o l e c u l a rb i o l o g y , e n v i r o n m e n t a le n g i n e e r i n g ，m i l i t a n t n e s sa n ds oo d d u r i n gt h ep a s ts e v e r a ld e c a d e s ，g r e a td e v e l o p m e n th a sb e e no b t a i n e di nt h e t h e o r e t i c a la n dm e t h o d sa s p e c t so fc 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 gd u et ot h e i m p o r t a n tp r a c t i c a la p p l i c a t i o n s o n e o ft h ei m p o r t a n t a p p r o c hf o rs o l v i n gc o i l 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 gi st oc o n v e r ti ti n t ou n c o n s t r a i n e dp r o b l e m p e n a l t y f u n c t i o nm e t h o d sa r ep r a v a i l i n ga p p r o a c ht oi m p l e m e n tt r a n s f o r m a t i o n t h e ys e e k t 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 g o n eo rm o r e p e n a l t yp r o b l e m s i fo p t i m a ls o l u t i o no fo n ep e n a l t yp r o b l e mi st h a to ft h ep r i m a l p r o b l e m ，t h e nt h ec 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 o t h e r w i s ei ti sc a l l e ds e q u e n t i a lp e n a l t yf u n c t i o n i ft h ep e n a l t yf u n c t i o np 扛) i sa s m o o t hf u n c t i o no fz ，t h e np ( x ) i sc a l l e ds m o o t h i ft h ep e n a l t yf u n c t i o np ( x ) o n l y i sm a d eb yo b j e c t i v ef u n c t i o na n dc o n s t r a i n e df r m c t i o n ，a n dd on o tc o n t a i nt h e i r g r a d i a n t ，p ( x ) i sc a l l e ds i m p l e i fp e n a l t yf u n c t i o np ( x ) i sb o t hs m o o t ha n ds i m p l e ， p ( x ) i sc a l l e ds i m p l es m o o t hp e n a l t yf u n c t i o n a n dt r a d i t i o n a lp e n a l t yf u n c t i o ni s e x a c t ，i tm u s tb en o n s m o o t h e d t h e r e f o r ei fi no r d e rt ot h ep e n a l t yp r o b l e m i ss i m p l e a sw e l la ss m o o t h e d ，t h e nw eh a v et oc h a n g et h ed e f i n i t i o no ft h et r a d i t i o n a lp e n a l t y f u n c t i o na n dw h i c hd e p e n d so nt h em u l t i p l i e r so f p r i m a lp r o b l e n t h ed e f i n i t i o no f t h et r a d i t i o n a lp e n a l t yf u n c t i o n s ： p ( x 1 = 0 兮z s a n dt h ed e f i n i t i o no fi m p r o v e ds i m p l es m o o t h e dm u l t i p l i e r sp e n a l t yf u n c t i o n ： z s = p ( z ) 0 ，e v e np ( x ) 0 ，a n do v e rg r e a tav a l u eo fp ( z ) i i i f o rz s w ew i l ld e f i n eak i n do fs i m p l es m o o t hm u l t i p l i e r se x a c tp e n a l t yf u n c t i o n i nt h i s p a p e rw e w i l ld i s c u s st w ok i n d so f e x p o n e n t i a la n dl o g a r i t h m i cs i m p l es m o o t hm u l t i p l i e r se x a c tp e n a l t yf u n c t i o n w ew i l lp r o v et h ee x a c tp r o p e r t i e so ft h e s et w ok i n d s o fs i m p l es m o o t hm u l t i p l i e r se x a c tp e n a l t yf u n c t i o n s a n dt h er e l a t i o no fl o c a la n d g l o b a lo p t i m a ls o l u t i o nf o rp e n a l t yp r o b l e mw i t hp r i m a lp r o b l e m w ef i n do u ta k i n do fr e l a t i o nb e t w e e nt h ek k - t m u l t i p l i e r so fp r i m a lp r o b l e ma n dm u l t i p l i e r s p e n a l t yp a r a m e t e r so fp e n a l t yp r o b l e m f u r t h e r m o r e ，w ee s t i m a t et h ek ，k tm u f f - p l i e r sf o rp r i m a lp r o b l e ma n dg i v ea na l g o r i t h mf o rc o m p u t i n gp r i m a lp r o b l e m w e a p p l yt h e mf o rs o m ek i n d sc o n v e xp r o g r a m m i n gp r o b l e m ，t h en u m e r i c a le x p e r i m e n t s h o wt h a ti ti se f f e c t i v e f u r t h e r m o r e ，w ea l s od i s c u s st h ee x a c tp e n a l t yf u n c t i o n s i nm i x e d i n t e g e rp r o g r a m m i n g t h e p 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 np e n a l t yf u n c t i o n sa n dt h ec o n c e p to ft h e s i m p l es m o o t hm u l t i p l i e r se x a c tp e n a l t yf u n c t i o n i nc h a p t e r2 ，w ed i s c u s sa ne x p o n e n t i a ls i m p l es m o o t h m u l t i p l i e r se x a c tp e n a l t yf u n c t i o na n d i t sg l o b a la p p r o x i m a t e e x a c tp e n a l t y p r o p e r t y , a n dw e o b t a i na na p p r o x i m a t er e l a t i o nb e t w e e nk k tm u l t i p l i e r so fp r i m a lp r o b l e m a n d m u t i p l i e rp e n a l t yp a r a m e t e r so ft h ep e n a l t yp r o b l e m u n d e rt h es o m ec o n s t r a i n tq u a l i f i c a t i o n s ，p e r t u r b i n gt h ek - k tm u l t i p l i e r so f p r i r e a lp r o b l e m ，w em a y g e tt h eg l o b a lo p t i m a ls o l u t i o no ft h ec o r r e s p o n d i n gp e n a l t y p r o b l e m ，t h u s ，w er e d u c em i n i m i z i n gas m o o t hc o n v e xp r o g r a m m i n gt oam i n i m i z i n gs t r o n gc o u v e xf u n c t i o no nc o m p a c tx ，u s i n ge x p o n e n t i a ls i m p l es m o o t h e d m u t i p l i e re x a c tp e n l t yf u n c t i o n ，t h e nan e w t o nm e t h o df o rm i n i m i z i n gt h es t r o n g c o n v e xf u n c t i o no nxi sg i v e n t h en u m e r i c a le x m a p l e ss h o wt h a tt h em e t h o di s e f f e c t i v e i nc h a p t e r3 ，w ec o n s t r u c tal o g a r i t h m i cs i m p l es m o o t hm u t i p l i e re x a c t p e n a l t yf u n c t i o n f i r s t ，w ep r o v et h ea p p r o x i m a t ee q u i v a l e n c eo fg l o b a lo p t i m a l s o l u t i o nf o rp r i m a lp r o b l e ma n dc o r r e s p e n d i n gp e n a l t yp r o b l e m ，u n d e rt h es e c o n d o r d e ro p t i m a ls 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 yie w h e np 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 yl o c a lm i n i m u ms a t i s f y i n gt h es e c i v o n do r d e ro p t i m a ls l l f l i c i e n c yc o n d i t i o ni sas t r i c tl o c a lm i n i m u mo ft h el o g a r i t h m i c m u l t i p l i e re x a c tp e n a l t yf u n c t i o n f u r t h e r m o r e ，a c c o r d i n gt oo b t a i n e da p p r o x i m a t e e q u i v a l e n c ep r o p e r t yo ft h es o l u t i o n ，w eg i v eak i n do fr e l a t i o nb e t w e e nt h ek k t m u l t i p l i e r so fp r i m a lp r o b l e ma n dm u l t i p l i e rp a r a m e t e r so fc o r r e s p o n d i n gp e n a l t y p r o b l e m t h e n ，w er e s p e c t i v e l yg i v ew e a ka n ds t r o n gd u a l i t yt h e o r e mo fl o g a r i t h m i c m u l t i p l i e re x a c tp e n a l t yf u n c t i o na n de f f e c t i v e l ye s t i m a t eo fm u l t i p l i e r s f i n a l l y ，w e d e s i g na na l g o r i t h mt ol o g a r i t h m i cs i m p l es m o o t hm u t i p l i e re x a c tp e n a l t yf u n c t i o n t h em u m e r i c a le x a m p l e ss h o wt h a ti ti se f f e c t i v et os o l v et h el o g a r i t h m i cm u l t i p l i e re x a c tp e n a l t yp r o b l w 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 r4 ， 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 ni nm i x e d i n t e g e rp r o g r a m m i n g s e v e r a ls u n c i e n tc o n d i t i o n sa r ep r o p o s e df o rt h ee q u i v a l a n c eo ft h eg l o b a lo p t i m a ls o l u t i o n s b e t w e e nt h ep r i m a lp r o g r a m m i n ga n dp e n a l t yp r o b l e m i na d d i t i o nw ef i n do u t r e l a t i o n s h i pb e t w e e n k k tm u l t i p l i e r sa n dp e n a l t yp a r a m e t e r si nt h ec a s eo fl i n e a r m i x e d i n t e g e rp r o g r a m m i n g k e y w o r d sn o n l i e a rp r o g r a m m i n g ，m u l t i p l i e re x a c tp e n a l t yf u n c t i o n ，k k t m u l t i p l i e r s ，n e w t o nm e t h o d ，m i x e d i n t e g e rp r o g r a m m i n g v 上海大学 本论文经答辩委员会全体委员审 查，确认符合上海大学博士学位论文质 量要求。 嚣贻獬：互氓糊曼如涝 主任：互哲民j 暴掇夏础 颈：愁b 冁爿融 爱蠲琢羹害麓蓉 垫璐b 欲凝澎舀秀 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有j 殴保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名穷握篷日期： 第一章 基本概念及相关结论 1 1 问题的阐述 考虑如下约束非线性规划问题 ( p )m i n ，( z ) s t g i ( x ) 0 ( i = 1 ，2 ，m ) x x 其中，g l , i ：1 ，2 ，m 是定义在册上的非线性连续可微函数， x 是r n 的一个子集，。= ( 钆。，z 。) 丁是n 维向量。 集合 s = z x19 i ( x ) 0 ，i = 1 ，2 ，m ) 表示为问题( p ) 的可行域。s 中的点称为问题( 尸) 的可行点。 设z + s ，若存在z + 的领域 0 ( z + ，占) = 。li lz 一。+ l l o ，i = l ，2 ，t ，n ， 厂( 。) = il 吼( 。) 0 ，则称在x 4 处严格互补松弛条件成立。 定理1 2 1 ( k k t 必要条件，见 1 定理42 1 3 ) 设在问题( p ) 中， 矿为可行点，f ，g i ( i i ( x + ) ) 在z + 可微，g i ( i 芭j ( ) ) 在矿连续， 并且v g i ( x ) ( i ) ) 线性无关 若z + 是局部极小点，则存在圮r ? 使得 v f ( x + ) + a + v g i ( x + ) = 0 i e i ( x + ) 此外g i ( i i ( x ) ) 在z + 也可微，则k k t 条件可写成 m v f ( x 4 ) + nv g i ( x + ) = 0 i = l k 肌( z + ) = 0 ，i = 1 ，2 ，。，m n 0 ，i = 1 ，2 ，一，m 下面，对于凸规划，给出最优解的充分条件。 定理1 2 2 ( 见 1 】定理4 3 8 ) 设，9 i ( i = 1 ，2 ，m ) 在r “上连 续可微，且设，9 ( i = 1 ，2 ，m ) 是凸函数，若在x + 处k k t 必要条 件成立，则矿是全局极小点。 定理1 2 3 ( 二阶充分条件) ( 见 1 定理4 4 2 ) 设在问题( p ) 中， f ，9 。( i = 1 ，2 ，m ) ，在r ”上二次可微，为k k t 点，且w 为 l a g r a n g e 乘子，记 ，+ = i ，( 。+ ) a ： 0 ) ，j o = i ，( z + ) fa ；= 0 l ( x ) 在x + 的h e s s i a n 阵为 v 2 l ( x + ，”) = v 2 s ( x + ) + n v 2 9 i ( x + ) i e i ( x ) 其中v 2 ，( z + ) ，v 2 9 i ( z + ) ( i z ( z + ) ) 分别是f ，9 i ( i = 1 ，2 ，m ) 在x + 的h e s s i a n 阵 3 定义锥 c = 切i v g i ( z ) = 0 ，i i + ，v g ( x ) t p 0 ，i i o ， 于是，v p g ，都有 矿v 2 l ( x ，a + ) p 0 ， 则。+ 为严格的局部极小点。 定理1 2 4 ( 二阶必要条件) 见 1 】定理4 4 3 ) 设在问题( p ) 中， f ，g i ( 江1 ，2 ，m ) ，在形上二次可微，矿为局部极小点，l a g r a 几g e 函数在矿的h e s s z a n 阵为 v 2 三( 矿，a + ) = v 2 ，( 矿) + k v 2 9 i ( z + ) t ，知) 其中v 2 ，( 矿) ，v 2 9 i ( x + ) ，i ，( 矿) 分别是，g ：i ，( 。t ) 在z + 的 h e s s i a n 阵 假定v 2 肌( 矿) ，i j ( 。) 线性无关，则矿为k k t 点，且对v p c ： 如oi 、t g i ( x + ) 0i ，( 矿) 成立p t v 2 l ( x ，a ) p 0 通常对于求解非线性规划问题方法，应当要求它具有有关的收敛性， 而要判断其有效性，除了可以看它是否具有收敛性之外，重要的衡量标 准是它的收敛速度。下面我们将介绍有关的收敛性和敛速的一些定义。 定义1 2 1( 局部收敛性) 设z + 为问题解，存在矿的某领域 o ( ，盯) ，盯 0 ，对初始点x 0 o ( ，由算法产生的点列 z t ， 总成立1 i mz t = z + i - - + 0 0 定义1 2 2 ( 全局收敛性) 设z + 为问题解，对任跏船，由算 法产生的点列 z t ) ，总成立。1 + i m 。z t = 。4 定义1 2 3 ( 局部线性敛速) ) 为由算法产生的点列，z + 为 问题的解，若成立i 卫m z + j scjjz t z + 忆或j ，( z 蚋) 一，) j s cl ，( z k ) 一，( z + ) l ，这里k o ，k o 0 为某正整数，0 c 1 ，则称 点列 z t ) 具局部线性敛速。 4 定义1 2 4 ( 一致线性敛速) 为由算法产生的点列，z + 为 问题的解，若成立l lx k + - 一z + | | cf | z m 一。+ l l ，或lf ( x m ) 一，( z ，) i ci ，( 。k ) ( x 4 ) l ，对所有k = 1 ，2 ，0 0 为常数。 1 3 罚函数方法 考虑问题 m i n ( 5 ) ( p ) s t g i ( x ) 0 ，i = 1 ，2 ，仇( 1 3 1 ) h j ( x ) = 0 ，j = 1 ，2 ，r 罚函数方法的基本思想就是把上述约束问题变换成无约束问题来 求解，采用的方法是在目标函数上加上一个或多个与约束函数有关的函 数，而删去约束条件，在形式上把问题( p ) 变换成如下形式： 讯r q ( z ，a ，肛) = f ( x ) + a k e l y , ( x ) + p 女妒 吗( z ) 1 j ：1= 1 其中，( g ) ，砂( ) 为连续函数，且满足( ) = 0 ，y o 且毋( ) 0 ，y 0 ； 妒( ) = 0 ，= 0 且砂( ) 0 ，y 0 ，而k ，m ，为罚因子，q ( x ，k ，p k ) 称为 罚函数。 若a t = a ，肌= 肛，则变成一个无约束问题；若出现一列儿，“k ， 1 ，2 ，a k ，肌t + 则变成一系列无约束问题。 罚函数法主要分s u m t ( s e q u e n t i a l u 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 s ) 法，增广l a g r a n g e 罚函数法和精确罚函数法三类。它们有一点共同 点就是对不可行点要予以惩罚其惩罚大小体现在罚参数a m ，肌及西( ) ，妒( y ) 5 上。 用罚函数方法来解约束最优化问题通常认为最早由c o u r a n t 在求解 线性规划时提出。后来，c a m p 2 和p i e t r g y k o w s k i 3 讨论了罚函数方法 在解非线性规划问题中的应用。f i a c c o 和m c c o r m i c k 4 【9 在利用罚函数 方法，即序列无约束极小化方法上作了不少工作，并总结为s u m t 方法。 s u m t 法是用形如m i n y ( z ) + 即( z ) 】的序列无约束问题来替代问题 ( 户) ，其中“ 0 称为罚参数，p ( z ) 称为r “上的罚函数它满足： 1 p ( x ) 在r “上连续 2 p ( x ) 0 ，v x 形 3 p ( x ) = 0 充要条件是 z s = zlg i ( z ) 0 ，i = 1 ，2 ，- - ，m ， j ( z ) = o ，j = 1 ，2 ，r 例如对问题( 户) ，下述两函数均是罚函数 p ( x ) = ( 乳( z ) ) + 妒( b ( z ) ) i = 1 j = l m r p ( z ) = m a x ( o ，吼( 。) ) 9 + lh a x ) p ( 1 3 3 ) ( 1 3 4 ) 这里p 为正整数。 一般来说，无约束问题 ( q “) ：罢要，( z ) + 肛p ( z ) ( 1 3 5 ) 随着“的增加，其解必落在p ( z ) 之值很小的一个区域内，亦即 s 附近，因而可设想， 当“_ 。时，问题( 吼) 的解趋于可行域。 设q ( 肛) = i n f f ( x ) + p p ( x ) iz x ，我们有如下结论 6 引理1 3 1( 见 1 】定理9 2 1 )设，g ii = l ，2 ，m ，h j ，j = 1 ，2 ，r 为r “上的连续函数，x 为r “中一个非空集合，设p ( x ) 由 ( 1 3 3 ) 定义的连续函数，如果对任何p 0 ，存在一点x 。x ，使得 q ( p ) = f ( x ，) + p p ( z 口) = i n ， ，( z ) + u p ( x ) ：x x ) ， 那么下述结论成立： 1 i n f f ( x ) l9 ；( z ) 0 ，i = 1 ，2 ，m ，h j ( x ) = 0 ，j = 1 ，2 ，。，r ，z x s u p q ( p ) ； “2 0 2 ，( ) 是关于芦的单调不减函数，q ( ) 关于弘的单调不减函 数，p ( z 。) 是关于肛的单调不增函数。 定理1 3 1 ( 见 1 定理6 2 4 ) 设f ，g ii = 1 ，2 ，m ，b ，j = 1 ，2 ，r 为印上的连续函数，x 为钟中的非空集合，设问题( 户) 至少有一 个可行解，p ( x ) 为由( 1 3 3 ) 定义的连续函数，如果对任何肛0 ，存 在一点吼x ，使得 q ( 弘) = f ( x p ) + 肛p ( z ，) = i n f f ( x ) + 即扛) ：x x ， 而且 ) 也包含于x 中的一个紧子集，那么成立 解。 1 i n f f ( x ) g i ( x ) s0 ，i = 1 ，2 ，一，m ，h j ( z ) = o ，j = 1 ，2 ，一，r ，zex ) = s u p q ( p ) “0 = 。q ( 弘) ； 2 的任何收敛子列的极限点是原问题( p ) 的一个最优解； 3 。+ l i m + 。p p ( x “) = 0 显然，如果对某个p 成立p ( x 。) = 0 ，那么是原问题户的最优 从定理1 3 t 得知，当取罚函数p 充分大时，问题( q 。) 的最优 解可以任意逼近原问题( 户) 的最优解，但是，如当肛很大时， 7 y ( x 。) + 肛p ( ) 的h e s s i a n 阵趋于病态而导致计算困难，因此当用无约束 优化方法来解m i n f ( z ) + t t p ( z ) 时，运用有些算法如n e w t o n 法，其收敛 速度很慢，引用s u m t 方法来解原问题所需的计算量是比较大的。因此 产生了求解约束非线性规划的一些改进的罚函数方法 与传统的罚函数( 1 3 3 ) 不同， 性规划问题( p ) 的指数型罚函数， 在文【1 1 】中亦讨论了不等式约束非线 其形式如下； 必荆三m ) 押矧e e 印 m ( z ) r 】，r o 称z 一为二( z ) 的“一极小解，若满足下述不等式： 氏( z 0 ，而“ 0 为罚参数 它得到下述s e 近似解的结论。 定理1 3 。2 ( 见文 1 1 】命题2 1 ) 假定函数，( z ) ，g i ( z ) ，i = 1 ，2 ，m 是 连续的且，下有界。令茁k 舒是允的t 一极小解，这里k 0 ，仉 0 都趋于0 ，则点列 ) ) 的任一极限点矿皆为原问题的全局解。此外 若存在卵 0 ，成立 删嬲如m ) = + 则点列 0 ，对所有z ，而当z 芒s ，r 0 时，p ( z ，r ) 随着r 0 减小而增大，且对同样r 0 ，z 乏s 的不可行程度越严 重，则p ( z ，r ) 值越大。这一指数型罚函数l ( x ) 是简单的、光滑的，但 仍然不是精确的。因为仅当r 七l0 时，若。收敛于z t ，则z 为原 问题的全局解，因此仍是序列的。 定理1 3 3 ( 见文【1 1 定理3 1 ) 设f ( z ) ，肌( z ) 在问题( p ) 的最优解 z 。的某个邻域内二次连续可微，如果在矿处满足严格互补和二阶最 优性条件，则方程组 m v ，( z ) + e x p m ( 。) r 】v 玑( 窖) = z = 1 8 在( 0 ，0 ) 附近关于( n ) 定义了一个连续可微隐函数x ( r ，) ，其中r 0 并满足 蛾。z ( r ，f ) = z + 此外，a i ( r ，) = e x p q ( 。( r ，f ) ) r 是连续可微函数，并满足 l i m - - * 0 “o 九( r ， ) = 茁 ，f 1 0 、。 并且当( r ，) 趋于( 0 , 0 ) 时，。( r ，) 和a ( r ，) 的导数有极限，还对所有充分 小r ，点x ，= z ( r ，0 ) 是 的严格局部极小点。 在介绍了一个外插算法后，文章又给出了如下结论 定理1 3 4 ( 见文【1 1 】定理j 1 ) 设氩+ ，是经第“次迭代后得到的 外插点，对罚参数n + 。首次迭代的牛顿方向e 满足 i | e nl 卜o ( r ：) 此外，如果z 各。表示首次牛顿迭代后得到的点，则有 m jv ，( z 盘。) + e x p 旧( x 州n ) r 州】v 吼( z 群，) 卜o ( r 玉。) t = 1 1 4 精确罚函数方法 考虑问题 r a i n ，( z ) ( p )s t 9 i ( x ) 墨0 ，i = 1 ，2 ，m x xcr “ 精确罚函数是用形如m i n 。x ，( z ) + p e ( z ) 的无约束问题( b ) 来替 代问题( p ) ，其中“为参数，e ( x ) 为x _ r 上的函数且满足 1 e 扛) 0 ，地x 2 e ( z ) = 0 的充要条件是。s 9 这里 s = zf 肌( z ) 0 ，i = 1 ，2 ，- 一，槐，z x 定义1 4 1 若存在弘o 0 ，当“时使得问题( 只) 的解是问 题( p ) 的解，或问题( p ) 的解是( o ) 的解， 则称 ，( ) + , u e ( x ，) 为问题( p ) 的精确罚函数。这里解可以是局部最优解，也可以是全 局最优解。 精确罚函数概念首先由e r e m i nf 1 2 和z a n g w i l l 1 3 于上世纪六十年代 后期提出。这是线性规划中大m 法在非线性规划中的自然推广。从那时 起，精确罚函数一直在数学规划理论与方法中扮演很重要的角色。 1 4 一 3 6 】 下面我们介绍发展最为成熟的z - 精确罚函数方法的主要理论结 果，设原问题( p ) 中集合x 为开集，令( 1 3 4 ) 中p = 1 ，得罚问题 m r ( r )m i n 。e x ，( 。) + “( m a x o ，肌( 茁) ) + 1 ( 。) 1 ) i = lj = l 称 m r p i ( z ，弘) = ，( z ) - 4 - p ( em a x o ，夕i ( z ) ) + e 1h a x ) j ) l = l j = l 为f 。精确罚函数，f ，精确罚函数又称为经典精确罚函数。 定理1 4 1 ( 见文 1 定理9 3 1 ) 设z + 为问题( p ) 的k k - t 点，( 札+ ，u + ) 为与矿相应的k k t 乘子，进一步， 设，( z ) ，吼( z ) ，i i o ( x + ) = i1g i ( x 4 ) = 0 ，i = 1 ，2 ，m 是凸函数，而 且如( z ) ，j = l ，2 ，r 是仿射函数，则对p 2m o z 成，i 凡( ) ，l ”；l ，j = 1 ，2 ，r ) ，z + 也是问题( q ) 的解。 定理1 4 2 ( 见文 2 7 定理4 4 ) 设。4 为问题( p ) 的一个严格局部极 小点，( z ) ，肌( 。) ，i = 1 ，2 ，m ，h i ( z ) ，j = 1 ，2 ，r 在。8 的一个领 域内连续可微，进一步，设z + 满足m