（运筹学与控制论专业论文）一个修正的罚函数方法.pdf

2 0 0 5 年上海大学硕士学位论文 摘要 现代科学、经济和工程的许多问题都有赖于相应的约束非线性规划问题的全 局最优解的计算技术，在过去的几十年里，求解非线性规划问题的方法已取得 了很大的发展。求解非线性规划问题的重要途径之一是把它转化为无约束问题求 解而罚函数方法是把约束问题转化为无约束问题的一种主要方法，它通过求解 一个或者一系列的无约束问题来求解原约束问题。本文的工作是对传统的罚函数 进行了改造，主要是引入了分式一二次函数，并在其中增添乘子参数，从而构造 了一个修正的罚函数我们用比较初等的方法证明了原问题和相应罚问题的全局 最优解之间的一种近似等价关系。然后我们对乘子参数进行了估计，给出了乘子 参数，罚参数与迭代点之间的关系，在此基础上设计了算法，数值试验表明所给 的方法是有效的。最后，我们研究了对偶问题，并给出了一个强对偶定理和鞍点 定理。 本文的结构如下：第一章，介绍相关的概念和罚函数的一般思想以及主要的 罚函数方法季玎一些结果第二章，我们给出了一个修正的罚函数，讨论了原问题 和相应的罚问题最优解之间的关系，给出了原问题的k k t 乘子与相应罚问题的 乘子参数问的近似关系以及乘子参数和罚参数与迭代点之间的关系。第三章，在 二阶最优性充分条件下，我们对原问题的最优解以及罚函数中的乘子进行了有效 的估计，并设计了一个对修正罚函数的简单算法，数值试验也表明我们给出的算 法是行之有效的第四章，我们讨论了对偶和鞍点的概念，然后证明了在二阶最 优性充分条件成立时基本的强对偶定理和鞍点定理。 关键词：非线性规划罚函数方法k k t 乘子对偶定理 2 0 0 5 年上海大学硕士学位论文 i i a b s t r a c t m a n yp r o b r o 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 lr e l yo nn u m e r i c g t e c h n i q u e s f 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 i n m i n gp r o b l e md 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 ya 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 gc l u e t ot h ei m 一 1 3 0 1r a n tp r a c t i a la p p l i c a t i o n s o n eo ft h ei m p o r t a n ta p p r o c h f o rs o l v i n gc o n s t r a i n e c l n 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 s l t yf u n c t i o n m e t h o d sa r ep r a v m l i n gt 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 kt oo b t a i nt h es o l u 。 t i o no 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 nt h i sp a p e r ，am o d i f i e dp e n a l t yf u c t i o nm e t h o di sg i v e n 、t o g e t h e rw i t ht h ea l g o r i t h ma n dn u m b e r i c a le x p e r i m e n t w ea l s od i s c u s st h ed u a lp r o b l e ma n dp r o o ft h e c t h eb a s i cd u a l i t yt h e o r e mr e n l a i n st r u eu n d e rt h es e c o n d o r d e rs u f f i c i e n tc o n d i t i o n s 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 e r1 w eg i v eab r i e fh l t r o d u c t i o nt ot h ei d e aa n dc o n c e p to ft h ep e n a l t yf u n c t i o n i nc h a p e r2 am o d i f i e d p e n a l t yi sg i v e n w i t hw h i c hac 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 mi s c o n v e r t e di n t oa uu n c o n s t r a i n e dp r o b l e mw ed i s c u s st h er e l a t i o no fl o c a ia n dg l o b a l o p t i m a ls o l u t i o n sb e t w e e np r i m a lp r o b l e ma n dc o r r e s p o n d i n gp e n a l t yp r o b l e m ，a n d g i v ear e l a t i o nb e t w e e nm u l t i p l i e rp a r a m e t e r sa n dp e n a l t yp a r m n e t e r sw i t hi t e r a t i o np o i n t s i nc h a p e r3 ，w ep r o o ft h a tu n d e rt h es e c o n d o r d e rs u f f i c i e n tc o n d i t i o n s a n dp e n a l t yp a r a m e t e rb e i n gl a r g ee n o u g h ，t h ea l g o r i t h mi sc o n v e r g e n t w ea l s og i v es s i m p l ea l g o r i t h m ，n u m e r i c a le x p e r i m e n ts h o wt h i sm e t h o di se f f e c t i v e i nc h a p e r4 ，w e d i s c u s st h ec o n c e p t i o no fd u a la n ds a d d l ep o i n t ，t h e nw ep r o v et h a t t h ed u a lp r o b l e mb a s e do nt h em o d i f i e dp e n a l t yf u n c t i o n ，i ft h es e c o n d o r d e rs u f f i c i e n tc o n d i t i o n s h o l d ，t h e nt h eb a s i cd u a l i t yt h e o r e mr e m a i n st r u e ，w h i c hi sn o tt r u ef o rn o n c o n v e x p r o g r a m m i n g 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 ，k k tm u l t i p l i e r s ， d u a lp r o b l e m s 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 酪绷啉耐乒，7 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留 论文及迭交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容。( 保密的论文在解密后应遵守此规定) 签名 别程各麟嗍2 w b t fu 2 0 0 5 年上海大学硕士学位论文 5 11 问题的阐述 第一章前言 最优化理论和方法是一个重要的数学分支，它所研究的问题是讨论在众多的 可行的答案中如何找出最优者。最优化理论的研究虽然在上世纪四十年代，即二 次世界大战时期才开始，然而，今天它已经得到广泛的应用，工程设计、金融工 程、社会保险、交通网络、图形和图象处理、分子生物学、环境工程、集成电路设 计、数据处理、国民经济管理和生产管理等等，它的应用几乎涉及人类生活各方 面。随着科学技术的迅猛发展，特别是计算机技术越来越广泛的应用到社会生活 的各个方面，最优化理论的应用范围会进一步扩大，在社会生产和社会服务中发 挥越来越大的作用。 最优化理论和方法的内容是相当丰富的，本文主要研究的是应用罚函数方法 来解决优化问题。其主要思想是利用罚函数把有约束的问题转化为无约束的问题， 其中罚函数的选择和构造是一个关键的问题本文将致力这方面的研究。 考虑如下的约束非线性规划问题； ( p ) m i n，( z ) 侪( o ) 0 ，i = 1 ，2 ，一一，m z x 其中，( z ) ，吼( 。) ，i = 1 ，2 ，m 是定义在r - 上的非线性连续可微函数，x 是 只n 的子集，z 是n 维向量。这里，f ( x ) 称为目标函数，肼( z ) ，i = 1 ，2 ，m 是不 等式约束函数。 集合 s = 。x ：g i ( z ) 0 ，i = 1 ，2 ，m ) 表示为问题( p ) 的可行域s 中的点称为问题( p ) 的可行点。 设矿s ，若存在矿的邻域 o ( x ，6 ) = z ：忙一矿l l 0 i = 1 2 - ， 定理1 2 2 ( - - 阶必要条件 5 】) 设在问题( p ) 中，( z ) ，吼( z ) 0 = l ，2 ，m ) 在 r ，；上二次可微，z + 局部极小点，l a g r a n g e 函数在z + 的h e s s i a n 矩阵为 v ：。l ( + ，a + ) = v 2 ，( 茁+ ) 十n v 2 肌( z + ) 2 “z + ) 其中v 2 ，( z + ) 和v 2 9 ( 矿) ，i i ( x + ) 分别是，g l ，i z ( 2 + ) 在矿的h e s s i a n 矩阵。 定理1 2 3 ( - 阶最优性充分条件 5 ) 设在问题( p ) 中，( 。) ，历( z ) ( 扛1 ，2 ，m ) 在口上二次可微，z + 为k k t 点，并且n 为l a g r m l g e 乘子，记 j 十= i j ( z + ) i ： o ) ，j o = i j ( 。+ ) l a ；= 0 ) l ( x ) 在矿的h e s s i a n 矩阵为 v ：。工( z + ， + ) = 审2 ，( z + ) + e ；v 2 9 ；( z + ) t j 佃) 其中，v 2 ，( 矿) 和v 2 玑( 一) 分别是 ，( z ) ，毋( z ) ( # l ，2 ，m ) 在z + 的h e s s i a n 矩阵定义锥 c = _ p ：z t g ( x ) r p = 0 ，i j + ；v g ( x + ) t p 茎0 ，i i o ) 2 0 0 5 年上海大学硬士学位论文 4 如果坳c ，都有 则。+ 是问题( p ) 严格的局部极小点。 在本文里，我们使用一个更强的二阶充分条件，它保证局部极小点是孤立的 局部极小点，即存在一个邻域，在这个邻域里，它是唯一的极小点。 定理1 2 4 ( 标准二阶最优性充分条件【1 ) 设在问题( p ) 中， ”，、) 肼( 。：) ( i = 1 ，2 ，一，m ) 在r n 上二次可微，z + 为k k t 点，并且n 为l a g r a n g e 乘子，记 l ( x ) 在z + 的h e s s i a n 矩阵为 v ：。l ( x 4 ，”) = v 2 ，( 。+ ) + n v 2 9 i ( x 4 ) i e ( x + ) 其中，v 2 ( x + ) 和v 2 9 。( 。+ ) 分别是，( z ) ，吼( z ) ( i = 1 ，2 ，m ) 在z + 的h e s s i a n 矩阵。 如果满足条件c 1 一c 3 ： c 1 梯度v 肌( z + ) ，i = 1 ，2 ，m 线性独立；因此存在唯一的l a g r a n g e 乘子使 得 r v 。工( 矿，”) = v ( x + ) + w v 吼( 筑) = 0 t = 1 c 2 l ( x ，a ) 的关于x 的h e s s i a n 矩阵 r v ：。l ( x ， ) 4 = v 2 ，( z + ) + w v 2 ( ) t = 1 在可行切锥子空间上正定；也就是 任意的y y c 彤，这里 9 7 v ：。l ( x + ，a + ) f 0 y = y ：y t v g i ( z + ) = 0 ，i = 1 ，2 ，r ) c 3 强互补条件成立，即 砖肌扛+ ) = 0 ，i = 1 ，2 ，一，m 2 0 0 5 年上海大学硕士学位论文 5 a + 0 ，i = 1 ，2 ， ) r ；g i ( z + ) 0 ：i = r + 1 ，m 那么，z + 是一个孤立的局部极小点。 定义1 2 1 ( 局部收敛性) 设z + 是问题( p ) 的解，如果存在。+ 的一个邻域 o ( x + ，6 ) ，6 0 ，对任意初始点z o ( x 4 ，6 ) ，由算法产生的点列p k ) ，总有 l i r az k = z + 成立，则称算法是局部收敛的。 e + 定义1 2 ，2 ( 全局收敛性) 设z + 是问题( p ) 的饵，如果在任意初始点z r “， 由算法产生的点列 z k ) ，总有1 i m 。k = 矿成立，则称算法是全局收敛的。 5 1 3 罚函数方法 考虑问题 ( p ) h ( z ) = 0 ，i = 1 ，2 ，- ，r 罚函数方法的基本思想就是把上述约束问题转化成无约束问题来求解，方法 是在目标函数上加上一个或多个与约束函数有关的函数，而删去约束条件，把上 述问题变换为如下形式： mr ( 国)m i n q ( x ，a ，“k ) = ，( z ) + 入k 咖【吼洳) + p k 币【恤) i = l j = l 其中，咖( g ) ，妒( f ) 为连续函数，且满足毋( ) = 0 ，y50 且( ) 0 ，y 0 和 妒( ) = 0 ，y = 0 且妒( g ) 0 ，y 0 ，而k ，肌为罚因子，q ( x ，h ，肌) 称为罚函数。 对确定的取值a h ，卢= p k ，罚问题是一个无约束问题；若取一系列的 h ，肛，= 1 ，2 ，h ，卢t + o 。，则是一系列的无约束问题。这样，原问题的求解 就转化为一个或一系列的无约束问题的求解。 用罚函数方法来解约束优化问题通常认为最早由c o u r a z ，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 k1 4 9 在利用罚函数方法，即系列无约束极小化方法做 了不少工作，并总结为s u m t 方法。 m 一一 0 称为罚参数，p ( z ) 满足： 1 p ( z ) 在r “上连续； 2 p ( 。) 0 ，v z r ”； 3 p ( z ) = 0 的充要条件是 z s = 茁：鼠( 。) s0 ，i = 1 ，2 ，m i ，k ( 茁) = 0 ，i = l ，2 ，r ) 例如对问题，下面的函数是符合要求的 mt p ( 。) = m a z ( o 舰( 。) ) 】2 + i h j ( 。) 1 2 # 1 ，2 1 显然，这里的指数2 可以换为其它正整数。 一般来说，无约束问题 ( ) 暇m ) + 艘( z ) 随着p 的增加，p ( z ) 在可行域之外会变得很大，迫使q 。的解落在可行域或 靠近可行域，当芦一o 。时，问题( 吼) 的解应该趋于可行域， 设q ( p ) = i n f ( f ( x ) 4 - 即( 。) ：z x ) ，我们有如下的结论： 定理1 3 1 设，( z ) ，吼( z ) ，t = l ，2 ，m ；( z ) ，i = 1 ，2 ，r ，是兄”上的连续函 数，x 为冗”中一个非空集合，p ( 。) 是罚函数，如果对任何卢 0 ，存在一点 。x ，使得 q ( p ) = f ( x p ) + 巾( z 。) = i n f f ( x ) + 印( 。) ：z 。y ) ， 那么下面的结论成立： 1 i u f f ( z ) l g i ( x ) s0 ，i = l ，2 ，一，仇；堍 ) = 0 ，i = 1 ，2 ，- ，r i z 彳 2s u p q ( f ) 2 f ( x p ) 是关于卢的单调不减函数，q ( p ) 是关于p 的单调不减函数，p ( ) 是芦 单调不增函数 定理1 3 ，2 设，( z ) ，吼( z ) ，i = 1 ，2 ，m ；( z ) ，i = l ，2 ，_ 是r “上的连续函 数，x 为咒”中一个非空集合，设问题( 户) 至少有一个可行解，p ( z ) 是罚函数， 2 0 0 5 年上海大学硕士学位论文 如果对任何p 0 ，存在一点z 。x ，使得 q ( “) = f ( x p ) 4 - 舢p ( z p ) = 1 1 f ，( z ) + 巾( z ) ：z x ) 并且所有的z 。包含在x 的紧子集里，那么成立： 1 i n f f ( x ) 1 9 。( z ) 0 ，i = 1 ，2 ，：m ； z ( 。) = 0 ，i = 1 ，2 ，。，r ；z x ) 。嬲q ( p ) 。恕q ( 肛) ； 2 z 。) 的任何收敛子列的极限点是原问题( 户) 的一个最优解； 3 l i l p ”尸( j _ ) = 0 1 _ 0 0 显然，如果对某个肛成立p ( x 。) = 0 ，那么z 。是原问题( p ) 的最优解。 从上面的结论可以看出，当取罚参数p 充分大时，罚问题的解可以任意逼近 原问题的解。但是，随着的p 增大，f ( x 。) 4 - g 。p ( x p ) 的h e s s i a n 阵趋于病态而导致计 算困难，因此用无约束方法来解m i n f ( x ) 十肛p ( z ) 时，其收敛速度很慢，用s u m t 方法来解原问题的计算量是比较大的。因此，产生了求解约束非线性规划的一些 改进的罚函数方法。 精确罚函数方法 精确罚函数的概念首先是和在上世纪六十年代后期提出，这是线性规划中大 法在非线性规划中的自然推广。从那时起，精确罚函数一直在数学规划理论和方 法中扮演很重要的角色【2 6 - 3 5 】。 考虑问题 精确罚函数是用形如。r a i x n i f ( z ) + p e ( z ) 的无约束问题( 昂) 来替代问题( p ) 其中肛为参数，e ( 。) 是x 到r 上的函数，且满足 1 e ( x ) 0 ，v z x ； 2 e ( x ) _ 0 的充要条件是z s ，这里s = z ：吼( z ) 0 ，i = l ，2 ，m ，a j x ) m21 1 | 0 琏x 忙 玑 o s 2 0 0 5 年上海大学硕士学位论文 8 定义1 3 1 若存在p o 0 ，当芦 枷时是得问题( 只。) 的解是问题( p ) 的解 或问题( p ) 的解是问题( r ) 的解，则称 为问题( p ) 的精确罚函数。这里的解可以是局部最优解，也可以是全局最优解。 精确罚函数概念首先由e r e m i n 1 2 】和z a ，g w i l l 1 3 】于上世纪六十年代后期提 出。这是线性规划中大m 法在非线性规划中的自然推广。从那时候起，精确罚函 数一直在数学规划理论与方法中扮演很重要的角色。【1 4 3 0 】 下面我们介绍发展最为成熟的2 - 精确罚函数方法的主要结果，设原问题( p ) 中集合x 为开集，取罚函数的指数为l ，的罚问题 ( 哦) 恕他) + 肛( 三一( z ) ) + 简i h a z ) 1 ) 我们称 尸1 ( z ，肛) = ，( 。) + p ( m a x o ，吼( z ) ) + i h j ( x ) ) i = 1j = 1 为1 1 精确罚函数，f 。精确罚函数又称为经典精确罚函数。 定理1 3 3 【1 】设矿为问题( p ) 的k - k t 点，( “+ ，u + ) 为与z + 相应的k k t 乘 子，进一步，设，( z ) ，仇( z ) ，i i o ( x + ) = 0 ：g i ( x + ) = 0 ，i = l ，2 ，m 是凸函数，而 且h i ( x ) ，= 1 ，2 ，r 是仿射函数，则对肛m a x 鹰，i i o ( x + ) ，喵，j = 1 ，2 ，r ) ， z + 也是问题( 兑) 的解 定理1 3 4 设z + 为问题( p ) 的一个严格局部极小点，( ) ，吼( z ) ，i = 1 ，2 ，m ， 锄( z ) ，j = l ，2 ，r 在的一个邻域内连续可微，进一步，设矿满足m a n g a s a r i a n f r o m o v i t z 约束品性，那么，存在旷，使得当p 肛+ 时，。+ 是问题( 磁) 的局部 极小点。 定理1 3 5 如果定理1 2 3 的条件成立，则对任何满足 p m “ 瞄，i i o ( x + ) ，嵋，j = 1 ，2 ，r ) 的罚参数肛，矿是罚问题( 墨) 的严格局 部极小点 2 0 0 5 年上海大学硕士学位论文 9 在算法上，使用精确罚函数的历史已经很长，它的优点是原问题不必转化为 无限个无约束问题，只需要有限个，甚至一个就够了。但是由于经典精确罚函数 不是可微的，从算法的角度来看，这种不可微性能引起所谓的“m a r a t o s 效应”， 即引起阻止快速局部收敛的现象。 乘子罚函数方法 t s e n g 在文 9 1 中构造了一个改进的指数型乘子罚函数，分析了极小化凸规划 问题的乘子指数型方法和对偶情况，并给出了一种熵极小化算法，丽且强化了方 法的有效收敛结果。在应用到线性问题时，给出了收敛速度。 在上世纪9 0 年代，乘子罚函数是罚函数方法中非常活跃的研究领域f 7 一1 5 乘子罚函数的基本思想是在罚参数之外，还引入参数作为乘子的近似值来调节计 算，达到快速准确的目的。 考虑非线性规划问题： ( r )r a i n ，( z ) s t 吼 ) 0 ，i = 1 ，2 ，一，m 假设其最优解集非空且有界，即扣：f ( x ) 0 其算法有下面的两式给出 i = 1 伽躲饥卅薹譬峋蝴 伊1 = 砖e 亏。i ( 。“，j 其中，心 0 相当于第j 个约束的乘子， 1 ，2 ，一，m 勺 0 是罚参数。当，( 。) ，乳( z ) ，j 1 ，2 ，m 为凸函数时，利用对偶可以求出妒的共轭函数 且有如下k k t 最优条件 妙4 = s i ns s + 1 0 a ，( ) + 心+ 1 0 9 l ( z ) 2 0 0 5 年上海大学硕士学位论文 l o 及 这里 0e 毋d ( 芦2 + 1 ) v 妒+ ( 琦“t - j ) c d ( p ) + 瓣) + 蚤岫( z ) ) 障碍函数方法 和罚函数相似，障碍函数也可以把约束问题转化为一个或者一系列的无约束 问题。障碍函数为可行域设置了障碍，使无约束问题的解不能离开可行域。如果 最优点在可行域的边界，那么，系列无约束问题的解从可行域的内部逼近它因 此，障碍函数方法也称为是内罚函数方法。 考虑非线性规划问题： 障碍问题是 s t 9 i ) 0 ，i = 1 ，2 ，一，m z x ( 兄) m i n 日( p ) s t “ 0 这里，口( p ) = i n f ，( z ) + 肛b ( z ) ：仇( z ) so ，i = l ，2 ，m ，z 柳，b ( x ) 是障碍函 数，在域 z ：9 l ( z ) o ，i = 1 ，2 ，m ) 上是非负的连续函数，当z 趋近 ( 。：吼( z ) o ，i = 1 1 2 ，m ) 的边界时，b ( 。) 趋近+ 。 我们可以这样定义障碍函数： b ( z ) = 妒b ( 。) 2 0 0 5 年上海大学硕士学位论文 这里，是单变量函数，且满足 y 0 时，西妇) 0 ，且l i l 9 曲 ) = + 。 典型的障碍函数是下面的形式： b ( z ) 5 萎丽- i 或者 m b ( z ) = 一1 n 卜9 。( z ) 】_ z = 1 利用障碍函数，如果我们从可行域的一个内点，那么就可以在可性域里达到 最优点。我们有下面的结论。 定理1 3 6 设，( 。) ，吼( z ) ，i = 1 ，2 ，m 是r “上的连续函数，x 为r “中一个 非空闭集合，若集合和x ：肌( 。) 0 ，如果 z k ) cx 满足g ( x k ) 0 ，存在z 。x ，g ( x 。) 0 使得 o o , ) = ，( z “) + , u b ( x “) = i n f f ( x ) + p b ( z ) ：甄( 。) 一1 ，妒7 0 ) o ( o p ) r a i n q 扛， ，p ) = ，扫) + ；凡妒( p 取( z ) ，l = l 这里p 0 凡0 ，= 1 ，2 ，- ，m 我们用g ( ) 和l ( t ) 分别表示问题( ) 的全局极小点和局部极小点。 本文给出的修正的精确罚函数与文f 1 所研究的函数不同，我们首先用比较初 等的方法研究了原问题和相应的罚问题的全局最优解的近似等价性，然后证明在 等的方法研究了原问题和相应的罚问题的全局最优解的近似等价性，然后证明在 2 0 0 5 年上海大学硕士学位论文 1 2 第二章修正的罚函数方法 2l 引人 考虑如下的非线性规划问题： r a i n f ( x ) s t z ( z 冗”：吼( z ) s0 ，i = 1 ，2 ，m ) 其中，( z ) 和吼( z ) ，i = 1 ，2 ，m 是二次连续可微函数，假设，( z ) 具有下面的性质 l 齿m ) = 佃 所以存在一个有界闭箱x ( 自然也是紧集) ，使得i n t x 包含f ( x ) 的全局极小点。 本文中我们考虑上面问题的等价问题； ( p ) r a i n f ( x ) s t # s = 。x ：g i ( x ) 0 ，i = l ，2 ，m ) 引入函数 ，= 憎圳t o 显然，妒( t ) 是二次连续可微的单调凸函数，且具有下面的性质： v ( o ) = 0 ，( o ) = l ，妒”( o ) = 2 ，v t r 妒0 ) 一1 ，妒7 ( t ) 0 ( o 却) m i a q ( x ， ，p ) = ，( z ) + 妒( p 仇 ) ) ，i = l 这里p 0 ，凡0 ，t = 1 ，2 ，m 我们用g ( ) 和l ( ) 分别表示问题( ) 的全局极小点和局部极小点。 本文给出的修正的精确罚函数与文【1 】所研究的函数不同，我们首先用比较初 等的方法研究了原问题和相应的罚问题的全局最优解的近似等价性，然后证明在 2 0 0 5 年上海大学硕士学位论文 1 3 满足二阶充分条件，罚参数足够大时，原问题的局部极小值点是相应的罚问题的 严格局部极小值点。此外我们还给出了原问题的k k t 乘子和光滑精确罚函数中 的乘子参数间的关系。最后，我们给出了一个简单的算法和两个算例来说明所给 方法的有效性。 2 2 主要结论 下面我们证明主要的定理。 定理2 2 1 若g ( p ) ci n t x ，g ( p ) 十e b ( 日，1 ) i n t x ，其中 0 ，u ( o ，1 ) = t r ”：i o ，t = 1 ，2 ，m ， 这里z + g ( p ) ，0 e 1 e ， o 。( 即。日( 躜舄( p ) 瑚( ) ) m ) 一m 4 ) ) ， o f ( x + ) 成立。因为s ( g ( p ) + s b ( o ，1 ) ) 是紧集，( z ) 连续，所以存在 8 l 0 且5 l 0 ，使得z ( s + e , b ( o ，1 ) ) ( g ( p ) + b ( 日，1 ) ) 时，成立l ( x ) l ( x + ) + r 。，此外，m a x 9 l ( z ) ，9 2 ( 。) ，g m ( z ) ) 是连续函数，且x ( s + e l b ( o ，1 ) ) 是紧集，所以成立 喇( 踏聊) ) m “x 9 1 ( 2 ) 胁( 。) ，( 。) ) g i o ( x i o ) o 下面把。分为两种情况： ( 1 ) z ( s + e a b ( o ，1 ) ) ( a ( p ) + s b ( o ，1 ) ) 时 q ( z ，a ，p ) = m ) + 九妒t ( 。) ) t = l ，( 矿) + 一：九 2 0 0 5 年上海大学硕士学位论文 ( 2 ) z x ( s + 1 b ( e ，1 ) ) ，这时z 是不可行点，从而m n 。 9 1 ( z ) ，9 。，( z ) ) = g j ( x ) g i o ( z ，o ) 0 q 扛，a ，p ) = ，( z ) + p i f = l 丸妒函毋( z ) ) 一m 一；p + c o ” 一m 一雅。，+ ，( m 。( z 。) 十工峥未( 。o ) ) 一m 一僵。十( m + ，( 茁+ ) + 傩e ，) = m 弛m ；p 妒( z 刊矿，椰) 所以在定理的条件满足时，对所有z x ( g ( p ) 十e b ( e ，1 ) ) ，成立 q ( z + ，a ，p ) 一 一 = 2 0 0 5 年上海大学硕士学位论文 v f ( x + ) + 舛v m ( z + ) = 0 i l ( z ，) 所以，z + i n t x 是( 0 蛔) 稳定点 引理p 和q 是两个对称矩阵，q 是半正定的，p 在q 的零空间上是正定 的，即当z 0 且q z = 0 时z 7 p x 0 则存在正数e ，使得当c e 时，p + c q 足正定的。( 罔) 定理2 2 3 若z + l ( p ) ni n t x ，并且标准二阶最优性充分条件在2 j + 成立 k k t 乘子n ，i = 1 ，2 ，一，m ，严格互补，即 y y = ye 钟：y t v g i ( x + ) = 0 ，0 ，i i ( x 4 ) ) 时r ( v 2 f ( z + ) + a ；v 2 9 。( + ) ) g 0 ，且a ： 0 ，i i ( x + ) ， i e i ( + ) 则令凡= n ，i = 1 ，2 ，m ，当p 充分大时，z + el ( q 却) 。 证明因为 q ( 。， ，p ) = ，( 。) + 争p ( p g i ( z ) ) t - = 1 。 m x 7 。q ( x ，a ，p ) = v ，( 。) + 九( 姗( z ) ) v m ( z ) i = 1 又因对= 0 ，igj ( 矿) ，妒即) = 1 ，所以 并且 v 。q 扛+ ，a + ，p ) = v ，扛+ ) + 碍妒( p 肼( z + ) ) v 肼扛+ ) t e l ( z + ) = v f ( x 4 ) + n v 肌( 。+ ) = 0 t j ( z ) v ：。q ( z ，a ，p ) = v 2 ，( 。) + 九【妒7 ( p 优( 。) ) v 2 9 i ( x ) + p c f l ”( p g i ( x ) ) v g i ( x ) v t 仇( 。) i = 1 v ：。o ( z + ，a ，p ) = v 2 f ( x + ) + a ；v 2 9 i ( x + ) + a ；p 妒”( o ) v g 。( 搿+ ) v 了1 卯( 。4 ) j ( )i e l ( x + ) 因为 2 0 0 5 年上海大学硕士学位论文 16 v 2 ，( ) + n v 2 9 i ( x 4 ) i e i ( x + ) 在y = g ：y t v g ( x + ) = 0 ，y 0 ) 上是正定的， v g ( x + ) v 7 肌( z + ) 是半正定的， 妒”( o ) = 2 ，n 0 ，i j ( z 8 ) ，由引理可知，当p 充分大时v ：，q ( x + ，a + p ) 正定。所 以z + 是q ( z ，”，p ) 的严格局部极小点，即z + l ( q 却) 定理2 2 4 如果z 如g ( q 押) n i n t x ，z 4 g ( p ) ，p 和九 0 ，i = 1 ，2 ， ，m 满 足定理21 的条件，并且v g i ( x + ) 0 i ( x 4 ) ) 线性无关，则 v ，( z j p ) + 凡v m ( z 知) 圭日， i e l ( x + ) 这里元= k 妒7 ( p 肌( 。k ) ) 圭k ，z 知是( p ) 的近似的k k t 点。 证明根据定理2 2 1 有g 旧加) ca ( p ) + e 口( p ，1 ) ，当p 和九，i = 1 ，2 ，一，m 满足 定理2 1 的条件，e 充分小时，则有z + g ( p ) ，使得1 1 一。+ 8 茎，且 v ，( 知) 圭v ，净+ ) ，v 吼( z 知) 圭v g i ( x 4 ) ，肌( z 知) 圭肌0 + ) 记扛知) = ( i = l ，2 ，m ：仇( z k ) 圭o ) ，当i ，( z + ) 时，吼( 卫知) 圭9 z ( z + ) 圭0 ，当 ig ，( z + ) 时， g l ( z k ) ：= 吼( z + ) 0 ，i = 1 ，2 ，r ；m ( o + ) 0 ，z = r4 - 1 ，一，m 我们把问题( p ) 用函数妒( 。) 转化为等价问题，妒( 。) 有下面的性质 ( 妒o ) 妒是单调增加的c 2 类函数，定义域d o m ( c i o ) = ( 一o 。，+ 。) ， ( 妒1 ) _ p ( o ) = 0 ， ( 妒2 ) 妒( o ) = 1 ， ( 妒3 ) 当t 0 固定又充分大，我们可以解( p ) 从任意的初始 点( 。a ) 解的过程如下，假定无约束问题的解i = i ( a ， ) 存在 则有 1 v 。f ( 圣， ，忌) = v ，( t ) 十k 妒7 ( 惫吼( z ) v 肌( 圣) ) = 0 l = l 用下面的公式来更新a 可以写成 k = 九妒7 ( k g 。( z ) ) i = 1 ，2 ，m v 。f ( 2 ，i ，) = i t v 吼( ) ) = v 。l i ) _ 0 然后，用i 代替a ，把k 也更新，就完成一次迭代。不断重复这一过程，可 以得到一系列的( 。竹，h ) ，它们收敛于( ， + ) ，z + 是原问题的最优解， a + 是点 x + 的k k t 乘子。事实上a + 是对偶问题的最优解。 3 2 收敛性及其证明 引理p 和q 是两个对称矩阵，q 是半正定的，p 在q 的零空间上是正定 的，即当z 0 且q z = 0 时z ? p x 0 则存在正数，使得当c 三时，j p + ( ：q 是正定的。 定理3 2 1 假设二阶局部充分条件在点矿处成立，即c 1 ，c 2 ，c 3 满足那么 存在k o ，使得z + 是，( z ，”，k ) 孤立局部极小点。 证明因为 f 扛a 驴m ) + 蚤等蚶必) ) m v 。f ，a ，) = v ，) + 凡妒7 ( k 肼( z ) ) t = 1 而n = 0 ，i = r + 1 ，m ，妒( 0 ) = 1 ，所以 2 0 0 5 年上海大学硕士学位论文 2 1 rr v 。f ( x ， + ，) = v ，( z + ) + a i 妒7 ( k 吼( z + ) ) v 肌 4 ) = v f ( x + ) + a ：v 9