（应用数学专业论文）约束优化问题的若干算法研究.pdf

山东科技大学硕士学位论文 摘要 摘要 本文对非线性约束优化问题的一些理论与算法进行了研究。全文由四章组成，各章 的内容安排如下： 第一章主要介绍了约束优化算法的研究现状、发展方向，并指出了有待研究的课题。 第二章，详细分析了约束优化问题中常用的约束规范，如l i c q ，s m f c q ，m f c q ， c r c q ，c p l d 以及伪正规、拟正规和拟正则约束规范。讨论了它们与拉格朗日乘子的存 在性及其性质之间的关系，给出了各种约束规范之间的关系图。特别通过反例，说明了 w m f c q 在含等式约束的问题中不是一种约束规范。 第三章首先对不等式约束优化问题在退化与非退化情形下的两个广义投影梯度算 法，特别对采用的线性系统求迭代方向与采用直接公式求迭代方向的两种方法的共同性 进行了分析。在此基础上，给出了一般非线性约束优化问题在退化情况下的广义梯度投 影算法，在m f c q 下，证明了算法的全局收敛性。 第四章，借助于有效约束集的识别技术，给出了一个不等式约束优化问题的无严格 互补松弛条件的s q p 可行方法。该算法每次迭代只需求解一个规模较原问题要小的二次 规划和计算一次广义投影，从而简化了算法的结构，减少了计算量。无需严格互补性假 设，且在一个比强二阶充分性条件更弱的条件下，证明了算法的全局收敛性及局部超线 性收敛性。 关键词：非线性约束优化问题、s q p 算法、广义投影梯度、退化问题、序列线性方程组、 严格互补松弛条件、全局收敛性、超线性收敛性。 山东科技大学硕士学位论文 摘要 a b s t r a c t i nt h i sp a p e r , s o m en o n l i n e a rp r o g r a m m i n gt h e o r ya n da l g o r i t h m sa r ed i s c u s s e d t h e w h o l ep a p e ri sd i v i d e di n t of o u rp a r t s ，a n di ti so r g a n i z e da sf o l l o w s ： i nc h a p t e ro n e ，w eb r i e f l yi n t r o d u c et h eo r i g i na n dd e v e l o p m e n to ft h en o n l i n e a r o p t i m i z a t i o np r o b l e m s ，a n dt h e nw ep r o p o s et h ep r o b l e m s t h a tw i l lb ed i s c u s s e di nt h ef l l r t h e r r e s e a r c h i nc h a p t e rt w o ，w ea n a l y z es e v e r a lc o n s t r a i n tq u a l i f i c a t i o n si nc o n s t r a i n to p t i m i z a t i o n s u c ha sl i c q ，s m f c q ，m f c q ，c r c q ，c p l de t ci nd e t a i l t h e i rd e f i n i t i o n sa r el i s t e da n d t h ep r o p e r t yo fl a g r a n g em u l t i p l i e r su n d e rt h e s ec o n s t r a i n tq u a l i f i c a t i o n sa r ed i s c u s s e df o r e q u a l i t ya n di n e q u a l i t yc o n s t r a i n to p t i m i z a t i o n t h er e l a t i o n s h i pa m o n ga l l t h e s ec o n s t r a i n t q u a l i f i c a t i o n si sc o n c l u d e da n dar e l a t i o ng r a p hi sg i v e n m o r e o v e r , w ea l s os h o wt h a tt h e “w m f c q ”c o n d i t i o ni sn o tac o n s t r a i n tq u a l i f i c a t i o nb y ac o u n t e r e x a m p l e i nc h a p t e r f h r e e ，f i r s t ，w ea n a l y z et h eg e n e r a l i z e dg r a d i e n tp r o j e c t i o nm e t h o df o r n o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m su n d e rn o n - d e g e n e r a c ya n dd e g e n e r a cy t h e nw e g i v e ag e n e r a l i z e dg r a d i e n tp r o j e c t i o na l g o r i t h mf o rn o n l i n e a ri n e q u a l i t ya n de q u a l i t y c o n s t r a i n e do p t i m i z a t i o np r o b l e m su n d e rm f c q i i lt h ef o u r t hc h a p t e r , b yt h ea c c u r a t ea c t i v es e ti d e n t i f i c a t i o nt e c h n i q u ew ee s t a b l i s ha n e ws q pf e a s i b l ea l g o r i t h mf o rn o n l i n e a ri n e q u a l i t yc o n s 订a i n e do p t i m i z a t i o np r o b l e m s ，w h i l e t h es t r i c tc o m p l e m e n t a r ya s s u m p t i o ni sn e v e ri n v o k e d p e ri t e r a t i o n ，o n l yo n eq u a d r a t i c p r o b l e mo nas m a l l e rs c a l ea n dag e n e r a l i z e dg r a d i e n tp r o j e c t i o n n e e dt ob es o l v e da n d c o m p u t e d u n d e rt h ea s s u m p t i o n s ，w h i c hd o nn o tn e e dt h e s t r i c tc o m p l e m e n t a r ya n da r e w e a k e rt h a ns t r o n gs e c o n do r d e rc o n d i t i o n ，t h ea l g o r i t h mi sp r o v e dt ob eg l o b a l l ya n dl o c a l l y s u p e r l i n e a r l yc o n v e r g e n t k e y w o r d s ：n o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n ，s q pa l g o r i t h m ，g e n e r a l i z e dg r a d i e n t p r o j e c t i o n ，d e g e n e r a t ep r o b l e m s ，s s l e ，s t r i c tc o m p l e m e n t a r ya s s u m p t i o n ，g l o b a l c o n v e r g e n c e ，s u p e r l i n e a rc o n v e r g e n c e 1 1 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名：芬锌芹茚 日 期：盯。，0 a f f i r m a l l i o n id e c l a r et h a tt h i sd i s s e r t a t i o n ，s u b m i t t e di nf u l f i l l m e n to ft h er e q u i r e m e n tf o r t h ea w a r do fm a s t e ro fs c i e n c e ，i ns h a n d o n gu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y , i sw h o l l ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h ed o c u m e n th a sn o t b e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r e d a t e ： 矿节 艿估荔 盯 山东科技大学硕士学位论文 绪论 1 绪论 1 1 研究背景和意义 出于现代工程、经济管理和国防建设等方面的需要，非线性最优化问题作为运筹学 的一个分支在二十世纪四十年代开始形成。其所研究的内容包括模型创建、算法设计及 收敛性分析、数值试验等。由于非线性最优化问题特别注重算法的可计算性和实用性， 因而现在的非线性规划实质上是传统的运筹学与计算数学的交叉学科。 众所周知，目前求解非线性约束优化的最有效的方法之一是序列二次规划方法 ( s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ) ，亦称约束变尺度法，或s q p 算法，它自上世纪7 0 年代以来一直得到广泛研究。其迭代过程中的每步需求解一个或多个二次规划子问题， 然后引入步长线性搜索，在一定条件下具有全局收敛性和局部超线性收敛速度。一般地， 由于二次规划的求解难以利用原问题的稀疏性、对称性等良好特性，随着问题规模的扩 大，其计算量和所需的存储量非常庞大。另外，由于大规模二次规划问题的求解通常使 用迭代法，所需要解的精度越高，花费的时间就越多，稳定性也越差，而且二次规划子 问题有可能不相容，即子问题无解，从而导致算法的复杂度增加，理论证明不完善，这 就严重影响了序列二次规划算法的效率。针对上述问题，国际优化领域的许多学者开展 了序列线性方程组算法( 简称s s l e 或q p f r e e 算法) 的研究，试图用若干个线性方程 组代替二次子规划以求得迭代方向，在保证与序列二次规划算法具有相同收敛性质的前 提下，大大减少了每步的计算工作量，提高算法的稳定性。 从理论和实用的角度来看，传统的s q p 或s s l e 算法都存在两个主要问题。首先， 为了确保局部快速收敛性并防止m a r a t o s 效应，必须假设严格互补松弛条件( s t r i c t c o m p l e m e f l t a r i t ys l a c k n e s sc o n d i t i o n 简记为s c ) 成立，然而在一般情况下，该条件很难 检验。其次，求解等式和不等式约束优化问题的s q p 算法或s s l e 算法一般要求所有等 式和有效不等式约束的梯度向量线性无关，然而当等式约束个数多于两个或者总约束个 数超过空间维数时，该线性无关条件经常失效。这时，病态w a c h t e r b i e g l e r ( 参见【1 ) 现象就会发生。所以在无严格互补松弛条件或线性无关约束规范( l i n e a ri n d e p e n d e n t c o n s t r a i n e dq u a l i f i c a t i o n 简记为l i c q ) 下。建立s q v 、q p f r e e 或s s l e 算法具有十分 重要的意义。 山东科技大学硕士学垃论文 1 2 非线性约束优化问题模型及其基本概念 菲线性约束优化问题的模型来源于生产实践，现实生活中许多问题经过建模都可归 结为求解如下形式的数学模型( n l p ) ： r a i n f i x ) s f 毋( x ) s 0 ，i = 1 ，m ， g a x ) = o z = m + 】，m + p - 其中j = ( z ，z ：，z ) 7 r ”，郝j 是w 维列向量，( 柚，g ，o ) ，i = 1 , 2 ，- ，m + p 为x 的函 数，“是s a b j e c t t o 的缩写表示z 受不等式条件及等式条件的限制；f ( x ) 称为目标函 数。若m + p = o ，则称其为无约束优化问题，若m + p ，0 ，即若有不等式和，或等式约束 存在，则称为约束撮优化问题。若目标函数，( j ) 与约束函数g 。i x ) ，i = 1 ，i n + p ，都是线 性函数，则称之为线性规划问题，否则称之为非线性约柬优化问题。我们研究的对象主 要是非线性约束优化问题。 记x = 红f 毋( ) 0 ，f = 1 , 2 ，一，m ；g 。i x ) = 0 ，i = + 1 ，m + p ) ，称x 为上述非线性约 束优化问题的可行域。若x x ，则x 称为可行解。若对某一z t x ，存在常数 0 ， 使得对讥e x n 酬忙z 吲c s ，有，( z ) ，( 矿) ，则称j 为局部撮优解；若对一切，e x 都有- 厂( j ) - 厂( ，) ，则称x + 为全局最优解。 求解最优化问题( n l p ) ，就是要求目标函数，0 ) 在约束条件下的极小点，即求出其 全局最优解，但在一般情况f ，我们往往只能求出它的一个局部最优解。 一般说来，非线性约束优化问题比起线性规划无论从理论还是到算法的研究都要困 难些。不论何种情形，在讨论算法得到的点列( x 。 的收敛性及收敛速度时，都放宽到求 得问题的k k t 点。 我们称r ”为问题0 q l p ) 的个k k t 点，如果z x 且存在向量( 2 ，爿) r ”，使下 面的关系式成立： 可( x ) + w 。( z ) + 卢，码，( x ) ；0 ， 2 0 ， 晶( j ) = o ，i = 1 , - - - , m ： f = l m + l 其中，( ，卢) 称为拉格朗日乘子向量。在正规性假设下最优解必为k k t 点。 最优化问题的求解，通常用迭代算法。常用的迭代算法的基本格式包含两个主要步 最优化问题的求解，通常用迭代算法。常用的迭代算法的基本格式包含两个主要步 生奎型茎查兰堡主兰垒堡兰 堕堡 骤，即 1 、用某种方式确定当前点 ( k o ) 处的迭代方向d 。= d ( x 。) ， 2 、求出由_ 出发沿方向d 。的一维线搜索的步长吼，令j 。= x k + o r 。d 。 方向d 。的不同选择与初始点是否可行构成不同的算法及其分类。 如果迭代方向d 。= d ( x 。) 是通过求解一系列二次规划所得到的，称之为序列二次规 划( s q p ) 算法。 1 3 s o p 算法与投影类算法 1 3 1s q p 算法 拟牛顿算法是求解无约束优化问题最有效的算法之一，而序列二次规划方法是将拟 牛顿算法应用到求解约束优化问题的推广与发展，由于它保持了拟牛顿算法的超线性收 敛速度而备受人们的青睐。序列二次规划算法最早i 扫w i l s o n 于1 9 6 3 年在其博士论文 3 5 】 中提出，他证明在最优解的邻域内，算法具有二次收敛速度。但是w i l s o n 的算法存在许 多问题，例如，每步中的二次子规划的解可能不存在以及二次规划中的v 2 三( t ，丑) 不一 定正定等等。直到2 0 世纪7 0 年代，在h a r t s p ，p o w e l l m j d 等大批学者的研究与改进下， 序列二次规划方法获得了新的生命力。他们在w i l s o n 算法的基础上，将拟牛顿算法中关 于盈的修正公式加以推广用来代替v 2 l ( x k ，五) ，同时引入效益函数进行线搜索求步长 a ，从而建立了一个完整、实用、快速、有效的序y t - 次规划方法，这就是人们熟知的 著名的w i l s o n h a n p o w e l l 方法。随后的二十多年，对序列二次规划方法的研究进入了极 盛时期，新的成果不断涌现，从而使得s q p 算法成了求解约束优化问题的重要算法类。 序列二次规划算法的基本思想，就是对于任意一迭代点x 。，在处将约束函数( 工) 线性化，并以v f ( ) 7 d + d 7 b 。d 作为目标函数形成一个正定的二次规划q ( x i ，b k ) ，解 此二次规划求出方向t ，并沿方向破作一维线搜索( 精确的或非精确的) 求出步长q ，令 + 。= 札+ o r 。d 。再以也+ 。为新的初始点，修正b k 成为b + l ，使反+ 。保持正定性，构造 q ( x k + lb 。) 并解出d 。，重复上述计算过程a 若算法在有限步内得到巩= 0 ，n x 。为( n l p ) 的k k t 点；否则如果算法得到一个无穷点列 孔 ，则可以证明其任一极限点都是( n - l p ) 些查登垄查兰堡兰竺垦苎 堕堡 的k k t 点。序列二次规划算法的具体计算步骤如下： 算法1 1 序列二次规划( s q p ) 方法 给定初始点，初始矩阵b o ，k = 0 。 步骤l 对于任意的以，构造二次子规划o ( x ，风) ： m i n v f ( x t ) 7 d + d 7 b k d 占， g ( 工i ) + v g ，( ) 1 d 0 ，i ：1 ，。棚； g f ( j ) + v g f ( 上t ) 。d = 0 ， i = m + 1 ，一，小+ p 求解上述二次子规划q 。，b k ) 得解砍。- 若：d k = 0 ，停止， 为( n l p ) 的砌( t 点。 步骤2 沿方向破按某种方式作一维线搜索求步长，令x 。= + 口t d t 。 步骤3 修正统得反十l ，并使反+ 。保持正定。 步骤4 令k 等k + 1 ，转回步骤1 。 s q p 算法除了具有全局收敛性外，在一定条件下( 如严格互补松弛条件及线性独立约 束规范等) ，还具有局部超线性或二次收敛性质。 1 3 2 可行的s q p 算法 在许多实际问题中，由于一些客观环境的制约，往往要求所求得的解必须可行，有 些问题甚至要求算法每步迭代的点均要可行。为了解决这个问题，1 9 8 7 年e r p a n i e r 和 a l t i t s 2 7 1 给出了一个可行的序列二次规划算法，从而保证了算法的迭代总是在可行域内 进行，并且他们还证明了算法的全局收敛性和局部两步超线性收敛性。他们考虑的是不 等式约束优化问题( n p ) ： m i n f ( x ) s t g ，o ) 0 ，i = 1 , 2 ， 具体算法如下： 算法1 2 可行的序列二次规划( f s q p ) 方法 选取初始可行点x 。，初始阵h 。e ，以及m 0 ，a ( o ，专) ，卢( o 1 ) d 2 ，k 2 ， r ( 2 ，3 ) 。 步骤0 令k = 0 。 步骤1 计算搜索方向。 ( i ) 求解 c q 蹦芒g 拶i ( x 2 k 篇) 鬻d r 三0 ，i 乩2 ，mh f + ( ) 7 蔓，= 1 ， 得k k t 点司。如果d ? = o ，停止：若( q p o ) 无解或忙钏 m 或陋。d 刘 肛邓，转( i v ) 。 ( i i ) 求解 ，雕t 夏善嚣d 氛j f v ，i 乩2 ，协l 寞岛( t ) + 甲毋( ) 1 一l i | ， = 1 ，一，协 如果解以存在，令吼= v f ( x 。) 7 d 。；若( q p ) 无解或忙。8 肼或 0 。 m i n c - i i 1 1 0 ) ，弱有效不等式约束集为：i o ( x ) = ，o ) ，+ ( 工) 。 2 2 常用的约束规范的定义、性质与举例 首先让来回顾一下几种常见的约束规范。 定义2 1l i c q ( l i n e a r1 1 1 d 印e 1 1 d e n c ec o n s t r a i n tq u a l i f i c a t i o n ) ：称可行点工满足 这个约束规范，如果向量组 v ( 曲，i ( 功 u v ，( j ) ，j ， 线性无关。 由( 2 2 ) 式，我们不难得到如下结论： 命题2 , 1 【2 1 】在一阶k k t 点x 处，如果l i c q 成立，则乘子存在且唯一，即m ( x ) 为 单点集。 例2 1 取目标函数厂( x ) = 号( + 1 ) 2 + 工：2 。考虑问题 m i n 厂( j ) s t 一工0 ( x l 一1 ) 2 一x 2 1 0 l 圈 i v g 如“一 7 v g ：( 崮21例2 1 f i g2 i e x a m p l e 21 不难看出，扩= ( 0 ，0 ) 7 是问题( 2 1 ) 的唯一最优解，此时，) = 1 , 2 ， v 岛( p ) = ( - 1 ，0 ) 7 ，v 9 2 ( 矿) = ( - 2 ，一1 ) 7 ，可丁( 矿) = ( 1 ，o ) 7 。显然，v g i ( 矿) - 与v 9 2 ( x + ) 线性 无关，并且使得k k t 条件成立的唯一乘子为舻= ( 1 ，o ) 0 。 由于l i c q 具有很好的性质，因此是一种常用的约束规范。但是，正如a w i c h t e r 0 坐查型垫盔兰堡主兰垡笙苎垫塞垡些囹璧! 堂旦塑丝壅塑蔓墨墨塑皇茎墨 和l t b i e g l e r 在文献【1 中所指出的，当不等式约束的个数很多，特别是当等式约束的个 数大于2 时，这一条件很难得到保证。因此寻求较弱的约束规范很有必要。接下来要介 绍的就是比l i c q 弱的一种约束规范。 定义2 2s m f c q ( s t r i c t m f c q ) ：称可行点z x 满足s m f c q ，如果向量组 v g ，( z ) ，i ，+ ( d u v h ，( z ) ， 线性无关，且存在向量d r ”使得： v g f ( x ) 7 d 0 ，使得v 奢。( 矿) 7 d o 使得 i e l ( x ) l e j 。( 工) + v h 小) = o i e l ( x )业， 则称点x x 为m f 一非正则点。 定义2 5 ( 正线性相关) t 2 5 1 设a = 和1 ，a r ，b = 6 i ，b ”) 为r “的两个有限子集， 且4 u b 庐，我们称向量组( 彳，b ) 为正线性相关的，如果存在常数口r7 及卢er “，使得 口o ，( 口，) 0 且 g 。口+ 岛6 = 0 i = 1 j = l 否则称向量组( 4 ，口) 为正线性无关的。 显然，对于m f 一非正则点j e x ，向量组 v g 。( x ) ，i ，o ) ) u v h 。( 曲，j j ) 必为正线性 相关。 命题2 5 2 5 1 v x 石，假定，( z ) u j ，则m f c q 在x 点处成立当且仅当向量组 v g ( x ) ，i ，( 片) u v h ，( x ) ，j j 正线性无关。 例2 3 考虑问题 1 2 山东科技大学硕士学位论文约柬优化问题中常用的约束规范及其相互关系 m i n ，( 工) s f 一z l 0 ( 工1 1 ) 2 + z 22 1 0 工1 2 x 2 = 0 豫，( z + ) v g g )多弋。一 钒一7 卜、 、v ( z ) 图2 3 例23 f i g ，2 3e x a m p l e 2 + 3 0 问题( 2 3 ) 的最优解为p = ( o ，o ) 7 ，相应的有效不等式约束集l ( x + ) = 1 , 2 ) ，有效约束 梯度v 岛( 矿) = ( 一1 ，0 ) ，v 奢：( 矿) = ( - 2 ，0 ) 7 ，v 啊( 矿) = ( 1 ，- 2 ) 7 ，显然，v h l ( 矿) 线性无关， 而v 岛( 一) 与v 奢：( 矿) 线性相关。并且存在向量d = ( 吐， d 。) l d 、 o ，使得 v g , ( p ) 7 d 2 震【+ 篙0 ，+ 。) 由于m f c q 不再成立，因而得到的乘子集m ：o + ) 就变为无界集。 些蔓型垫查耋堡圭兰垡笙塞塑壅垡堡塑堕! 堂星竺丝壅塑蔓墨基塑呈茎墨 i 注1 】：由于当约束函数均为仿射函数时c r c q 是恒成立的，因此，对于当这个条 件成立时乘子集m ( j ) 的性质我们无法给出一个一般性的结论，只有当把这个条件分别 与l i c q ，s m f c q 或m f c q 相结合时，才能得到乘子集m ( x ) 的相关性质。这一点在例 2 4 中已经得到了验证。 定义2 7c p l d 条件( c o n s t a n tp o s i t i v el i n e a rd e p e n d e n c ec o n d i t i o n ) 1 2 6 1 - - 个可行 点z 满足c p l d 条件，如果它是m e - 正则点，或者当它为m f 一非正则点时，对 v i o ，( 工) 和w 。j ，当 v g f ( j ) ，i i o ) u v h ，( j ) ，j o 为正线性相关时，存在x 的一个 邻域n ( x ) ，使得对所有的y n ) ，向量组 v 爵( y ) ，i i o ) u h i ( y ) ，j - i o ) 为线性相关。 c p l d 条件是1 9 9 7 年由l q i 和z x w e i 在文献【2 5 】中提出的，但他们并没有证明 c p l d 条件是否为一个约束规范而只是作为一个开放性的问题提了出来。2 0 0 4 年由 r a n d r e a n i ，j m m a r t i n e z 和m l s c h u v e r d t 等人在文献 2 9 q b 对这一条件进行了讨论，证 明了由c p l d 条件可以推出下面将要介绍的一种较弱的约束规范拟正规约束规范，从而 c p l d 条件也可以作为一种约束规范来使用。 由c p u ) 条件的定义及命题2 3 可得如下结论： 命题2 6 对一阶k k t 点z ，如果x 为m e 非正则点，且在x 处c p l d 条件成立， 则乘子集m “) 必为无界集。 事实上，在例2 4 中，当把等式约束x ，一2 x ，= 0 替换成等价的两个不等式约束 z 一2 x 2 o 和一x 1 + 2 x 2 0 后所得的问题在矿= ( o ，o ) 7 处也满足c p l d 条件，但是正如 例2 4 中所分析的，由于m e c q 不成立，即x 为一m y 一非正则点，因而可得此时使得 k k t 条件成立的乘子集m ，( 矿) 必为无界集。 定义2 8 拟正规约束规范( q u a s i n o r m a l i t y c o n s t r a i n t q u a l i f i c a t i o n ) ：我们说点z 工 满足拟正规约束规范，如果它是m e 一正则点，或者当它是m f 非正则点时，对于常数 届，死， ，i ，( j ) ，不存在点列o 。 c r ”，使得当! i m 儿= j 时，对v j 上皿，o 及 v i f ( x ) 五0 ，都有： 声i h j ( y k ) 0 且2 i g i ( y k ) o v k = 0 ，1 ， 类似地，我们还有如下约束规范： 定义2 9 伪正规约束规范( q u a s i n o r m a l i t y c o n s t r a i n t q u a l i f i e a t i o n ) ：我们说点x x 满足伪正规约束规范，如果它是m f 一正则点，或者当它是m f 一非正则点时，对于常数 些查型垫奎兰堡圭兰垡笙苎 堑墨垡些塑里! 堂旦竺丝塞塑蔓丝茎塑至羞墨 屈，瓦，互，i ，o ) ，不存在点列 y t c r “，使得当l 鳃y t = x 时，对w j ，乃o 及 v i ，( 工) ，五0 ，都有： 巧g 渺。) + 五毋( n ) 0 ，v k = 0 , i ， j = ti e l ( x ) 与命题2 6 类似，由拟正规与伪正规约束规范的定义及命题2 3 可得下面的结论成立： 命题2 ，7 对一阶k k t 点工，如果工为m f 一非正则点，且在x 处拟正规或伪正规约 束规范成立，则乘子集膨( 曲必为无界集。 i 注2 1 ：由伪正规和拟正规约束规范的定义我们不难看出，一个点j x 如果满足了 伪正规约束规范，则它一定满足拟正规约束规范，即伪正规约束规范是比拟正规约束规 范更强的约束规范。虽然c p l d 条件也可以推出拟正规约束规范，但是伪正规约束规范 与c p l d 条件之间却不存在任何关系，即由c p l d 约束规范得不到伪正规约束规范，同 时由伪正规约束规范也得不出c p l d 约束规范。相关讨论参见文献 2 9 1 的c o u n t e r e x a m p l e 3 和c o u n t e r e x a m p l e4 。 最后，我们给出一种对于k _ k t 条件而言最基本的约束规范，它是从几何意义的角 度来定义的。为此，我们先给出一个与之有关的定义： 定义2 1 0 设c r “，j c l x ，称集合 r ( 五) = d l _ y = ；i m p k ( x 一x ) ，p i o ，j x ，x x ) 是啦处的正切锥。其中c x 是集合z 的闭包。 定义2 1 1 拟正则约束规范( q u a s i r e g u l a rc o n s t r a i n tq u a l i f i c a t i o n ) ：我们称点工 满足拟正则约束规范，如果它满足条件：丁0 ) = v ( x ) 。其中t ( x ) 是可行集z 在点z 处的 正切锥，矿( j ) = 抄尺“l v 奢；o ) 7 y s o ，i i ( x ) ；v h ，( z ) 7 y = o ，j 以。此时我们称j 是一拟正 则点。 有时，拟正则约束规范也称为a b a d i e s 约束规范。一般说来，现有的包括我们上面 所提到的各种约束约束规范的提出都是为了保证这一约束规范中的关系成立。正因为如 此，我们可以说只要满足了拟正则约束规范，则在最优解处一阶k k t 条件一定成立， 从而在最优解处相应拉格朗日乘子的存在性也就得到保证。 下面要介绍的一个条件是d h l i 和l q i 在文献【5 】中提出来的： 定义2 1 2w m f c q ( w e a rm f c q ) ：如果存在向量d r “，使 坐壅型垫查兰堡主兰竺堡苎竺塞垡些塑望主鲎望塑竺塞塑蔓墨茎塑蔓茎墨 1 矿g f ( x ) 7 d o ，v i l ( x ) ；v h j ( x ) 7 d = 0 ，w j 。 则称在点z x 处w m f c q 成立。 关于这一条件，文献 5 e o 证n 了以下结论： 命题2 8 在一阶k k t 点z 处，如果w m f c q 成立，则不等式约束乘子肘，( 柚为有 界集。 上述条件之所以称为“w e a rm f c q ，只是为了区别于m f c q ，因为它在，m f c q 的 基础上进一步去掉了等式约束梯度 v ，( x ) ，三) 线性无关这一条件。显然，当x 只包 含不等式约束时，w m f c q 营m f c q 。但是当存在等式约束时，这一条件不是一个约束 规范，反例如下： 例2 5 考虑问题 r a i n f ( x ) j t 工i 一2 x 2s 0 j 1 2 + ( x 2 + 1 ) 2 1 = 0 z 12 + ( z 2 2 ) 2 4 = 0 ( 、 ) 旧 2 、 彳j 心一v ，( 7 ) 、 - a v g ( 一) 圈25 例25 f i g 25e x a m p l e 25 最优解为妒= ( o ，o ) 7 ，此时v 岛( 一) = 0 , - 2 ) 7 ，v h 。( 矿) = ( o ，2 ) 7 ，v h ：( j + ) = ( o ， 4 ) 7 ， v f ( x + ) = ( 1 ，o ) 7 ，并且存在向量d = ( d ，o ) ，d 。 o ，使得v 氢( 矿) 7 d = ( 1 ，_ 2 ) ( 吐，o ) 7 = d t 0 ， v h ，( 矿) 7 d = ( o ，2 ) ( d 。，o ) 7 = 0 ，v h ：( 矿) 7 d = ( o ，一4 ) ( d ，0 ) 7 = 0 ，即在工+ 处w m f c q 成立。 但是容易求得乘子 = 一1 ，为一个负数，从而不满足k k t 条件，亦即满足k k t 条件的 17 些查型垫查兰堡主堂垡堡苎垫塞垡些塑垦! 堂里塑竺塞塑蔓墨苎塑兰i 竖 拉格朗日乘子不存在。因此，w m f c q 并不是一种约束规范。 【注3 】：值得指出的是，在l i c q 中，由于要求所有的有效约束梯度线性无关，因而 等式与不等式约束乘子都是唯一的：对s m f c q 而言，虽然只要求所有的强有效不等式 约束和等式约束梯度线性无关，但由于所有的非强有效不等式约束对应的乘子都为零， 故乘子集也是单点集；而在m f c q 中，由于要求等式约束梯度线性无关，从而只决定了 等式约束乘子的唯一性，而整个乘子集是有界的；相比较而言，由于w m f c q 进一步去 掉了等式约束梯度的线性无关性，因此它只能保证不等式约束乘子的有界性。 在回顾了约束优化问题中常用的约束规范，如l i c q ，s m f c q ，m f c q ，c r c q ， c p l d 以及伪正规、拟正规和拟正则约束规范，并讨论了它们与拉格朗日乘子的存在性 及其性质之间的关系之后，接下来给出各种约束规范之间的关系图。 2 3 各种约束规范之间的相互关系 为了得到各种约束规范之间的相互关系，我们首先给出几个引理： 首先，由l i c q 的定义可得以下引理。 引理2 1 在可行点x x 处l i c q 成立当且仅当下列关系式成立： v g f ( ) + ，v h ，( x ) = 0 j 丑= o ，v i ，( x ) ；2 ，= o ，巧j i e l ( x )i 毛l 引理2 2 在可行点z x 处s m f c q 成立当且仅当下列关系式成立： v g 。( 工) + 卢v h ( 工) = o ，a i o ，v i i o ( 功= ，丑i = o ，v i ，( 工) ；= 0 , v je j i e l ( x )i e j 引理2 3 在可行点x x 处m f c o 成立当且仅当下列关系式成立： , z , v g 。( z ) + 一v h ，( j ) = o ，2 1 o ，v i ，( x ) j 2 i = o ，v i ，( z ) ；1 2 ，= o ，w j 掂，( z )j e j 证明：该引理实际上是命题2 5 的一个变形。 由以上三个引理，我们不难得到如下结论： 引理2 4l i c qs m f c q m f c q 。 引理2 5 m f c q 伪正规约束规范。 证明：本结论可由伪正规约束规范的定义直接得到。 引理2 5 的结论反过来是不成立的，即由伪正规约束规范推不出m f c q 。反例参见 文献 2 9 】中的c o u n t e r e x a m p l e4 。 生奎登垫查竺堡主兰竺堡奎 竺至垡垡塑堕生堂里箜竺塞塑蔓墨薹塑兰鲞至 引理2 6 7 , p r o p o s i t i o n 2 如果点z 满足拟正规约束规范，则它必满足拟正则约束规范。 综合以上引理，我们可以得到以下定理： 定理2 1l i c qs m f c q j m f c q j 伪正规约束规范拟正规约束规范j 拟正 则约束规范。 i 注4 】：对上述定理中约束规范l i c q 、s m f c q 和m f c q 的关系，反过来是不成立的。 为简单起见，我们只考虑不等式约束的情形，l i c q 要求所有的有效约束梯度都是线性 无关的，而s m f c q 只要求强有效约束，即所有有效约束中拉格朗日乘子大于零的那些 约束梯度线性无关，而对拉格朗日乘子等于零的那些约束梯度则有可能是线性相关的， 因此，由s m f c q 推不出l c q ；类似的，由于m f c q 去掉了强有效约束梯度线性无关 的要求，故由m f c q 也推不出s m f c q 。但是对于只含等式约束的情形，它们三者是等 价的，即对等式约束问题，我们有： l i c q s m f c q m f c q 。 此外，由c r c q 的定义可得如下结论： 引理2 7 在可行点j x 处c r c q 成立当且仅当对w 。x c x ) 和w 。j ，当向量组 f v 奢，o ) ，i e l u v ，( z ) 山) 为线性相关时，存在x 的一个邻域0 ) ，使得对所有的 y ( z ) ，向量组 v g 。( y ) ，i l ) u v h j ( y ) ，j j o ) 也是线性相关的。 引理2 8l i c q j c r c q 。 证明：如果在一阶k k t 点x 处l i c q 成立，即向量组 v g 。( z ) ，i ，( j ) u v h ，( x ) 刀线性无关，则由函数v g ，0 ) o ，( z ) ) 与v h j ( x ) ( j e ，) 的 连续性可知，存在x 的邻域( z ) ，使得对v y n ( x ) ，向量组 o ，) ，i ，( ) u v ，( 少) ，j 以也是线性无关的。因此由引理2 7 知在x 处c r c q 成立。 即l i c qc r c q 。 引理2 9 在可行点x 彳处，如果c r c q 成立，则c p l d 约束规范成立。 证明：由于正线性相关一定线性相关，而由引理2 7 及c p l d 条件的定义，c p l d 条件中的正线性相关要求只是c r c q 中线性相关性要求的一种特殊情形，从而 c r c q j c p l d 。 引理2 1 0 如果可行点x x 处满足c p l d 约束规范，则它必满足拟正规约束规范 成立，但反之不成立。 证明：参见文献 2 9 t h e o r e m1 及c o u n t e r e x a m p l e1 。 1 9 坐奎型垫奎兰堡主茎堡堡苎丝塞垡些塑璧童星塑丝塞塑蔓墨墨塑皇茎墨 定理2 2 l i c q j c r c q c p l d 拟正规约束规范j 拟正则约束规范。 同时，由c p l d 的定义可得： 定理2 3m f c q j c p l d 。 l 注5 l ：类似于第二节中的 注1 ，虽然由c r c q 和m f c q 都能