（应用数学专业论文）精确罚函数与交叉规划问题的研究.pdf

摘要 罚函数是用于求解非线性规划问题的一个重要方法，它将有约束的优化问题 转化为无约束的优化问题进行求解，使得求解过程变的简单有效，因此罚函数方 法一直是国际上研究的重要课题。交叉规划是近年来发展起来的个新的研究领 域，是用于解决多人决策问题的一种数学模型，它的主要研究内容包括最优解的 定义及其求解。 本文研究求解约束优化问题的精确罚函数和交叉规划问题的理论与方法，本 文第一章首先讨论了课题的来源、罚函数和交叉规划方面的研究进展，第二章研 究了一种的菲线性双参数罚函数的精确性和算法，第三章研究了二次l a g r a n g e 双参数罚函数的精确性和算法，第四章研究了两种口次l a g r a n g e 罚函数的精确 性和算法，第五章研究了多目标规划问题的二次l a g r a n g e 罚函数的精确性并提 出了一个交互算法，第六章研究了集值映射向量优化问题的精确罚函数问题。第 七章讨论了m 人交叉规划问题的s 一最优联合解的定义、存在性和求解问题，以 及与对策问题的联系，第八章研究了用非线性罚函数求解整数规划和交叉规划的 方法，讨论了基于非线性罚函数的一种神经网络模型。 本文所取得的研究成果可分以下七个方面。 ( 1 ) 给出了一种双参数精确罚函数，在不要求凸性、光滑性和镇定性的条件 下证明了其精确罚定理，它确定了最优目标值与目标罚参数值之问的关系；基于 这个结果。提出了个求解原问题最优解的双参数精确罚函数算法，这个算法与 传统的精确罚算法不同。它是通过改变目标罚参数值计算，而约束罚参数不变。 并在较弱的条件下证明了算法的收敛性；数值计算结果表明了算法的有效性。 ( 2 ) 针对二次l a g r a n g e 双参数罚函数，证明了与第二章不同的一个精确罚定 理，给出了一个求解罚优化问题的下降算法和改进算法，并分别证明了它们的收 敛性。 ( 3 ) 研究了两种口次l a g r a n g e 罚函数的形式，获得了原约束问题最优值与两 种罚函数闯题最优值之间误差的估计，证明了在凸性条件下的精确罚定理；并给 出了一个求解序列无约束光滑罚函数优化的算法，证明了其收敛性。讨论了2 七 次l a g r a n g e 双参数罚函数形式。 ( 4 ) 定义了多目标规划的一种二次l a g r a n g e 罚函数，证明了罚函数的最优解 是原多目标规划的p a r e t o 弱有效解的精确性结果。在给定理想目标和权重不变的 条件下，给出了一个求解多目标规划的下降算法，证明了其收敛性，进而还提出 了求解多目标规划的一种交互式算法。 ( 5 ) 研究了集值向量优化问题的精确罚函数问题，引进了集值向量优化问题 的镇定性和稳定性的概念，讨论了它们之间的关系，证明了一种向量集值优化罚 函数的精确罚定理。 ( 6 ) 引进了m 人合作交叉规划问题的一般模型，提出了m 人交叉规划问题的 最优联合解的概念，证明了判断最优联合解的两个定理；引进了s 最优联合解的 概念，证明了它的存在性，并将其求解转化为求解一个单目标规划问题；研究了 凸交叉规划的s 最优联合解集的性质：进而，还讨论了合作对策问题与合作交叉 规划问题之间的联系。 ( 7 ) 将有界变量的整数规划或混合整数规划问题可以转化为一个等价的非整 数规划问题，并给出了用双参数罚函数求解整数规划的若干例子，计算表明我们 的算法是有效的。利用非线性罚函数构造了一种非线性神经网络，证明了罚优化 问题的最优解与神经网络动力系统的平衡点之间的联系。给出了双参数罚函数求 解m 人合作交叉规划的方法。 本文最主要的创新包括两个方面。一、提出了一个基于双参数精确罚定理的 算法，这将对非线性规划求解方法提供新的思路；二、建立了一类合作交叉规划 问题的基本理论，这有助于解决许多实际交叉决策问题，帮助人们进行决策。 关键词精确罚函数交叉规划问题非线性双参数罚函数非线性规划多耳标规划对策 论集值映射向量优化问题最优解p a r e t o 弱育效解鼍优联合解s 最优联合 解n a s h 均衡解 a b s t r a c t t h ep e n a l t yf u n c t i o nm e t h o di s o n eo ft h em o s t i m p o r t a n tw a y st os o l v e m a t h e m a t i c a lp r o g r a m m i n g i t sm a i ni d e ai st ot r a n s f o r mac o n s t r a i n e dm a t h e m a t i c a l p r o g r a m m i n gi n t oas e q u e n t i a lu n c o n s t r a l n e dm a t h e m a t i c a lp r o g r a m m i n gw h i c ha r e e a s i e rt os o l v e h e n c e ，t h ep e n a l t yf u n c t i o nm e t h o di sa ni m p o r t a n ts u b j e c ti n t h e m a t h e m a t i c a l p r o g r a m m m g a s an e ws u b j e c t ，t h e i n t e r a c t i o n a l p r o g r a m m i n g p r o b l e m ( p p ) i sam o d e lf o rm u l t i p e r s o n d e c i s i o nm a k i n g p r o b l e m s t h ek e y p r o b l e m s i ni tj n c l u d eh o w t od e f i n eas o l u t i o na n dh o wt os o l v ej t t i l i sd i s s e r t a t i o ns t u d i e st h ee x a c tp e n a l t yf u n c t i o nm e t h o df o rm a t h e m a t i c a l p r o g r a m m i n g a n di n t e r a c t i o n a lp r o g r a m m i n g p r o b l e m s t h ed i s s e r t a t i o ni 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 ed i s c u s st h eo r i g i no f t h es t u d y ，t h ea d v a n c eo f t h e p e n a l t yf u n c t i o nm e t h o da n di p e i nc h a p t e r 2 ，w es t u d y an o n l i n e a rp e n a l t yf u n c t i o nw i t ht w op a r a m e t e r s i nc h a p t e r3 ，w es t u d ye x a c t n e s s f o ra s q u a r el a g r a n g ep e n a l t y f u n c t i o nw i t ht w o p a r a m e t e r sa n dp r e s e n t a na l g o r i t h m b a s e do ni t i nc h a p t e r4 ，w es t u d ye x a c t n e s sf o rt w ot y p e so ft h e 口一t hl a g r a n g e p e n a l t y f u n c t i o n s i n c h a p t e r5 ，w es t u d y a ni n t e r a c t i v e a l g o r i t h m t os o l v e m u l t i o b j e c t i v ep r o g r a m m i n gp r o b l e m s b a s e do nt h es q u a r el a g r a n g e p e n a l t y f u n c t i o n i nc h a p t e r6 ，w es t u d ya ne x a c tp e n a l t yf u n c t i o nf o rv e c t o ro p t i m i z a t i o np r o b l e m so f s e t v a l u e dm a p s i nc h a p t e r7 ，w es t u d yt h ed e f i n i t i o n ，e x i s t e n c ea n da l g o r i t h m sf o r t h es - o p t i m a lc o a l i t i o ns o l u t i o n so f 研i p e r s o n si p p s hc h a p t e r8 ，w eu s et h ep e n a f l y f u n c t i o nw i t ht w op a r a m e t e r st os t u d yam e t h o dt os o l v ei n t e g e rp r o g r a m m i n g p r o b l e m s a n di n t e r a c t i o n a lp r o g r a m m i n g p r o b l e m s a n dd i s c u s san e u r a ln e t - w o r k s t h er e s u l t so b t a i n e di nt h i sd i s s e r t a t i o ni n c l u d et h ef o l l o w i n gs e v e na s p e c t s ( 1 a p e n a l t yf i m c t i o nm e t h o dw i t ht w op a r a m e t e r si sp r e s e n t e d w i t h o u tt h e c o n d i t i o n s0 nc o n v e x i l ya n dd i f f e r e n t i a l ，a ne x a c tp e n a l t yt h e o r e mf o rt h i sp e n a l l y f u n c t i o ni ss h o w n 。a n a l g o r i t h mb a s e do n i ti sp r e s e n t e da n di t sc o n v e r g e n c ei ss h o w n s o m en u m e r i c a le x a m p l e si n d i c a t et h ei m c i e n to f t h ea l g o r i t h m ， ( 2 ) f o rt h es q u a r el a g r a n g ep e n a l t yf u n c t i o n 谢也t w op a r a m e t e r s ，s o m ee x a c t p e n a l t yt h e o r e m sa r e s h o w nu n d e rs o m ec o n d i t i o n s as t e e p e s td e s c e n td i r e o r i o n a l g o r i t h ma n di t s m o d i f i e da l g o r i t h mf o rs o l v i n gu n c o n s t r a i n e dn o n l i n e a rp e n a l t y o p t i m i z a t i o np r o b l e m s a r ep r e s e n t e d t h e i r c o n v e r g e n c e sa r ea l s os h o w n 0 。对应的罚优化问题( f p ) 为： r a i n ，( 。) + 户p ( z ) ， s t z r “ 其中p 0 是罚参数。可以证明在一定的条件下，当罚参数增大到无限大时， 罚优化问题的最优解也是原问题( n p ) 的最优解。这样当我们不断的增加罚参 数时，我们需要求解一系列罚优化问题，得到一个近似最优解，但受到精度影 响，罚参数不可能无限增大 1 9 5 5 年f r i s h 和1 9 5 9 年c a r r o l l 发展了内部罚函数 4 5 】考虑非线性规划问 题： ( p ) m i n ，( z ) s t ， g l ( x ) s0 ，i = 1 ，2 ，一，m 。 注意到任何一个问题( n p ) 都可以转化成问题( p ) 的形式其内部罚函数b ( z ) = 一凳lz 0 9ig i ( 。) j 对应的罚优化问题( f p ) 为： m i n ，( $ ) + t b ( 。) ， s t z r “， 1 0 西安电子科技大学博士论文：精确罚函数和交叉规划问题的研究 其中t 是罚参数，可以证明在一定条件下，当罚参数t 趋向0 时，罚优化问题 的最优解也是原问题( p ) 的最优解。 还有其他形式的内部罚函数，如口( 。) = 一墨，l 屈( 。) ，口( 。) = 銎。l 触( 。) 。 等。上面的外部罚函数p ( z ) 和内部罚函数b ( x ) 并不是精确罚函数，1 9 6 7 年 z a n g h i l l 提出了一个精确罚函数【l 】： m p 扛，p ) = ，忙) + p 芝二m a x 0 ，肌0 ) ) ， i = 1 在一定条件下，存在一个值芦使得当p 万时对应的罚优化问题的最优解都 是原问题的最优解。这样我们可能只需求解一个罚优化问题就可以得到原问 题的最优解。因此，精确罚函数成为人们解决约束非线性规划的重要方法， 并开展了许多研究，如1 9 7 9 年h a n 和m a n g a s r i a n 讨论了精确罚函数1 2 】，1 9 8 1 年r o s e n b e r g h e 和l a s s e r r e 4 】分别给出了一个精确罚函数的全局收敛算法， 1 9 8 2 年c l a r k e 在文 5 】中讨论了精确罚函数的镇定性和稳定性条件，1 9 8 4 年 r o s e n b e r g 也在文 6 j 6 中讨论了精确罚函数的镇定性和稳定性，其中镇定性和 稳定性是判断精确性的充分必要条件，但对于复杂问题无法验证d i p p i l l o 和 g r i p p o 在文 7 - 8 中研究了精确罚函数的算法。1 9 9 5 年m o n g e a u 和s a r t e n a e r 在 文 1 1 】中对精确罚函数的罚参数自动减小问题进行了研究，1 9 9 0 年k o r n e r 和 f r a n k 研究二次规划的精确罚函数的数值解法 3 2 1 ，1 9 8 6 年b e n - t a 和t e b o u l l e 讨论了随机规划的罚函数问题1 3 3 - 3 4 】，1 9 9 5 年韦增欣研究了一族精确罚函数的 存在性及控制参数的下界【3 5 】，1 9 9 6 年林亮讨论了一种精确罚函数的存在性 ，王万量在文 3 7 中研究了l 1 精确罚函数的存在性，杨波艇和张可村研究 了用l l 一罚函数作线性搜索函数的一种修正约束变尺度算法 3 8 j ，刘昌文讨论 了二次规划的精确罚函数法，1 9 9 7 年张连生给出了全局精确罚函数的一 个充要条件，1 9 9 4 年黄学祥也研究了精确罚函数的一致镇定性【4 3 。文献 2 6 2 7 、【3 0 对各种序列罚函数技术进行了详细论述。 在整数规划、多目标规划和分层规划等方面的精确罚函数研究也取得了一 定成果，如1 9 8 6 年s i n c l a i r 和m a r i u s 研究用精确罚函数求解整数规划问题【3 1 】， 1 9 9 2 年n 研究用罚函数求解混合整数规划【2 2 】，2 0 0 0 年y a n g 、m e e s 和c a m p b e l l 讨论了罚函数方法解决0 - 1 整数规划1 2 3 j ，2 0 0 0 年d i m i t r i s 、g e o r g i u 和s r i h e e r 也讨论了类似罚函数方法求解0 - 1 整数规划 2 4 j ，1 9 9 9 年高峰和张连生讨论利 用0 - 1 连续化求解o 1 整数规划的方法【4 7 】，1 9 9 9 年施保昌和陈铤研究了一类 第一章绪论 基于精确罚函数的交互式方法求解多目标规划问题【4 4 】。1 9 9 7 年李智慧和吴 丹等研究了求解线性二级规划问题的罚函数法 4 2 1 ，1 9 9 8 年赵蔚讨论了两层 多目标规划罚函数法，2 0 0 0 年c a m p e l o 、d a n t a s 和s c h e i m b e r g 讨论了解 2 层线性规划罚函数法【1 5 ，2 0 0 1 年刘三阳和杨亚红也研究了二层多目标规划 的一个精确罚函数法 5 0 】。吴志远、邵惠鹤和吴新余在文 4 8 】中讨论了基于遗 传算法的退火精确罚函数非线性约束优化方法，b e r n a u 在文 6 2 中也讨论了 求解规划的有效方法。胡奇英和孟志青等在文 5 2 讨论了集值映射的罚函数 的镇定性和稳定性，并在文 1 5 3 中给出了一种求解整数规划与混合整数规划 非线性罚函数方法。 一般精确罚函数都是不光滑函数，大大影响了它们的应用。自9 0 年以来， 人们一直在寻找新的光滑精确罚函数，p i n a r 和z e n i o s 等给出了一种光滑罚函 数方法卧o ，基本上是在原来罚函数的基础上，通过将不光滑的点用光滑函 数来代替，以提高罚函数的光滑性。1 9 9 6 年周晓阳和施保昌给出了一种广义 精确可微罚函数【4 0 ，2 0 0 0 年张菊亮和章祥荪研究了不等式约束最优化的非 光滑化精确罚函数的一个光滑近似方法【5 l 】。 1 9 9 9 年，r u b i n o v 、g l o v e r 、杨晓奇定义了广义l a g r a n g e 罚函数 1 2 - 1 3 1 ，其 中的一种形式如下： f ( 。，p ) = ( m ) p + p m a x g i ( x ) ，o f ) 1 扫， i e l 其中p ，p 0 。在一定条件下，他们证明罚函数是精确的。当p = 1 时，即为通 常的精确罚函数形式。对应的罚优化问题为： ( p ( p ) ) m i n f ( z ，p ) 。r ”。 2 0 0 1 年杨晓奇和黄学祥发表了l a g - r a n g e 罚函数研究的一系列成果 1 6 - 2 1 】，分 别研究了最优性条件、精确性和算法等方面精确性定理是精确罚函数的重 要成果，在文【1 3 】中已经证明了一个精确罚定理，即存在一个参数p 使得罚问 题( p ( p ) ) 的最优解也是问题( p ) 的最优解的充分必要条件是 ，粤铲铲 喵 其中对“= 0 l ，“。) ，y 如) 是下面扰动问题的最优解： ( p ( u ) ) m i n i ( x ) 8 t $ 妒，g i ( x ) s t ，i = 1 ，2 ，一，m 。 1 2 西安电子科技大学博士论文：精确罚函数和交叉规划问题的研究 事实上，上面保证精确性的条件就是镇定性必须满足，但是这一条件在实际计 算中比较难以验证。 另一方面，一种非常吸引人的带目标罚参数的罚函数方法在6 0 年代已经 有了一些研究这种罚函数的定义如下【2 6 2 1 ： 咖( 。，m ) = ( ，0 ( z ) 一m ) ，+ ( 。) 1 i e i 同样需要构造一个序列罚函数，找到一个对应的序列 m ) 使它收敛到目标最 优值，+ ，从而得到序列x ( m 。) 收敛到最优解。由于同样需要求解许多序列无 约束优化问题，所以这可能是这一方法没有更多研究的原因1 9 6 8 年m o r r i s o n 在文f 2 5 】考虑了问题m i n f ( x ) j g ( x ) = o ) 对应的罚函数： m i n ( ，( ) 一m ) 2 + i g ( z ) 1 2 ， 他研究了构造收敛的m 。方法。f l e t c h e r 在文 2 6 - 27 】仅对罚函数咖( 。，m ) 做了 简要的讨论。1 9 9 1 年b u r k e 在文f 2 8 】考虑了比( 。，m ) 稍微广泛一些的罚函数 形式，但是，没有做进一步的深入研究。f i a c c o 和m c c o r m i c k 在文【2 9 3 0 】类似 地讨论了目标罚函数曲( z ，m ) 。2 0 0 0 年m a u r i c i o 和m a c u l a n 对于o - 1 规划在文 1 4 】定义了下面的目标罚函数： h ( x ，m ) = m a x f o ( 。) 一m ，1 ( z ) ，南( 。) ) 。 在文中给出了一个收敛算法，并做了一些实验。 最后，我们介绍在罚函数与神经网络方面之间的研究。自h o p f i e l d 引进反 馈式神经网络用来求解优化问题取得成功以后，神经网络的研究取得了快速 的发展p 5 9 。用神经网络研究最优化问题成为当前国际上的前沿性研究课题 之一 1 5 9 。焦李成在文f 1 5 9 1 对神经优化进行了详细讨论，邢文训和谢金星在文 4 6 1 中也对神经优化进行了讨论。神经网络解决优化问题过程是引进一个神经 网络，这个网络对应于一个微分动力系统和一个能量函数，研究这个系统的平 衡点的稳定性，当系统能量达到最小时，这个平衡点就是优化问题的最优解。 问题的研究主要是侧重于能量函数和动力系统的构造，以保证系统的平衡点 与优化问题的最优解对应。h o p f i e l d 网络成功地解决了一些约束优化问题，如 旅行商问题、最短路问题和分类问题等f 4 6 】。许多研究所引进的神经网络模型 都类似与h o p f i e l d 模型，近年来，许多研究集中在研究非线性神经网络模型用 第一章绪论1 3 来求解含约束的优化问题，如1 9 9 8 年s m i t h 、p a l a n i s w a m i 和k r i s h n a m o o r t h y 研究了神经网络求解组合优化问题，x i a 和w a n g 给出了神经优化全局收敛 的一个方法 6 1 ，1 9 9 7 年候增广和吴沧浦研究了用广义h o p f i e l d 神经网络求解 数学规划 1 6 0 ，1 9 9 8 年刘舒考、刘雯林、郑晓东和李勇根讨论了同伦神经优化 理论及其在地震反演中的应用 1 6 1 】，2 0 0 0 年钟守楠和蔡伟也研究了多目标拟 神经优化方法 1 6 2 】。 总之，光滑精确罚函数的研究已成为计算非线性规划问题的一个具有非常 诱人的课题。 1 3 交叉规划的研究进展 1 9 9 8 年由刘家壮、李荣生和孟志青在文 1 4 8 】中提出了一种二人交叉规划 的数学模型， ( p ( a ) ) m i n ，( o ，o ) s t 矿( a ，o ) ， ( q ( p ) ) m i ng ( z ，y ) 、 s y ( 反) ， 其中a 和卢分别是问题( p ( a ) ) 和( q ( 卢) ) 的参数变量，并且两者之间存在着一 定的联系，例如 ( 0 1 卢) = o ；矿( 。) ，v ( z ，z ) 是约束条件，我们把这种模型称为 交叉规划( i n t e r a c t i o n a lp r o g r a m m i n g ) 。交叉规划的模型是由若干个参数规划 构成，它是对策模型和群体决策模型的推广，模型也更加复杂，由于存在决 策变量之间联系和相互的作用关系，所以我们取名为交叉规划z a n g w i l l 和 g a r e i a 1 4 6 ，f l a r e 和a n t i p i n 1 4 r l 也研究了一种类似于交叉规划模型的均衡规划 问题 在 1 4 8 中给出了显式交叉线性规划模型： ( ) ) m i n c 。z s t a x y o 0 ， ( q ( z ) ) m i nd r y s t b y o y 0 ， 1 4 西安电子科技大学博士论文：精确罚函数和交叉规划阅题的研究 其中。月“，y r ”，c ，d 是给定的向量，a ，b 是给定的矩阵。根据第2 节的讨 论，这个模型显然也是一个对策模型 在【1 4 8 】文中还给出了隐式交叉规划模型： ( p ( v ) ) r a i nv t x s 。t 。a z 0 ( q ( u ) ) r a i nu t y s t b y c y2 0 ， 其中z r ”，g r m ，c l d 是给定的向量，a ，b 是给定的矩阵。向量u 是问题 ( q ( u ) ) 的对偶问题的向量，向量u 是问题( q ( ”) ) 的对偶问题的向量 而后李荣生在他的博士论文“一般经济均衡与交叉数学规划问题” 1 4 9 1 中 对二入交叉规划问题进行了系统的讨论，得到了交叉规划的均衡解与一个互 补问题等价的结论，他讨论了交叉规划的经济背景来源于市场经济均衡问题 和企业产品生产问题，在他的博士论文中给出了相应的实际例子，指出了交叉 规划在解决产品合作开发和产品计划决策方面具有重要的作用和意义 下面是一种显式交叉规划的模型。设函数( u ， ，2 2 ) ：r p r q r “r 1 和 g ( u ，”，y ) ：彤r 口r ”- r 1 。考虑下面两个参数规划问题( 我们称为交叉规 划问题i n t e r a c t i o n a lp r o g r a m m i n gp r o b l e m ，简记i v p ) i “8 j ： p ( u ) q ( v ) ： s t m l n 5 c s t ( 。，奶x ，( “，v ，o ) ( u ，z ) u ( “) 9 ( ，口，y ) ( “，y ) 矿( u ) 其中疗( u ) cr 口r n ，“r p ，v ( v ) c 舻r m ， r q 。针对这种模型，1 9 9 9 年 李荣生和孟志青讨论了二人交叉规划模型联合最优解的存在性问题 1 5 0 - 1 5 1 】， 1 9 9 9 年李荣生、王剑敏和王丽君讨论了交叉规划与双层规划的经济背景差异 分析 1 5 2 ，2 0 0 2 年胡奇英和孟志青研究了一类二人合作交叉规划的s 一最优联合 解【1 5 “，并给出求解二人交叉规划的方法。 1 9 9 9 年刘家壮和马建华也研究了一类特殊的交叉规划【1 5 3 1 ，2 0 0 0 年他们 第一章绪论】5 研究了般交叉规划与经济均衡模型，提出了下面一般模型： ( 只( 。! 。) m h ，i ( z ! 。) s t g i ( x i ，。o 一 ) s0 ，。i x i ， 其中。t r “。是决策变量，f ! ：= ( 尘1 ，- ，瓢山z 。+ l ，z m j r n j 月札tx r ”一x r ”m 是参数，他们研究了交叉规划均衡解的存在性，2 0 0 1 年他们 研究了上面定义的一般交叉规划与双层规划之间的联系f 1 5 4 。 从上面已研究的交叉规划模型来看，交叉规划的模型来源于数学规划、对 策论和群体决策等问题的模型，是非线性规划。对策论和群体决策的推广，它 主要研究具有相互作用的决策问题，这种问题可以是对抗性的或没有对抗性 的或部分对抗性的。 l4 本文研究内容 我们的论文研究主要包括了两个部分，一个是精确罚函数部分，另一个是 交叉规划问题部分 我们将分七章来论述。精确罚函数部分分为五章。第二、三章研究单目标 规划的双参数罚函数。第四章研究单目标规划的两种单参数的罚函数，第五章 研究多目标规划的罚函数，第六章研究集值向量优化问题的罚函数交叉规 划问题我们放在第七章中进行研究。而论文的第八章研究罚函数的应用，包 括在交叉规戈1 j 中的应用。本文以精确罚函数和交叉规赳为主线，按不露同题 的罚函数研究来展开的 下面对本文的各章研究内容做一简介 第一章介绍了与本文相关的内容，主要目的是给出本文研究的来源，与本 文研究有关的罚函数与交叉规划的研究进展。 第二翥对于含不等式约束的优化阍题 p ，我们弓 入了一个双参数懿罚函 数，这种罚函数与传统的单参数罚函数不同，推广了文f 2 5 - 3 0 1i , - j - i 仑的目标罚 函数形式。在一定的条件下，我们将证明这种罚函数的一个重要结果，即不仅 证明一个无约束罚垅 二问题的最优解也是原优化问题的最优解，而且与传统 1 6 西安电子科技大学博士论文：精确罚函数和交叉规划问题的研究 的精确罚定理的结果不同是，还确定了最优目标值与目标罚参数值之间的关 系，基于这个结果。提出了一个求解原问题最优解的双参数罚函数算法，并证 明了算法的收敛性。所作的数值实验说明了算法的有效性。 第二章的结果为后面几章的研究打下基础，由于这一章研究的是双参数罚 函数的通用形式，所以得到的结论具有一定的普遍性但一些结果还不够完 全，需要对双参数罚函数的特殊形式作进一步研究以便获得更好的结论因 此在第三章我们研究了二次l a g - r a n g e 双参数罚函数，它是双参数罚函数的特 殊形式之一我们在这一章所获得的关于精确罚定理、算法、以及收敛性等方 面的结果比第二章多，并且弥补了第二章研究的不足 第三章我们研究了二次l a g r a n g e 双参数罚函数与原优化问题的关系，在凸 性的条件下，证明了这种罚函数的与第二章不同的一个精确性结果。我们提 出求解这种罚函数对应优化问题的一个下降算法，并证明该算法的收敛性；然 后我们结合第二章的算法，给出一个改进算法，并证明改进算法的收敛性。最 后，使用改进算法进行数值计算。 第四章我们研究二次l a g r a n g e 罚函数更广泛的另一种形式，即n 次l a g r a n g e 罚函数近似光滑化方法，它是文 1 0 】研究的推广，对求解约束优化问题具有重 要作用。这一章我们也讨论了2 次l a g r a n g e 双参数罚函数，它是第三章的二 次l a g r a n g e 双参数罚函数更广泛的形式，但是随着女增大这种罚函数很难收 敛到最优解。本章的结果表明，对含约束罚参数的n 次l a g r a n g e 罚函数，a 值越小时对应的精确罚参数值也越小，所以在计算时，只需取较小的罚参数 就可能是精确罚参数值，这样可以求较小的罚优化问题而获得原问题的最优 解。当a 0 为实数) 仅含一 个约束罚参数。当0 0 当且仅当t 0 。 满足上述条件的函数非常多，例如：口( f ) = t 孔，p ( t ) = ( m “托o ) ) “，k = l ，2 ，- 2 1 ) 西安电子科技大学博士论文：精确罚函数和交叉规划问题的研究 _ 一 我们定义双参数罚函数： f ( t ，p ，m ) = q ( f o ( x ) 一m ) + p p ( ( z ) ) ， 2 ， 其中p 0 称为约束罚参数，m r 1 称为目标罚参数。 显然，上述的罚函数与传统的单参数罚函数形式不同，当m = 0 和q ( t ) = t 时。上述的罚函数即是传统番皇罚西数。 如果函数勺( t ) ，p ( t ) ， ( 。) ( z 0 ) u i ) 是可微的，那么罚函数f ( z m m ) 也是 可微的。例如，在以下的二例中，罚函数都是可微的，若取q ( t ) = t 2 ，p ( t ) = m a x t ，o 4 ，那么罚函数 f ( z ，p ，尬) = ( ，0 ( 。) 一m ) 2 + p p ( 。) 4 。 诓f 若取q ( t ) = p ，e ( t ) = m “旭d ) 2 ( k 是正整数) ，那么罚函数 f ( z ，p ，m ) = ( ，o ( z ) 一肘) 驰+ p 口( z ) 拈。 i e f 考虑下列无约束罚优化闫题： ( p ( p ，m ) ) m i n f ( z ，p ，财) ， s t z 矗“ 现在定义榜确罚函数的概念，传统的单参数精确罚函数满足的条件是，对 于某个罚参数p 对应的无约束罚优化问题的最优解也是原问题的最优解。 这里我们给出双参数罚函数的精确性概念，对于给定的罚参数m 和p ， 如果矿是罚问题( p ( p ，m ) ) 的最优解，那么。+ 也是问题( p ) 的最优解，则称 f ( r ? 吼m 1 是关于0 翘，鹋精确罚函数和是精确罚参数 显然，双参数精确罚的概念是单参数精确罚概念的推广如果我们能够找 到双精确罚参数，那么，我f f 丁只要求解对瘦的一个无约束罚优化闽题的最优解 就可以得到原问题的最优鳃， 下面我们研究用求解无约束最优化问题( p ( 岛吖) j 来代替求懈原约束不等 式优化问题( p ) 的问题。 2 2 精确罚定理 我们讨论有关双参数精确罚函数的几个定理 第二章双参数精确罚函数方法 定理2 2 1 如果。+ 是问题( p ) 的最优解，且m = n ( z + ) ，则对于任何p o , x + 是罚问题( p ( p ，m ) ) 的最优解，且f ( x + ，p ，m ) = 0 。 证明因为矿是问题( p ) 的最优解，m = ，0 如4 ) 那么f ( 。，p ，m ) = o 。而 对于任何z r n ，我们有f ( z ，p ，m ) 0 。所以，。+ 是罚问题( p ( p ，m ) ) 的最优 解， o 定理2 2 1 说明，当矿是问题( p ) 的最优解和m = f o ( x ) ，那么任何罚参数p 对应的无约束罚优化问题的最优解z ；一定使得f ( z ；，p ，m ) = f ( 。；，p ，f o ( x + ) ) = 0 ，0 ( z ；) = f o ( x + ) ，且。；是问题( p ) 的可行解，因此z ；也是问题( p ) 的最优 解，那么罚函数f ( z ，p ，m ) 是精确的。我们有下面更好的结果 定理2 2 2 设z + 是问题( p ) 的最优解，对某个p 0 和m ，z ；是罚 问题( p ( p ，m ) ) 的最优解且是问题( p ) 的可行锯，并且f ( 。；，p ，m ) 0 ，如果 m ，0 ( z + ) ，则。：也是问题( p ) 的最优解，即( 反掰) 是精确罚参数。 证明由定理所设，z ：是问题( p ( p ，m ) ) 的最优解，及问题( p ) 的可行解， 我们有 q ( ，0 ( z 一m ) = f ( 。刍p ，m ) sf ( x ，p ，m ) = q ( o ( z ) 一m ) ，妇x 如果我们能证明对任何。x 有，0 ( 。) 一m 0 ，0 ( 。；) 一m 0 ，由q 的定义 和上式知 ，0 ( 。：) f o ( z ) ，v z x 。 从而z ：也是问题( p ) 的最优解。因为ms ，0 ( 矿) ，且。；是问题( p ) 的可行解， 所以 f o ( 4 ) 一m ，( z ：) 一f o ( x 。) 2 0 。 假设存在。x 使得，0 ( z ) 一m 0 ，那么我们有，0 ( 。) 0 和m ，设z ；是罚问题( p ( n m ) ) 的最优解，则 ( i ) 若z ：是问题( p ) 的可行解且f ( z ：，p ，m ) = 0 ，则眠m m + 。 ( i i ) 若f ( z ；，p ，m ) 0 ，并且msm + ，则ms 尬。进而，如果z ；是问题 ( p ) 的可行解，则z ：是问题( p ) 的最优解 证明( j ) 结论显然成立。 ( i i ) 如果a 矗 m ，那么a 以 m m + ，因为南是连通紧集x 上的连续函 数，出引理2 2 2 知，存在现肖使得m = 矗) 。从而f ( x o ，n m ) = 0 但是， 因为z ；是罚问题( p ( p ，m ) ) 的最优解且，( 。；，p ，m ) 0 ，故0 f ( 。；，p ，m ) f ( 。o ，p ，m ) = 0 ，这是一个矛盾。因此我们有慨2m 。进而，如果正：是问题 ( p ) 的可行解，根据定理2 22 知z ：是问题( p ) 的最优解，口 下面给出一个双参数精确罚函数的例子。 例2 2 1 求解下面问题： ( p 2 2 1 ) s t 问题( p 2 2 1 ) 的最优解是( z 乱z ；) = ( 0 ，0 ) 。对应的最优目标值是0 定义下面 的罚函数： f ( z ，p ， 彳) = ( z + 王；一j 玎) 2 - + - p ( m a x o ，一z 1 ) 4 + m a x o ，一z 2 ) 4 ) 为了使得罚优化问题( p ( p ，m ) ) 得到最优解，求f ( z ，p m ) 的偏导数为零 两o f = 4 z t 暖+ z ；一m ) - 4 p 一 o ，- - e l 3 = 。 0 一 现 一0 遽 一 + 姐 一 第二章双参数精确罚函数方法 豢= 4 。2 ( z + z ；一m ) - 4 p m a x o ，吨) 3 = o ， 得解2 ；1 = 0 ，z 2 = 0 。然后再求f ( x ，p ，m ) 在( 。1 ，z 2 ) = ( 0 0 ) 的h e s s e 矩阵， ( 囊譬) = ( 一一如1 ( 盟筵竖2 ) = ( 一：“一：。，) a z l a 0 2a 2 0 l “刊 当m 0 ，根据定理2 2 2 知f ( x ，p ，m ) 是关于( p ，m ) 的精确罚函数。口 2 3 双参数精确罚函数算法 根据定理2 2 3 ，我们提出一个求解问题( p ) 全局最优解的一个算法。尽管已 经证明双参数罚函数在一定条件下是精确的，但我们并不知到精确罚参数的具 体值是多少，所以与已有传统精确罚函数算法一样。我们的算法思想仍然是通 过求解序列无约束双参数罚函数来获得原问题的解，不同的是通过改变目标罚 参数m 进行求解，最后算法的收敛性证明需要用到精确罚定理2 2 3 ，所以我们 把下面的算法称为双参数精确罚算法( t w o - p a r a m e t e r e x a c tp e n a l t ya l g o r i t h m ) 。 算法2 1 ( 双参数精确罚算法) s t e p1 ：给定值e 0 ，护x ，取a l 0 ，b 1 = ，( z o ) ，m = 9 虹； s t e p2 s t e p3 s t e p4 求罚问题粤娩f ( x ，p ，弧) 得到最优解扩 如果一不是问题( p ) 的可行解，则令6 k + 1 = b k o 1 = m k ，m k + 1 = 蚴峙2 “，转s t e p 5 否则，扩是问题( p ) 的可行解，转s t e p 4 如果f ( x 2 ，p m k ) = 0 ，令a k + l = a k ， b + 1 = 慨，m k + 1 = 蚴学，转s t e p 5 否则，f ( x k , p ，a 靠) 0 ，停止，