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

摘要 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一 门独立的学科还是在上世纪4 0 年代末d a n t z i n g 在1 9 4 7 年提出求解一般线性规 划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技 术的巨大发展，至今短短的几十年，它得到了迅猛的发展现在，解线性规划、非 线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种 最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等 方面得到了广泛的应用，成为一门十分活跃的学科 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域求解约束 非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方 法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法罚函数方法 通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时， 求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为 精确罚函数，否则称为序列罚函数针对传统罚函数的定义而言，若罚函数是简 单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不 光滑的；若罚函数是精确的、光滑的，则它一定是复杂的因此我们的工作是对传 统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后 的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结果我 们把这类罚函数称为简单光滑乘子精确罚函数所谓简单的，即罚函数中包含原 问题中的目标函数和约束函数而不包含它们的梯度，若罚函数中包含有原问题中 目标函数和约束函数的梯度，则称为是复杂的 本论文共三章：在第一章中，简要介绍了目前国内外关于罚函数、精确罚函 数、乘子精确罚函数的研究工作；第二章提出一种带有指数、对数性质的乘子罚 函数，并进行了定的数值试验，取得了较好的计算效果；第三章介绍我们给出 了一类等式约束最优化问题的精确罚函数，理论证明了该罚函数是简单的光滑 的。以此为基础，给出了简单精确光滑罚函数算法。 i 关键词：混合整数规划非线整数性规划非线性规划全局最优解填充函 数打洞函数分支定界积分函数。 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 n i m u mo ft h ep e n a l t yp r o b l e mi sam i m 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 e $ 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 t h i sp a p e rm a i n l yc o n s i s t so ft h r e 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 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 dd i s c u s si t s p 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 et h i r dc h a p t e r ，b a s e do nt h ep a p e rf w h u y e ra n da n e u m a i e r ，an e w e x a c tp e n a l t yf u n c t i o n ，s i a mj o u r n a lo no p t i m i z a t i o n ，v o l3 ( 4 ) 2 0 0 3 p 1 1 4 1 11 5 8 w eg i v ean e we x a c tp e n a l t yf u n c t i o n t h en e we x a c tf u n c t i o ni sd i f f e r e n t f r o mt 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 ，i ti ss m o o t ha n ds i m p l e ，n a m e l y , t h eg r a - d i e n to ft h eo b j e c t i v ef u n c t i o ni sn o ti n v o l v e di nt h en e we x a c tp e n a l t yf u n c t i o n s o ，i ti sv a l u a b l ef o ru st om a k eu s eo ft h en e we x a c tp e n a t l yf u n c t i o nt oc o n s t r u c t ap e n a l t yf u n c t i o nm e t h o d 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 ；d i s c r e t eg l o b a lo p t i m i z a t i o n ；m i ) ( e d i n t e g e rn o n l i n e a rp r o g r a m m i n g ；g l o b a lm i n i m i z e r ；t u n n e l l i n g f u n c t i o n ；b r a n c ha n db o u n d ；i n t e g r a lf u n c t i o n ；g l o b a lo p t i - m i z a t i o n ；f i l l e df u n c t i o n i i i 上海大学硕士学位论文 第一章基础知识及相关结论 1 1 基础知识 考虑如下约束非线性规划问题 ( p ) m i l lf ( x ) s t 矶( z ) 0 0 = 1 ，2 一，m ) ( 1 1 1 ) z x 其中f ，吼，i = 1 ，2 ，m 是定义在舻上的非线性连续可微函数，x 是舻的 一个子集，z = 1 ，z 2 ，) t 是n 维向量集合 s = z xi9 t ) o ，i = 1 ，2 ，m ) 表示为问题( p ) 的可行域，s 中的点称为问题( p ) 的可行点 设z 。s ，若存在矿的领域 d ( z ，6 ) = 【z10z z l l 6 ) ， 使对任意z sno ( z ，6 ) 成立 ， 。) ( o ) ，p = i j ( z ) la ：= o ) l ( x ，入) 在矿的h e s s i a n 阵为 v 2 l ( z ，r ) = v 2 f ( x ) + x v 2 俄( 矿) 诞j ( 。) 其中v 2 ，0 ) ，v 2 玑( 矿) ( i ， ) ) 分别是，夕t0 = 1 ，2 ，仇) 在z 的h e 鹋i 衄阵 定义锥 c = d lv g ( x + ) t p = 0 ，t r ，v g ( z ) t p 0 ， o ) ， 于是，v p c ，都有 ，v 2 l ( x ，a ) p 0 ， 则z + 为严格的局部极小点 定理1 1 4 ( 二阶必要条件，见【1 1 】定理4 4 3 ) 设在问题( p ) 中，玑g = 1 ，2 ，m ) ，在舻上二次可微，z 为局部极小点，l a g r a n g e 函数在z 的h e 蹈i a n 阵 为 v 2 三( z ，a ) = v 2 ，( z ) + 碍v 2 统( z ) d l ( z ) 3u 圭塑盔燮堂篁笙銮 其中v 2 ，( 矿) ，v 2 9 t ( x ) ，i i ( x ) 分别是，g ii l ( z ) 在矿的h e s s i a n 阵 假定v g i ( x ) ，i ， ) 线性无关，则矿为k - k - t 点，且对坳c = 切0f v 臻( z ) 0i ，( z ) 成立：，弋7 2 己( z ，a ) 尹0 通常对于求解非线性规划问题方法，应当要求它具有有关的收敛性，而要判 断其有效性，除了可以看它是否具有收敛性之外，重要的衡量标准是它的收敛速 度。下面我们将介绍有关的收敛性和敛速的一些定义 定义1 1 1 ( 局部收敛性) 设矿为问题解，存在z 的某领域d 0 ，盯) ，盯 0 ，对任意初始点x o o c x ，口) ，由算法产生的点列 珏 ，总成立1 i m 瓢= 矿 一 定义1 1 2( 全局收敛性) 设矿为问题解，对任z o 舻，由算法产生的 点列p 七) ，总成立1 i m = 矿 詹+ o d 定义1 1 3 ( 局部线性敛速) t ) 为由算法产生的点列，矿为问题的解，若 成立j lx k + l - - z | | ci | x k - - x 。| | ，或 ，( 瓢+ 1 ) 一，0 ) j gl ，( 瓢) 一，扛) l ，这 里七岛，硒 0 为某正整数，0 c 1 ，则称点列 x k ) 具局部线性敛速 定义1 1 4 ( 一致线性敛速) x k ) 为由算法产生的点列，矿为问题的解，若 成立f iz 詹+ l - - t , + i l ei fz 知一z 0 ，或if ( x k + 1 ) 一f ( x ) l elf ( x k ) 一，( z ) i ，对 所有k = 1 ，2 ，0 0 为常数 4 1 2 罚函数方法 考虑问题 m i n f ( x ) ( 户) s t 吼 ) o i = 1 ，2 ，m ( 1 2 1 ) 幻 ) = 0 ，歹= 1 ，2 ，凡 z x 其中xc 胛 罚函数方法的基本思想就是把上述约束问题变换成无约束问题来求解，采用 的方法是在目标函数上加上一个或多个与约束函数有关的函数，而删去约束条 件，在形式上把问题( p ) 变换成如下形式： ， q ( z ，入七，p 七) = ，( z ) + a k h ) 】+ p 七矽【b ) 】 ( 1 2 2 ) j = l j - - x 其中，( 掣) ，矽( 秒) 为连续函数，且满足( 箩) = 0 ，y 0 且多( 箩) 0 ，暑， 0 ； 砂( 可) = 0 ，可= 0 且矽( 秒) 0 ，y 0 ，而k ，肌，为罚因子，q ( z ，k ，纵) 称为罚 函数 若h = a ，纵= p ，则是一个无约束问题；若出现一列九，纵，七= l ，2 ，h ， 地t + o 。则是一系列无约束问题 罚函数法主要分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 罚函数法和精确罚函数法三类它们有一点共同点就是对不可行点 要予以惩罚其惩罚大小体现在罚参数h ，纵及( 可) ，妒( ! ，) 上 用罚函数方法来解约束最优化问题通常认为最早由c o u r a n t 在求解线性规 划时提出。后来，c a m p 4 8 】汞i p i e t r g y k o w s k i 4 7 讨论了罚函数方法在解非线性规 划问题中的应用。f i a c c o 和m c c o r m i c k 1 一f 6 】在利用罚函数方法，即序列无约束极 小化方法上作了不少工作，并总结为s u m t 方法 s u m t 法是用形如血n 【，( z ) + 即( z ) 】的序列无约束问题来替代问题( 户) ，其 中p 0 称为罚参数，p ( z ) 称为俨上的罚函数它满足： 1 p ( z ) 在舻上连续； 2 p ( x ) 0 ，v z 舻； 5 3 p ( z ) = 0 充要条件是 z s = zl 吼( z ) 0 ，i = 1 ，2 ，m ，b ) = o ，j = 1 ，2 ，7 ) 例如对问题( 户) ，下述两函数均是罚函数 t nr p ( z ) = 砂( 吼o ) ) + 妒( ，b ( z ) ) ( 1 2 3 ) i = l j = l mt i p ( z ) = m a x ( 0 ，9 t ( z ) ) 】p + ib ( 圳p ( 1 2 4 ) i - - - - 1 j = l 这勤为正整数 般来说，无约束问题 ( q p ) ： m i x n ， ) + p p p ) ( 1 2 5 ) 随着p 的增加，其解必落在p 0 ) 之值很小的一个区域内，亦即s 附近，因而可 设想，当p _ o o 时，问题( q p ) 的解趋于可行域 设q ( u ) = 锄， ，扛) + p p ( z ) lz x ，我们有如下结论： 弓 t e l 2 1 ( 见 1 1 】定理9 2 1 ) 设，吼i = 1 ，2 ，m ，b ，歹= 1 ，2 ，7 为舻上的连续函数，x 为舻中一个非空闭箱，设p ( z ) 由( 1 2 3 ) 定义的连续函 数，如果对任何p 0 ，存在一点2 7 ；x ，使得 o ( u ) = 厂( z p ) + p p ( z p ) = i n f f ( x ) + 即( z ) ：z x ) ， 那么下述结论成立： 1 i n f ，( z ) ig i ( z ) 0 ，i = 1 ，m ，b ( z ) = 0 ，歹出1 ，t _ ，z x ) s u p v ( u ) ； u o 2 ，( ) 是关于p 的单调不减函数，q ( 肛) 关于z 的单调不减函数，p ( ) 是 关于弘的单调不增函数。 6 定t l j l l 2 1 ( 见 1 1 1 定理6 2 4 ) 设f ，吼t = 1 ，2 ，m ，h j ，歹= 1 ，2 ，r 为印上的连续函数，x 为舻中的非空闭箱，设问题( 户) 至少有一个可行 解，p ( x ) 为由( 1 2 3 ) 定义的连续函数，如果对任何肛0 ，存在一点勘x ， 使得 q ( 弘) = ，( z p ) t - p p ( z p ) = i n f f ( x ) + ，印( z ) ：z x 】- ， 而且t ) 也包含于x 中的一个紧子集，那么成立 1 i n f f ( x ) ig i ( x ) 0 ，t = 1 ，一，m ，吩( z ) = 0 ，歹= 1 ，r ，z x ) = s u p q ( 弘) p 之o = l i mq ( p ) ； j 一r w 2 ) 的任何收敛子列的极限点是原问题( 户) 的一个最优解； 3 n m p p ( z p ) = 0 p 。，r 显然，如果对某个p 成立p ( x p ) = 0 ，那么是原问题户的最优解。 从定理1 2 1 得知，当取罚函数p 充分大时，问题( q p ) 的最优解可以任 意逼近原问题( p ) 的最优解，但是，如当p 很大时，( 却) + p p ( ) 的h 嘟i a n 阵 趋于病态而导致计算困难，因此当用无约束优化方法来解r a i nf ( x ) + 肛p 0 ) 时， 运用有些算法如n e w t o n 法，其收敛速度很慢，引用s u m t 方法来解原问题所需 的计算量是比较大的。因此产生了求解约束非线性规划的一些改进的罚函数方法 与传统的罚函数( 1 - 2 3 ) 不同，在文 8 9 】中亦讨论了不等式约束非线性规划问 题( p ) 的指数型罚函数，其形式如下； z r a 舻i n ( z ) 三m ) + r e x pf 露( z ) 叫，r 0 称为 p ) 的靠极小解，若满足下述不等式： a ( ) 0 ，而r k 0 为罚参数 它得到下述七一近似解的结论 定理1 2 2 ( 见文【8 9 】命题2 1 ) 假定函数，( z ) ，鲰( z ) ，蕾= 1 ，2 ，m 是连续 的且s 下有界。令酞舻是氏的七一极小解，这里钆0 ，仉 0 都趋 于o ，则点列 ( z 南) ) 的任一极限点矿皆为原问题的全局解此外若存在f 7 0 成立 i l 熙，厂( z ) = + o 。 以z ) s ， 则点列 ( ) ) 的极限点一定存在 f n 很显然，对于上述指数型罚函数二( z ) = ，( z ) + r e x p 参( z ) ，】= i = l ，( z ) + 叩( z ，r ) ，其中p ( z ，r ) 0 ，对所有z ，而当z 乏s ，r 0 时，p ( z ，r ) 随 着7 0 减小而增大，且对同样r 0 ，z 芒s 的不可行程度越严重，则p ( z ，r ) 值 越大这一指数型罚函数 ( z ) 是简单的、光滑的，但仍然不是精确的因为仅 当仉 【0 时，若z 七收敛于矿，则矿为原问题的全局解，因此仍是序列的 定理1 2 3 ( 见文 8 9 】定理3 1 ) 设，( z ) ，姨( z ) 在问题( p ) 的最优解矿的某个 邻域内二次连续可微，如果在z 处满足严格互补和二阶最优性条件，则方程组 v ，( z ) + e x p 【鱼p ) 7 】v 垒p ) = f d = l 在( o ，o ) 附近关于( 7 l ，) 定义了一个连续可微隐函数z ( r ，f ) ，其中r 0 ，并满足 豳z ( n ) = 矿 r i o 此外，j i ( r ，f ) = e x p 【c 0 ( 7 ，) ) 乃】是连续可微函数，并满足 f 1 i o r r a i 。，) = x 并且当( r ，) 趋于( 0 ，o ) 时，z ( r ，善) 和入( r ，) 的导数有极限，还对所有充分小r ，点研 。( r ，0 ) 是二的严格局部极小点。 8 在介绍了一个外插算法后，文章又给出了如下结论 定理1 2 4 ( 见文【8 9 】定理5 1 ) 设畲七十1 是经第次迭代后得到的外插点，对 罚参数t k + l 首次迭代的牛顿方向e 满足 0e ni f ( ) ( r 2 ) 此外，如果z 韪1 表示首次牛顿迭代后得到的点，则有 1 3 精确罚函数方法 考虑问题 r a i n ，( z ) ( p ) s t g i ( z ) 0 ，t = 1 ，2 ，m z xc 俨 i o ( r 2 r k 。) 精确罚函数是用形如卿 ，( z ) + 弘e ( z ) 】的无约束问题( 耳) 来替代问题( p ) ， 其中肛为参数，e ( x ) 为x _ r 上的函数且满足： 1 e ( z ) 0 ，v x x 2 e 0 ) = 0 的充要条件是z s ， 这里 s = zi 吼( z ) 0 ，l = 1 ，2 ，m ，z x ) 定义1 3 1 若存在肋 0 ，当p 脚时使得问题( 兄) 的解是问题( p ) 的 解，或问题( p ) 的解是( b ) 的解， 则称 ，( ) + p e ( 却) 为问题( p ) 的精确罚函数。这里解可以是局部最优解，也可以是全局最优解。 精确罚函数概念首先由e r e 衄【4 2 和z a n g w i n 【1 0 7 】于上世纪六十年代后期 提出。这是线性规划中大m 法在非线性规划中的自然推广。从那时起，精确罚函 9 z 玑v + 七 r v蚪 z 阢p既 m m + d 蚪 z f， v 上海大学硕士学位论文 数一直在数学规划理论与方法中扮演很重要的角色。下面我们介绍发展最为成 熟的1 1 精确罚函数方法的主要理论结果： 设原问题( p ) 中集合x 为开集，令( 1 2 4 ) 中p = 1 ，得罚问题 ( e ) 卿m ) + p ( m a x 0 ，鳜( z ) ) + i h i ( z ) 1 ) 称 片( z ，p ) = 厂( z ) + p ( m a x 0 ，吼( z ) ) + l 如( z ) i ) t = l j = l 为z 1 精确罚函数，1 1 精确罚函数又称为经典精确罚函数 定理1 3 1 ( 见文i n 定理9 3 1 ) 设矿为问题( p ) 的k - k - t 点，( t ，矿) 为 与矿相应的k k t 乘子，进一步，设f ( x ) ，矶 ) ，i j 1 0 ) = 0l9 t ( 矿) = 0 ， = 1 ，2 ，m ) 是凸函数，而且h i ( x ) ，j = 1 ，2 ，r 是仿射函数，则 对p m a x 心，蕾o ( x ) ，l 嗡l ，歹= 1 ，2 ，r ) ，矿也是问题( e ) 的解 定理1 3 2 ( 见文 1 0 0 l 定理4 4 ) 设z 为问题( p ) 的一个严格局部极小点，( z ) ， 夕t ) ，i = 1 ，m ，( z ) ，歹= 1 ，在矿的一个领域内连续可微，进一步， 设z 满足：m a n g a s a r i a n - f r o m o v i t z 约束品性，那么存在旷，使得p 矿，矿 是问题( q 1 ) 的局部极小点 定理1 3 3 ( 见文 1 0 0 l 定理4 6 ) 设命题1 2 3 的条件成立，则对任何满足p m a x 心，i i o ( x ) ，l 哆i ，j f = 1 ，2 ，r ) ，的罚参数p ，矿是罚问题( r ) 的 严格局部极小点。 在算法方面，尽管使用精确罚函数的历史已经很长，由于已经证明在传统罚 函数定义下，若罚函数是简单的、光滑的，则一定是不精确的，这里所谓简单的 表示罚函数表达式中只含目标函数和约束函数。考虑问题 仉 0 i = 1 j = l 若罚问题是精确的、光滑的，则罚问题的表达式一定包含有，0 ) ，g i ( x ) ，h j ( z ) 的 梯度。如对只含不等式约束问题( p ) ，其罚函数为 q ( 2 ，a ，盯) = f ( x ) - 4 - a ( 茹) t g ( x ) ( 1 3 1 ) = f ( x ) - 4 - a ( z ) + v f ( x ) g ( x ) + 等( 4 + ( 。) 夕( 2 ) t ) ( a + ( 。) 夕( z ) ) ，( 1 3 2 ) 其中盯 0 ，a ( x ) a ( x ) = v f ( x ) ，4 0 ) = v 夕( z ) ，a + 0 ) 表示矩阵a ) 的广义 逆这里q ( z ，a ，口) 的表达式中包有， ) ，爨( z ) 的梯度，这种表达式就变得复杂了 鉴于上述情况，我们考虑对传统罚函数的定义进行改变，改变后的罚函数 定义为z s 兮p ( z ) 0 ，甚至于p ( z ) 0 且远大于 当z s 时，p ( z ) 的值按照这种改变，下一节我们将介绍和讨论简单光滑乘子 精确罚函数的现状及我们所得到的某些结果 】 1 4 乘子精确罚函数方法 文 3 7 1 构造一个改进的指数型乘子罚函数，从而分析了极小化凸规划问题的 乘子指数型方法以及对偶情况，并给出了一种熵极小化算法，而且强化了方法的 有效收敛结果，在应用到线性问题时，给出了其收敛速度，以下对这一途径作一 简单介绍，参文【3 7 】 考虑非线性规划问题： m i n ，( 2 ) s t 仇 ) 0 ，t = 1 ，2 ，m 假使( 1 4 1 ) 的最优解集非空且有界， zif ( x ) 0 其算法由下两式给出 i = 1 m 七 矿0 加神m i n 饥卅萎篝妒( 弓咖) ) ) ( “2 ) 砖+ 1 = 谚e 亏毋( 矿) ，歹= 1 ，2 ，m ( 1 4 3 ) 其中脚 0 是相当于第j 个约束的乘子，c j 0 是罚参数。此外当f ，g t 为凸 函数时，而相应的对偶问题为 m a xd ( # ) ( 1 4 4 ) “7 u 、 其中 州= 蛳 m ) + 心毋( z ) ) ( 1 4 5 ) j = l 由此给出了熵极小化算法 - = a r g 搿似小姜争( 钞 ( 1 4 6 ) 1 2 这里妒+ 是妒的共轭函数，它是一个熵函数： 且有如下k k t 最优性条件 及 妒( s ) = si ns s + 1 t n 0 o f ( x 七) + 矿1 嘞( 矿) ， 0 0d ( p 七+ 1 ) 一 v 砂( 啦+ 1 p ；) 砖 v 妒+ ( p l m 蠹+ 1 p 二) 磊 ( 1 4 7 ) 对凸规划问题，文( 3 7 】给出了算法的收敛性分析，现介绍有关主要性质。由 于其证明十分复杂，这里从略 设q ( u ，u ) = t l n ( u 加) 一u + 御，( t ，秒) 【0 ，) ( 0 ，+ ) ，利用公式 妒。( s ) = si ns s + 1 ， 可得g ( u ，v ) = 妒( u ) 这样( 1 4 6 ) 重新写成 p 12 a r g 搿一萎巧1g ( 吻，棚， 7 u !c ： 。 记 其中 m d ( a ，芦) = 口( ，纷) ， ( a ，p ) 【o ，o o ) m ( o ，+ ) m ， j = 1 m = p 【o ，o o ) mid ( p ) 。p ) 因此给出了以下一些性质： 护= j i ma ( u 七) 尤- 寸0 0 性质1 4 1 ：( 见文 3 7 】引理3 1 ) 比m ，序列 d ( 乒，矿) ) 是单调非增的 且【矿) 收敛 1 3 性质1 4 2 - ( 见文【3 7 】引理3 2 ) ( a )d ( p 知) d ( p 七+ 1 ) s ，v k 成立 ( 6 ) v j ，心砂( u 知缈( z 七) ) u 七一砖缈( z 七) 一0 ( c ) v 歹，店缈( ) 一0 ( d ) d ( 矿) 一，( 扩) 一0 性质1 4 3 ：( 见文【3 7 】引理3 3 ) 若令矿= 垡軎三筹，则有 。l i ms u p 鲂( 矿) 0 ，j i = 1 ，2 ，m 矗_ 一 性质1 4 4 ：( 见文 3 7 】命题3 1 ) 设 矿) 是由( 1 4 2 ) 和( 1 4 3 ) 产生的序列，且罚 参数满足弓= ，d 0 ，vk ，则 矿) 收敛于对偶问题( 1 4 4 ) 的最优解， 此外，序列 矿) 有界且其每一个聚点是原1 6 j 题( 1 4 1 ) 的最优解 性质1 4 5 ：( 见文【3 7 】命题4 2 ) 设 矿) 是由( 1 4 2 ) 和( 1 4 3 ) 产生的序列，罚参 数由亏= c 瞄，vk ，这里常数c 0 ，假定 矿) 收敛于m 中的点，则 矿) 至 少是二次收敛的 1 l 精确罚函数在那些使得对某个i 1 ，2 ，m 成立负( z ) = 0 的z 处 不可微，而非线性规划中大部分效果较好的算法都要求目标函数具有可微性，从 而促使人们去思考罚函数的光滑化 3 8 】， 3 9 】，【4 0 】文 4 0 】p i n a r 和z e n i o s 针对凸 规划问题提出了对f 1 精确罚函数的二次函数光滑逼近，并证明了通过解光滑 后的罚问题，可以得到e 可行和肛近似全局极小点，这里口是常数。此外， 在1 9 9 9 年，d g o l d f a r b 和r p o l y a k 等在文( 4 1 】“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 ，( z ) 一未他l i l ( 1 一坝( z ) ) f ( x ，他，v ，克) = 1 4 z i 礼t q 七 z 毛i n tq 七 p n、|， 危 触 七一2 + d p；吗 ，皿， 一 上海大学硕士学位论文 - - - 一一o 一 其中q 七= zi 夕( z ) - i ，t = 1 ，2 ，m ) 记 mf 三( 掣，可) = 他) + 讹仇( z ) + v j h j ( x ) ， = 1 j = l i = 0i 仇( z ) = o ) = 1 ，2 ，z ) ， 零是问题( 1 2 1 ) 的严格局部极小点，则有下述主要收敛结果： 定理1 4 1 ( 见 4 1 】定理5 。1 ) 假定对问题( 1 2 1 ) 在严格局部极小点z 处满足 第二阶最优性充分条件，则存在k o 0 ，占 0 ) 使得对任何 ( 缸，t ，k ) = ( u ，k ) d ( ，正k o ) = t ( u ，k ) = ( 缸，钉，k ) li iu u i l 6 七，u c l ) 0 ，t ( 仇一z ) 0 ，k k o ， 0u0 有界，有： ( 1 ) f ( z ，t ，u ，k ) 在矿的某一开球内有唯一极小点岔= 金( ，口，k ) ( 2 ) 对( 2 ，也，虽) ：哦= u ( 1 - k g i ( 2 ) ) ，i = 1 ，2 ，m ，喀= 一k h j ( 畲) ，歹= 1 ，2 ，r 成立 其中 。岔一z l i 丢l i 一u o ，i id 一叫1 1 0 与无关 定理1 4 2 ( 见【4 1 】定理5 2 ) 假定对问题( 1 2 1 ) 在全局最优解z 。满足第二阶 充分条件并假定存在 0 使得对所有固定u 0 和t j 及所有有限数q ，水平 集k ( t ，t ，k o ) = 扛俨lf ( z ，u ，移，) sq 为有界集，则当k o 0 充分大 使得对任何( u ，是) d p ，仃，) 定理1 5 1 中的点意是f ( z ，让，钐，k ) 的全局最 优解。 下面我们将给出关于指数型及对数型两类乘子精确罚函数的新形式，并讨 论某些相关的结论。若在问题( p ) 中，xc 舻为有界闭箱， ) ，9 ) ，i = 1 ，2 ，m 为光滑函数，则相应的指数型及对数型乘子精确罚函数分别表示为： 】5 1 指数型 ( q 札) 其中p 0 为罚参数，而九0 ，i = 1 ，m ，与原问题乘子有关的参数 2 对数型 ，。、m i n q ( x ，入，p ) = m ) 一言1 n ( 1 一九p g ( z ) ) ( q ) p 百 s t x x 或 ，n 、 面n q ( z ，入，p ) = ，( z ) 一五1 丸抚( 1 一弘鳜( z ) ) ( q 舢) p ：； s t x x 其中弘 0 为罚参数，而20 ，主= 1 ，r n ，为与原闯题乘子有关的参数 我们讨论了g ( p ) 、l ( p ) 与g ( q a p ) 、l ( q p ) 之间的关系，发现沁0 ，t = 1 ，2 ，仇与原问题( p ) 的乘子有着密切的联系，从而我们称它们为简单光滑乘 子精确罚函数。 特别需要指出的是在求解某类凸规划时，我们运用上述形式的乘子精确罚函 数，用牛顿法求解时，效果很好，具一致全局线性收敛性和局部二次收敛性 1 6 p 卿k e m ：i 1 一p +z 厂 兰 肛 x p q x 口 童 m s 第二章乘子精确罚函数法 2 1引言 考虑约束非线性规划问题 ( p )r a i n f ( z ) ，z s 其中s = z x i 肌( z ) 0 ，i = 1 ，m ) ，这里 j m ( x ) = + ，( z ) ，吼 ) ，主= i i 霉i i _ + + 1 ，m 为两次连续可微函数 记l ( p ) ，g ( p ) 分别为问题( p ) 的局部极小点和全局极小点的集合，1 7 tg ( p ) c i n t x ，x r n 为一个大的有界闭箱。 本文研究和探讨的问题是用罚函数方法来寻求问题( p ) 的局部极小点和全局 极小点关系，而对传统罚函数而言，当参数充分大时，相应罚问题的最优解可任 意逼近原问题的最优解。但当罚参数很大时，其罚函数的h e s s i a n 阵可能会趋于 病态，而导致计算困难【1 1 。因此产生了求解约束非线性规划的一些改进的罚函数 方法 文【8 9 】讨论了不等式的约束非线性规划( p ) 的指数型罚函数，它是一种改变定 义后的序列近似罚函数，其形式如下 瓣 ( z ) = m ) + r e x p 恤( z ) r ， 0 i = 1 针对问题( p ) ，文【3 7 】提出了与原问题乘子有关的乘子罚函数问题，使得定义 的精确罚函数为 仇 ，( z ) + 去 地( e x p c g i ( z ) - 1 ) ，c 0 ，雎 0 1 7 并给出相应的算法和收敛性等有关结论，文【4 1 】具体构造了变形障碍一增广乘子 罚函数 f ，( z ) 一丢姜肌h ( 1 一忌矶( 2 ) ) f ( z ，u ，口，南) = 一心( z ) + 鲁磅 ) 2 i n t f 2 七 lj = l j = 1 i o o z q 七 其中q 七= x l g , ( x ) 丢，i = 1 ，2 ，m ) ，并给出了一些主要收敛结果 对问题( p ) ，我们构造对数指数型乘子精确罚函数，其形式如下： ( 剐m 喇i nq ( m ，p ) = 他) + 丢汕( 1 - t - e 脚( z ) ) ， 这里p 0 ，九0 ，i = 1 ，仇 本文主要是引入对数指数型罚函数，而且在罚函数中添加了乘子参数，使 之成为光滑的精确乘子罚函数，从而有利于算法的设计 而且我们是用比较初等的方法，证明了原问题和相应的乘子罚问题之间全局 最优解的近似等价性，并讨论了所给罚函数的凸性及其精确性同时又给出了原 问题的k k t 乘子与相应罚问题中的乘子参数和罚参数之间的一种近似关系。最 后，设计了一个算法，数值试验表明所给算法是有效的 2 2 主要结论 定理2 2 1 若z g ( 尸) ， m m 2 九l n2p ( m + ( x + ) ) + 2 九l n 2 肛芝 ， 仇f 1 。 有限，其中 2i n ( 1 + e p 9 幻( z o ) ) 0j = 1 ，m o 卜 o ，对z 趴( g ( p ) + e b ( o ，1 ) ) ，仍成立，( z ) ，( z ) 因为s ( g ( p ) + e b ( p ，1 ) ) 是一个有界闭集而，( z ) 是x _ i z 的连续函数，故存在。 0 及e l 0 ，1 0 ，而x ( s + e 1 b ( o ，1 ) ) 为有界 闭集，故 x 、( s + r a 。i n 曰) 乎吼( z ) 29 ( z o ) o ，x 、( s + 1 曰( 只1 ，) l 。、 这里x , o x ( s + e x b ( o ，1 ) ) ，i o ( i ，m ) 下面讨论问题( p ) 和( r p ) 的全局解的近似关系 ( 1 ) 若z ( s + e 1 b ( o ，1