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

摘要 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一 门独立的学科还是在上世纪4 0 年代末d a n t z i n g 在1 9 4 7 年提出求解一般线性规 划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技 术的巨大发展，至今短短的几十年，它得到了迅猛的发展现在，解线性规划、非 线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种 最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等 方面得到了广泛的应用，成为一门十分活跃的学科 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域求解约束 非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方 法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法罚函数方法 通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时， 求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为 精确罚函数，否则称为序列罚函数针对传统罚函数的定义而言，若罚函数是简 单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不 光滑的：若罚函数是精确的、光滑的，则它一定是复杂的因此我们的工作是对传 统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后 的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结果我 们把这类罚函数称为简单光滑乘子精确罚函数所谓简单的，即罚函数中包含原 问题中的目标函数和约束函数而不包含它们的梯度，若罚函数中包含有原问题中 目标函数和约束函数的梯度，则称为是复杂的 本论文共五章：第一章，简要介绍了目前国内外关于罚函数、精确罚函数、 乘子精确罚函数的研究工作；第二章提出一种带有指数、对数性质的乘子罚函数； 第三章则对前一章提出的方法，给出一个算法并进行了一定的数值试验，取得了 较好的计算效果；第四章介绍一种光滑的近似精确罚函数，从理论上证明它的近 似精确性，为进一步研究打下了基础；最后一章则对近似精确罚函数给出一个相 1 应的算法，并进行了一定的数值试验。 关键词：非线性规划，罚函数，全局最优解，光滑近似精确罚函数 i i a b s tr 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 s f o rs 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 o u n 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 p e n a l t yf u n c t i o nm e t h o d sa n d l a g r a n g i a nd u a l i t ym e t h o d sa r et h et w op 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 tt h e t 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 gp 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 f e a c hm i m m u mo ft h ep e n a l t yp 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 d p r o g r a m m i n gp 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 t p e n a l t yf u n c t i o n i nt h i st h e s i s ，w ef i r s tg i v es o m ep e n a l t yf u n c t i o n ，a n dt h e n w ed i s c u s st h eg l o b a le x a c ta n da p p r o x i m a t i v e l ye x a c tp e n a l t yp r o p e r t yo fe x a c t p e n a l t yf u n c t i o n s ，w ea l s od i s c u s ss m o o t h i n go fe x a c tp e n a l t yf u n c t i o n s g l o b a lo p t i m i z a t i o np r o b l e m sa b o u n di ne 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 s ，c 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 l l - 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 , a n de n v i r o n m e n t a le n g i n e e r i n g s i n c et h e r ee x i s tm u l t i p l el o c a lo p t i m at h a td i f f e rf r o mt h eg l o b a ls o l u t i o n ，a n d t h et r a d i t i o n a lm i n i m i z a t i o nt e c h n i q u e sf o rn o n l i n e a rp r o g r a m m i n ga r ed e v i s e d f o ro b t a i n i n gl o c a lo p t i m a ls o l u t i o n ，h o wt oo b t a i nt h eg l o b a l l yo p t i m a ls o l u t i o n s i sv e r yi m p o r t a n tt o p i c i nt h i st h e s i s ，w ea l s od i s c u s st h ef i l l e df u n c t i o nm e t h o d s f o rg l o b a lo p t i m i z a t i o na n dg i v ean e wf i l l e df u n c t i o n t h i sp a p e rm a i n l yc o n s i s t so ff i v ec h a p t e r s i nt h ef i r s tc h a p t e r ，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 k o np e n a l t yf u n c t i o n s i nt h es e c o n da n dt h i r dc h a p t e r ，w eg i v ea nm u l t i p l i e rp e n a l t yf u n c t i o na n d d i s c u s si t sp r o p e r t i e s b a s e do nt h ep e n a l t yf u n c t i o n ，a na l g o r i t h mi sg i v e n i nt h el a s tt w oc h a p t e r ，w eg i v eak i n do fs m o o t h i n ga n da p p r o x i m a t i v e l y e x a c tp e n a l t yf u n c t i o n si sg i v e n ，a n di t sa p p r o x i m a t i v e l ye x a c tp r o p e r t yi sp r o v e d f i n a l l ya na l g o r i t h mi sg i v e n 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 ，p e n a l t yf u n c t i o n ，g l o b a lo p t i m i z a t i o n ， s m o o t h i n ga n da p p r o x i m a t i v e l ye x a c tp e n a l t yf u n c t i o n s i i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 扯魄胆 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：拯导师签名：圣圭! 刍三日期尸z ：墅：兰 上海大学硕上学位论文 第一章基础知识及相关结论 1 1 基础知识 最优化问题是研究最优解的性质和算法的- - i - j 应用性很强的学科，最优化问 题的一般形式是： m i n f ( x ) s t x s ( 1 1 1 ) 其中s = z 舒：g i ( x ) 0 ，i = 1 ，2 ，p ) ，称s 为可行域，f ( x ) ：留_ r ， 称，( z ) 为目标函数。 因为m a x f ( x ) ：x s ) = 一m i n - f ( x ) ：z s ) ，所以最大化问题包含在 上面模型中。进而，由于g i ( x ) 20 等价于- - g i ( x ) 0 ，g i ( x ) = 0 等价于g i ( x ) 0 和一g i ( x ) 0 ，我们看到( 1 1 1 ) 包含了许多其它类型的约束。 如果可行域是整个n 维欧氏空间，那么下述问题称为无约束最优化问题： m i n f ( x )( 1 1 2 ) s t x 俨 如果s 是一个多面体时，称问题( 1 1 1 ) 是线性约束的；此外，若目标函数也是线 性的，该问题称为线性规划问题。当( 1 1 1 ) 中出现的函数至少有一个是非线性的， 该问题称为非线性规划问题。当目标函数，和每个约束函数g i 都是凸的时候， 问题( 1 1 1 ) 称为凸规划问题。有时，当，是凸函数，s 是凸集时，问题( 1 1 1 ) 也 称为凸规划。 在本文中，为了方便统称问题( 1 1 1 ) 和i h - j 题( 1 1 2 ) 为原问题。如果不加特别 说明i | 1 i 始终表示欧几里得范数；v ，( z ) 表示f ( x ) 在点z 处的梯度；v 2 f ( x ) 表示f ( x ) 在点x 处的h e s s e 矩阵。 定义1 1 1 点o + s 称为一个局部极小点，如果存在某个e 0 ，对于所 有满足l i x z + l | 的x s ，成立，( 矿) ，( z ) ，而，( 矿) 称为局部极小值 1 上海人学硕士学位论文 定义1 1 2 矿s 称为一个全局极小点，如果对于所有z s ，成立 f i x + ) ，( z ) ，而，( 矿) 称为全局极小值。 在无约束全局最优化问题中，凸规划具有很好的性质，也就是当目标函数是 凸的，可行域也是凸的时候，凸规划的每个局部极小点就是全局极小点，所以我 们可以应用求局部极小点的方法，求得全局极小点，已有的局部极小化算法对它 都是有效的。而对于非凸的、有约束问题在求解局部极小点时都会变得很困难， 因此求解全局极小点就更加困难。这样就使我们在求解全局最优化问题时面临 很多困难，所以我们首先要研究目标函数在可行域s 上的局部和整体性质。 1 2 罚函数方法 考虑问题 r a i nf i x ) ( 户) s t 吼( z ) o ， = 1 ，2 ，m1 1 2 1 ) ( z ) = 0 ，j = 1 ，2 ，r ， z x 其中xc 舻 罚函数方法的基本思想就是把上述约束问题变换成无约束问题来求解，采用 的方法是在目标函数上加上一个或多个与约束函数有关的函数，而删去约束条 件，在形式上把问题( p ) 变换成如下形式： q ( x ，k ，p 七) = m ) + k 池( z ) 】+ 肌砂 ( z ) 】 1 1 2 2 ) j = l j = l 其中，咖( 可) ，妒( 可) 为连续函数，且满足( 可) = 0 ，y 0 且咖( ) 0 ，可 0 ； 妒( ) ；0 ，秒= 0 且妒( 可) 0 ，y 0 ，而入南，p 七，为罚因子，q ( x ，儿，肛詹) 称为罚 函数 若入七= a ，肌= p ，则是一个无约束问题；若出现一列入七，肌，k = 1 ，2 ，k ， 舰t + 。则是一系列无约束问题 罚函数法主要分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 s ) 法， 增广l a g r a n g e 罚函数法和精确罚函数法三类它们有一点共同点就是对不可行点 2 上海大学硕士学位论文 要予以惩罚其惩罚大小体现在罚参数入七，肌及咖( 夕) ，妒( y ) 上 用罚函数方法来解约束最优化问题通常认为最早由c o u r a n t 在求解线性规 划时提出。后来，c a m p 4 5 】和p i e t r 盱k o w s l 【i 4 4 】讨论了罚函数方法在解非线性规 划问题中的应用。f i a c c o 和m c c o r m i c k 1 一 6 1 在利用罚函数方法，即序列无约束极 小化方法上作了不少工作，并总结为s u m t 方法 s u m t 法是用形如m i n 【厂( z ) + 卯( z ) 】的序列无约束问题来替代问题( 户) ，其 中肛 0 称为罚参数，p ( x ) 称为舻上的罚函数它满足： 1 p ( z ) 在形上连续； 2 p ( x ) 0 ，比r n ； 3 p ( x ) = 0 充要条件是 z s = 【zg i ( x ) 0 ，i = 1 ，2 ，m ，0 ( z ) = o ，j = 1 ，2 ，7 ) 例如对问题( 户) ，下述两函数均是罚函数 m p ( 。) = 砂( 吼( z ) ) + 矽( 乃( z ) ) ( 1 2 3 ) p ( z ) = i m a m ( 0 ，g t ( z ) ) 】p + ih i ( x ) i p ( 1 2 4 ) i = 1 j = l 这里p 为正整数 一般来说，无约束问题 ( q p ) ： m z i x n ，( z ) + p 尸( z ) ( 1 2 5 ) 随着弘的增加，其解必落在p ( x ) 之值很小的一个区域内，亦即s 附近，因而可 设想，当p 0 0 时，问题( q p ) 的解趋于可行域 设q ( p ) = i n f f ( x ) + p p ( z ) lz x ) ，我们有如下结论： 引理1 2 1 ( 见【1 1 】定理9 2 1 ) 设，吼i = 1 ，2 ，m ，歹= 1 ，2 ，r 为舒上的连续函数，x 为舻中一个非空闭箱，设p ) 由( 1 2 3 ) 定义的连续函 3u 上海入学硕士学位论文 数，如果对任何肛0 ，存在一点x ，使得 q ( p ) = f ( x p ) + 弘尸( z p ) = i n f f ( x ) 4 - g p ( z ) ：z x ， 那么下述结论成立： 1 i n f ，( z ) i 吼( z ) 0 ，i = 1 ，m ，o ( z ) = 0 ，j = 1 ，r ，z x ) s u p q ( p ) ； p 2 0 2 i ( x p ) 是关于肛的单调不减函数，q ( p ) 关于p 的单调不减函数，p ( x 肛) 是 关于肛的单调不增函数。 定理1 2 1 ( 见【1 1 】定理6 2 4 ) 设，吼i = 1 ，2 ，m ，乃，j = 1 ，2 ，r 为i p 上的连续函数，x 为钟中的非空闭箱，设问题( 户) 至少有一个可行 解，p ( z ) 为由( 1 2 3 ) 定义的连续函数，如果对任何肛0 ，存在一点钆x ， 使得 q ( p ) = f ( x p ) + p p ( z p ) = i n f f ( x ) + t t p ( x ) ：z x ) ， 而且 ) 也包含于x 中的一个紧子集，那么成立 1 i n f f ( x ) i 夕 ( z ) 0 ，i = 1 ，m ，h e ( x ) = 0 ，歹= l ，r ，z x ) = s u p q ( 肛) p 2 0 一i l i r a q ( p ) ； “+ 十。o 2 0 为罚参数 它得到下述近似解的结论 定理1 2 2 ( 见文 7 6 j 命题2 1 ) 假定函数i ( x ) ，g i ( x ) ，i = 1 ，2 ，m 是连续 的且，下有界。令x k 舻是氏的鼠一极小解，这里“0 ，吼 0 都趋 于o ，则点列 ( 钆) ) 的任一极限点z + 皆为原问题的全局解此外若存在7 7 0 ， 成立 l i r a l l 圳i 一” 口t ( z ) s 叼 则点列 ( 钆) ) 的极限点一定存在 i ( x ) = + o o m 很显然，对于上述指数型罚函数 ( z ) = i ( x ) + r e x p 【仇( z ) r 】= i = l i ( x ) + r p ( x ，7 ) ，其中p ( x ，7 ) 0 ，对所有z ，而当茁之s ，7 0 时，p ( z ，r ) 随 着7 0 减小而增大，且对同样7 0 ，z 乏s 的不可行程度越严重，则p ( x ，r ) 值 越大这一指数型罚函数 p ) 是简单的、光滑的，但仍然不是精确的因为仅 当【0 时，若钆收敛于z + ，则矿为原问题的全局解，因此仍是序列的 定理1 2 3 ( 见文【7 6 】定理3 1 ) 设i ( x ) ，仇( z ) 在问题( p ) 的最优解z + 的某个 5 0r r z 吼唧 m 两 r + z ，j 三z g 舻m 蚝 上海人学硕士学位论文 邻域内二次连续可微，如果在z + 处满足严格互补和二阶最优性条件，则方程组 v ( x ) + e x p 【g , ( z ) r1v 吼( z ) = t = 1 在( o ，o ) 附近关于( n ) 定义了一个连续可微隐函数x ( r ，) ，其中7 0 ，并满足 ! i m x ( r ，) = 矿 f 一0 r 1 0 此外，凡( r ，毒) = e x p 【q ( z ( r ，) ) 叫是连续可微函数，并满足 e 姆l 。九( r ，) = k 并且当( r ，) 趋于( o ，o ) 时，z ( r ，) 和a ( 7 ，) 的导数有极限，还对所有充分小7 ，点研= x ( r ，0 ) 是矗的严格局部极小点。 在介绍了一个外插算法后，文章又给出了如下结论 定理1 2 4 ( 见文【7 6 】定理5 1 ) 设圣七+ 1 是经第九次迭代后得到的外插点，对 罚参数r + l 首次迭代的牛顿方向e 满足 i ie n 卜o ( r 2 ) 此外，如果z 益。表示首次牛顿迭代后得到的点，则有 1 3 精确罚函数方法 考虑问题 r a i nf ( x ) ( p ) s t g i ( x ) 0 ，i = l ，2 ，m z xc 形 l d ( r 2 r 玉。) 精确罚函数是用形如m z i x n i f ( z ) + p e ( z ) 】的无约束问题( 兄) 来替代问题( p ) ， 其中p 为参数，e ( z ) 为x r 上的函数且满足： 6 j抖 吼v他d p 吼p 畎 m 谢 + p ，j v 上海大学硕士学位论文 1 e ( x ) 0 ，比x 2 e ( x ) = 0 的充要条件是z s ， 这里 s = zg i ( x ) 0 ，i = 1 ，2 ，m ，z x ) 定义1 3 1 若存在肋 0 ，当p2 肛。时使得问题( 兄) 的解是问题( p ) 的 解，或问题( p ) 的解是( r ) 的解， 则称 f ( x p ) + g e ( z p ) 为问题( p ) 的精确罚函数。这里解可以是局部最优解，也可以是全局最优解。 精确罚函数概念首先由e r e m i n 3 9 和z a n g w i l l 【8 7 t - _ l = t 蚬六十年代后期提 出。这是线性规划中大m 法在非线性规划中的自然推广。从那时起，精确罚函数 一直在数学规划理论与方法中扮演很重要的角色。下面我们介绍发展最为成熟 的z l 精确罚函数方法的主要理论结果： 设原问题( p ) d p 集合x 为开集，令( 1 2 4 ) 中p = 1 ，得罚问题 ( r ) m 剌i n m ) + 肛( m a x o ，g i ( z ) ) + i = 1 j = l h j ( x ) i ) 称 p l ( x ，p ) = ，( z ) + p ( m a x 0 ，吼( z ) ) + ih i ( z ) i ) i - - - - i j = l 为z 1 精确罚函数，z l 精确罚函数又称为经典精确罚函数 定理1 3 1 ( 见文【1 1 】定理9 3 1 ) 设z + 为问题( p ) 的k k t 点，( u ，u + ) 为 与x + 相应的k - k t 乘子，进一步，设f ( x ) ，g i ( x ) ，i i o ( x ) = ig i ( x + ) = 0 ，i = 1 ，2 ，m ) 是凸函数，而且h j ( x ) ，j = 1 ，2 ，r 是仿射函数，则 对p m a x 成，i o ( x + ) ，i 哆i ，j = 1 ，2 ，7 ) ，z + 也是问题( 咒) 的解 定理1 3 2 ( 见文 8 6 】定理4 4 ) 设矿为问题( p ) 的一个严格局部极小点，0 ) ， 吼( z ) ，i = 1 ，m ，h i ( x ) ，歹= 1 ，r 在矿的一个领域内连续可微，进一步， 7 上海大学硕上学位论文 设z + 满足m a n g a s a r i a n f r o m o v i t z 约束品性，那么存在“+ ，使得“旷，z 是问题( 冠) 的局部极小点 定理1 3 3 ( 见文 8 6 】定理4 6 ) 设命题1 2 3 的条件成立，则对任何满足p m a x 成，i 1 0 ( x ) ，l 丐l ，j = 1 ，2 ，r ) ，的罚参数p ，矿是罚问 题( 兑) 的严格局部极小点。 在算法方面，尽管使用精确罚函数的历史已经很长，由于已经证明在传统罚 函数定义下，若罚函数是简单的、光滑的，则一定是不精确的，这里所谓简单的 表示罚函数表达式中只含目标函数和约束函数。考虑问题 ( p ) m i n 弛) = 一z s t g ( x ) = z 一1 0 ， 相应的罚问题 ( 兄)m i n q ( x ，p ) = 一z + pm a x ( o ，( z 一1 ) ) 2 当z 乏s 时，令q 7 ( z ，肛) = 0 ，得z = 瓦1 + 1 从而可知肛_ ，z = 1 为问 题( p ) 是最优解，显然所给出的罚函数是可微的，但不是精确的。长期来一直存 在着争论，争论的根源在于精确罚函数的不可微性。从算法的角度来看，这种不 可微性能够引起所谓的”m a r a t o s 效应”，即引起阻止快速局部收敛的现象，为了 克服这一效应，人们发展了所谓的”w a t c h i n gd o gt e c h n i q u e ” 7 9 和”s e c o n d o r d e r c o r r e c t i o nt e c h n i q u e s ” 8 0 一【8 2 】 另外，一些学者引入了与上述精确罚函数完全不同类的可微精确罚函数【2 l 卜 【2 8 】。这类可微精确罚函数由于其表达式包含有目标函数及约束函数的梯度，方法 大大地限制了其实际应用，从上世纪九十年代后期开始非线性精确罚函数【2 9 】_ 【? 】 得到了较广泛的研究，同时对精确罚函数进行了修正，非线性精确罚函数【2 9 卜 【? 】和低次罚函数【? 】【? 】开辟了关于精确罚函数的新的研究领域，至今不断有新 的研究成果问世。 而对于传统罚函数，若罚问题是简单的、精确的，则一定的非光滑的。如 q ( z ，a ，p ) = ，( z ) + a m 。z ( o ，吼( z ) ) + p i 吻( z ) i ，入 0 i = 1 j = x 8 上海大学硕上学位论文 若罚问题是精确的、光滑的，则罚问题的表达式一定包含有f ( z ) ，吼( z ) ，( z ) 的 梯度。如对只含不等式约束问题( p ) ，其罚函数为 q ( x ，入，o r ) = y ( x ) + a ( z ) t g ( x ) ( 1 3 1 ) = y ( x ) + a ( z ) + v ，( z ) 夕( z ) + 昙( a + ) 9 ( z ) t ) ( a + ( z ) 夕( z ) ) ， ( 1 3 2 ) 其中仃 0 ，a ( x ) a ( x ) = v f ( z ) ，a ( x ) = v g ( x ) ，a + ) 表示矩阵a ( x ) 的广义 逆这里q ( z ，入，盯) 的表达式中包有，( z ) ，仇( z ) 的梯度，这种表达式就变得复杂了 鉴于上述情况，我们考虑对传统罚函数的定义进行改变，改变后的罚函数 定义为z s 兮p ( z ) 0 ，甚至于p ( x ) 0 且远大于 当z s 时，p ( z ) 的值按照这种改变，下一节我们将介绍和讨论简单光滑乘子 精确罚函数的现状及我们所得到的某些结果 1 4 乘子精确罚函数方法 文 3 4 】构造一个改进的指数型乘子罚函数，从而分析了极小化凸规划问题的 乘子指数型方法以及对偶情况，并给出了一种熵极小化算法，而且强化了方法的 有效收敛结果，在应用到线性问题时，给出了其收敛速度，以下对这一途径作一 简单介绍，参文【3 4 考虑非线性规划问题： m i n y ( x ) s t g i ( x ) 0 ，i ；1 ，2 ，m 假使( 1 4 1 ) 的最优解集非空且有界， zi ，( z ) 0 其算法由下两式给出 i = l m 南 矿口加肿r a i n ，( 卅萎篝矽( c ；删) ) ( 1 4 2 ) 9 上海大学硕士学位论文 砖+ 1 = 蟛ke c ；9 j ( 妒) ，j = 1 ，2 ，m ( 1 4 3 ) 其中心 0 是相当于第j 个约束的乘子，勺 0 是罚参数。此外当，g i 为凸 函数时，而相应的对偶问题为 m a xd ( # ) ( 1 4 4 ) “7 u 、 其中 d ( p ) = 婴鬻 ，( z ) + 如仍 ) ) ( 1 4 5 ) j = l 由此给出了熵极小化算法 一 。k + l a r 9m 删a x 如) 一妻j = l 钞k 卷) ) 这里妒+ 是矽的共轭函数，它是一个熵函数： 且有如下k k t 最优性条件 及 矽( s ) = si n8 8 + 1 0 ad ( p 七+ 1 ) 一 v 妒+ ( 钟“瞄) 砖 v 矽+ ( p 1 ，n 蠡+ 1 p 麓) c ( 1 4 6 ) ( 1 4 7 ) 对凸规划问题，文【3 4 】给出了算法的收敛性分析，现介绍有关主要性质。由 于其证明十分复杂，这里从略 设g ( u ，v ) = ul n ( u v ) 一心+ v ，( u ，口) 【0 ，) x ( 0 ，+ o 。) ，利用公式 砂+ ( s ) = 8i n8 8 + 1 ， 可得g ( 钆，口) = 妒( u ) u 这样( 1 4 6 ) 重新写成 矿“= a r g 搿一萎巧1q ( 酬挑 p ，vo 1 0 z 拗 + 瞄 m 触 + z ，j a0 上海大学硕士学位论文 记 其中 d ( a ，芦) = q ( a j ，膨) ， ( 入，p ) o ，) m ( o ，+ 。) m ， j = i m 。= p 【0 ，o 。) mid ( 肛) d 0 。) 因此给出了以下一些性质： d = 。l i md ( 旷) 庀 性质1 4 1 ：( 见文 3 4 】引理3 1 ) v 豇m ，序列 d ( 皿，矿) ) 是单调非增的 且 肛) 收敛 性质1 4 2 ：( 见文 3 4 引理3 2 ) ( a ) d ( p 七) d ( p 七+ 1 ) ，+ ，v k 成立 ( 6 ) vj ，谚妒( u 南乃( z 七) ) u 七一砖缈( z 奄) _ 0 ( c ) vj ，瞄仍( 矿) _ 0 ( d ) d ( 旷) 一l ( x 2 ) 一0 性质1 4 3 ：( 见文 3 4 】引理3 3 ) 若令矿= 型夸乏等，则有 1 i ms u p 乃( 矿) 0 ，j = 1 ，2 ，m 糟。o 性质1 4 4 ：( 见文【3 4 】命题3 1 ) 设 p 2 ) 是由( 1 4 2 ) 和( 1 4 3 ) 产生的序列，且罚 参数满足弓= ，o 0 ，vk ，则 p ) 收敛于对偶问题( 1 4 4 ) 的最优解， 此外，序列 可知) 有界且其每一个聚点是原问题( 1 4 1 ) 的最优解 性质1 4 5 ：( 见文 3 4 】命题4 2 ) 设 p ) 是由( 1 4 2 ) 和( 1 4 3 ) 产生的序列，罚参 数由弓= c 时，vk ，这里常数c 0 ，假定 矿) 收敛于m 中的点，则 肛k ) 至 少是二次收敛的 1 1 上海大学硕上学位论文 1 1 精确罚函数在那些使得对某个i 1 ，2 ，m ) 成立夕i ( z ) = 0 的z 处 不可微，而非线性规划中大部分效果较好的算法都要求目标函数具有可微性，从 而促使) k i y - 2 思, 考罚函数的光滑化【3 5 】，【3 6 ，【3 7 文 3 7 】p i n a r 并i l z e n i o s 针对凸 规划问题提出了对f 1 精确罚函数的二次函数光滑逼近，并证明了通过解光滑 后的罚问题，可以得到可行和雕近似全局极小点，这里p 是常数。此外， 在1 9 9 9 年，d g o l d f a r b 和r p o l y a k 等在文【3 8 】“am o d i f i e db a r r i e r - a u g m e n t e d l a g r a n g i a nm e t h o df o rc o n s t r a i n e dm i n i m i z a t i o n ”中针对问题( 1 2 1 ) 给出下述形 式的修正障碍一增广l a g r a n g i a n 函数。 l 弛) 一 u ti n ( 1 一k g i ( x ) ) 脚垆 一壹喇卅鲁壹蜘) ，z 溉q 知 l 。：2 1 2 1 z ；凡亡q 七 其中q 岛= zi 吼( z ) i 1 ，i = 1 ，2 ，m ) i = zlg i ( x + ) = o ) = 1 ，2 ，f ) ， 矿是问题( 1 2 1 ) 的严格局部极小点，则有下述主要收敛结果： 定理1 4 1 ( 见【3 8 】定理5 1 ) 假定对问题( 1 2 1 ) 在严格局部极小点矿处满足 第二阶最优性充分条件，则存在 0 ，j 0 ) 使得对任何 ( u ，v ，k ) = ( ，) d ( u + ，6 ，知o ) = ( u ，尼) = ( u ，u ，k ) i | iu u + l l 6 尼，u q ) 0 ，u ( m 1 ) 0 ，k k o ， i i ul l 有界，有： ( 1 ) f ( x ，u ，v ，七) 在z + 的某一开球内有唯一极小点岔= 圣( u ，v ，k ) ( 2 ) 对( 2 ，五，西) ：碗= u ( 1 一七吼( 盒) ) ，i = l ，2 ，m ，略= 一七b ( 圣) ，j = l ，2 ，r 成立 1 2 z b吻 ，同 +z 吼 毗 m ：l +z ， = ”uzl 汜 上海大学硕士学位论文 i i 仝一z + l l 云| lu u + | l ，l i 2 j u + j l 云i iu u o 几 其中 ( ：j = ( 包，移) 和c 0 与k 无关 定理1 4 2 ( 见【3 8 】定理5 2 ) 假定对问题( 1 2 1 ) 在全局最优解矿满足第二阶 充分条件并假定存在k o 0 使得对所有固定u 0 和v 及所有有限数q ，水平 集k ( “， ，k o ) = z 酽if ( x ，仳，口，k o ) 口) 为有界集，则当 0 充分大 使得对任何( u ，v ，k ) d + ，仃，k o ) 定f i l l 5 1 中的点仝是f ( x ，u ，u ，k ) 的全局最 优解。 下面我们将给出关于指数型及对数型两类乘子精确罚函数的新形式，并讨 论某些相关的结论。若在问题( p ) 中，xct p 为有界闭箱，( z ) ，吼( z ) ，i = 1 ，2 ，m 为光滑函数，则相应的指数型及对数型乘子精确罚函数分别表示为： 1 指数犁 r a i n q ( x ，a ，p ) q 札x x 三，( z ) + 去喜e k 埘“甸 其中p 0 为罚参数，而九0 ，i = 1 ，m ，与原问题乘子有关的参数 2 对数型 m i n q ( z ，a ，肛) q a p x x = ，( z ) 一去喜l n ( 1 - a i 肛g i ( z ) ) 或 m i n q ( z ，a ，肛) 了a p x x = ，( z ) 一去喜a t f 礼( 1 一p 吼( z ) ) 其中弘 0 为罚参数，而九0 ，i = 1 ，m ，为与原问题乘子有关的参数 我们讨论了g ( p ) 、l ( p ) 与g ( q a 肛) 、l ( q a 肛) 之间的关系，发现凡0 ，i = 1 ，2 ，m 与原问题( p ) 的乘子有着密切的联系，从而我们称它们为简单光滑乘 上海大学硕士学位论文 子精确罚函数。 特别需要指出的是在求解某类凸规划时，我们运用上述形式的乘子精确罚函 数，用牛顿法求解时，效果很好，具一致全局线性收敛性和局部二次收敛性 1 4 上海火学硕士学位论文 第二章指数一对数型罚函数 2 1 引言 考虑约束非线性规划问题 ( p )m i n ，( z ) ，x s 其中s = z x ig i 0 ，i = 1 ，m ) ，这里j i mf ( x ) = + 。，( z ) ，吼( z ) ，i = i i z l l _ - t - o o 1 ，m 为两次连续可微函数 记l ( p ) ，g ( 尸) 分别为问题( p ) 的局部极小点和全局极小点的集合，且g ( p ) c i n t x ，x r n 为一个大的有界闭集。 本文研究和探讨的问题是用罚函数方法来寻求问题( p ) 的局部极小点和全局 极小点关系，而对传统罚函数而言，当参数充分大时，相应罚问题的最优解可任 意逼近原问题的最优解。但当罚参数很大时，其罚函数的h e s s i a n 阵可能会趋于 病态，而导致计算困难【1 】o 因此产生了求解约束非线性规划的一些改进的罚函数 方法 文【7 6 】讨论了不等式的约束非线性规划( p ) 的指数型罚函数，它是一种改变定 义后的序列近似罚函数，其形式如下 m i n f r ( h 。) + r 喜唧协 ) 吨。o 针对问题( p ) ，文 3 4 提出了与原问题乘子有关的乘子罚函数问题，使得定义 的精确罚函数为 m ) + 圭胁( e x p ( c g i ( z ) 卜1 ) ，c 0 ，胁 0 。i = l 1 5 上海人学硕士学位论文 并给出相应的算法和收敛性等有关结论，文 3 8 】具体构造了变形障碍一增广乘子 罚函数 f ，( z ) 一丢砉p t n ( 1 一忌9 t ( z ) ) f c z ，“，口，七，2 一喜 j ( x ，十鲁薹，弓c z ，z i n t q 后 i o o z q 知 其中q 七= z i 吼( z ) ，i = l ，2 ，m ) ，并给出了一些主要收敛结果 对问题( p ) ，我们构造对数一指数型乘子精确罚函数，其形式如下： 限川m 刺i n 酬而入萨m ) + 丢p h ( 1 + e 蛳。) ) 这里p 0 ，九0 ，i = 1 ，m 本文主要是引入对数一指数型罚函数，而且在罚函数中添加了乘子参数，使 之成为光滑的精确乘子罚函数，从而有利于算法的设计 而且我们是用比较初等的方法，证明了原问题和相应的乘子罚问题之间全局 最优解的近似等价性，并讨论了所给罚函数的凸性及其精确性同时又给出了原 问题的k k t 乘子与相应罚问题中的乘子参数和罚参数之间的一种近似关系。最 后，设计了一个算法，数值试验表明所给算法是有效的 2 2 主要结论 定理2 2 1 若矿g ( p ) ， mm 2e 入 l n2 p ( m + f ( x + ) ) + 2 九l n 2 p ， 有限，其中 0j = 1 ，m o 仇e 一2 ( s 帕州m ) )