（应用数学专业论文）多目标规划的非单调信赖域算法.pdf

华中科技大学硕士学位论文 摘要 信赖域方法是近二十几年发展起来的一类重要的数值计算方法。由于具有很 好的可靠性、强适性，以及很强的收敛性，目前它已和传统的线搜索类方法并列 为求解非线性规划的两类主要的数值计算方法。众所周知，大多数求解非线性规 划问题的信赖域算法是单调的。但研究表明，单调性的要求并不总是合理的，它 有时会降低计算效率，使迭代点列的收敛变得缓慢。设计非单调算法是解决这一 问题的有效途径之一。这方面成功的研究工作都集中在单目标领域。由于多目标 规划问题在现实生活中的普遍存在性，设计求解多目标规划的有效算法是一项重 要而有意义的工作扣本研究工作的内容是，就多目标规划问题设计一类非单调信 ， 赖域算法并证明其收敛性：工作的意义在于改善通常单调的信赖域算法的性能， 提高计算效率；工作的创新之处体现在将非单调算法的思想推广至多目标规划以 及算法的收敛性证明方法上。 鉴于信赖域方法在无约束及线性约束问题方面的工作较为完善，本研究只讨 论多目标规划相应的两种情形。首先，分别给出了无约束多目标规划问题以及一 般线性约束多目标规划问题的非单调信赖域算法模型，分析了算法的全局收敛性， 在一定的条件下得到了类似于单目标的全局收敛性结果。进一步，单独对线性等 式约束多目标规划问题加以讨论，去掉了一般线性约束情形下保证全局收敛的一 个假设条件，且仍然得到了全局收敛性结论。最后，算法得到了计算实现，数值 试验从实践的角度证明了新算法的有效性。 关键词：多目标规姆信赖域方法、非单毁全局收敛性j 华中科技大学硕士学位论文 a b s t r a c t t r u s tr e g i o nm e t h o di s a ni m p o r t a n tn u m e r i c a lm e t h o dd e v e l o p e di nt h el a s t d e c a d e b e c a u s eo fi t sr e l i a b i l i 吼r o b u s t n e s sa n ds t r o n gc o n v e r g e n c e ，u u s tr e , o n m e t h o d ，t o g e t h e r w i t hl i n es e a r c h a l g o r i t h m s h a sb e c o m eo n eo ft h et w om a i n n u m e r i c a lm e t h o d sf o rs o l v i n gn o n i i n e a rp r o g r a m m i n g i t sw e l lk n o w nt h a tm o s tt r u s t r e g i o na l g o r i t h m sf o rs o l v i n gn o i l l i n e a rp r o g r a m m i n g a r em o n o t o n e r e s e a r c h e ss h o w , h o w e v e r , t h a te n f o r c i n gm o n o t o n i c i t yi sn o ta l w a y sr e a s o n a b l e s o m e t i m e si tr e d u c e s c o m p u t a t o n a e f f i c i e n c ya n ds l o w st h er a t eo fc o n v e r g e n c e t od e s i g nn o u m o n o t o n e a l g o r i t h m s i so n eo ft h em o s te f f e c t i v em e t h o d st oo v e r c o m et h ep r o b l e m s t h e e x i s t i n gs u c c e s s f u lr e s e a r c h e si nt h i sf i e l dh a v eb e e nc o n c e n t r a t e do np r o g r a m m i n g w i t hs i n g l eo b j e c t i v e t h u s ，t od c s 追ne f f e c t i v ea l g o r i t h m sf o rs o l v i n gm u m o b j e c t i v e p r o g r a m m i n gp r o b l e m si sa ni m p o r t a n ta n d v a l u a b l ew o r kd u et oi t sg e n e r a le x i s t e n c e i np r a c t i c e - t h ec o n t e n to ft h ep m s e mm s e a r c hi st od e s i g nac l a s so fn o n m o n o t o n e a l g o r i t h m sf o rm u l t i o b j e c t i v ep r o g r a m m i n g t h es i g n i f i c a n c ef o rt h i sr e s e a r c h i st o i m p r o v ep r o p e r t i e s o fu s u a lm o n o t o n er u s t r e g i o na l g o r i t h m s a n d i m p r o v e c o m p u t a t i o n a le f f i c i e n c y t h ei n n o v a t i o nl i e si nt h a tt h ew o r kg e n e r a l i z e st h ei d e ao f n o u m o n o t o n et o m u l t i o b j e c t i v ep r o g r a m m i n g a n dt h et e c h n i q u ef o rp r o v i n gt h e c o n v e r g e n c e i sd i f f e r e n tf r o mo t h e r s c o n s i d e r i n gt h a tr e s e a r c hw o r k so nt r u s tr e g i o nm e t h o df o ru n c o n s t r a i n e da n d l i n e a rc o n s t r a i n e d p r o b l e m sa r er e l a t i v e l ym a t u r e ，t h ep m s e n t w o r k o n l yf o c u s e s o nt h e c o u n t e r p a r t sf o rm u l t i o b j e c t i v ep r o g r a m m i n g f i r s t l y , t h ep a p e rp r e s e n t st h em o d e l so f n o n m o n o t o ct r u s tr e g i o na l g o r i t h m sf o ru n c o n s t r a i n e dm u l t i o b j e c t i v ep r o g r a m m i n g a n dg e n e r a ll i n e a rc o n s u a l n e dm u l t i o b j e c t i v ep r o g r a m m i n g ，r e s p e c t i v e l y a n dg l o b a l c o n v e r g e n c ei sa n a l y z e d u n d e r c e r t a i nc o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c er e s e tt h a t i ss i m i l a rt ot h a to f s i n g l eo b j e c t i v ep r o g r a r r l m i n g i so b t a i n e d i n a d d i t i o n ， - _ _ _ - _ _ _ _ _ _ _ _ - _ - - - _ _ _ - _ _ _ _ _ _ _ _ - - _ - 一 i i 华中科技大学硕士学位论文 m u l t i o b j e c t i v ep r o g r a m m i n gw i t hl i n e a re q u a l i t y c o n s t r a i n e di sd i s c u s s e d f o rt h i s k 叫o f p r o b l e m s ，t h eg l o b a lc o n v e r g e n c e i ss t i l lr e m a i n e db u tr e m o v i n ga n a s s u m p t i o n w h i c he n s r r c st h eg l o b a lc o n v e r g e n c eo ft h ea l g o f i t h r a sf o rt h eg e n e r a lc o n s t r a i n e d m u l t i o b j e c t i v ep r o g r a m m i n g a tl a s t , t h ea l g o r i t h m sa r cp u th t t on u m e r i c a lp r a c t i c e f r o mt h ev i e wo f p r a c t i c e ，n u m e r i c a le x p e r i m e n t sp r o v et h ee f f e c t i v e n e s so f t h en e w a l g o r i t h m s k e y w o r d s ：m u l t i o b j e c t i v ep r o g r a m m i n g t r u s tr e g i o nm e t h o dn o n m o n o t o n e g l o b a lc o n v e r g e n c e i l l 华中科技大学硕士学位论文 1 1 量优化理论与方法 1 绪论 最优化理论与方法是一个重要的数学分支。它研究某些数学上定义的问题的 最优解，即对于给定的数学问题，从众多的方案中选出最优方案。这类问题在人 类改造自然界的过程中是普遍存在的。例如，工程设计中怎样选择设计参数，使 得设计方案既满足设计要求又降低成本；生产计划安排中，选择怎样的设计方案 才能提高产值与利润；城建规划中，怎样安排工厂、机关、学校、商店、医院、 住户和其他单位的合理布局，才能方便群众且有利于城市各行业的发展：军事指 挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争全 局；诸于此类，不胜枚举，最优化问题几乎涉及所有具有数值信息的活动。最优 化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到广泛的应 用，成为一门十分活跃的学科。 最优化是一个古老的课题。长期以来，人们对最优化问题进行了探讨与研究， 其历史可以追溯到1 7 世纪n e w t o n 发明微积分时代提出的极值问题。人们关于最 优化问题的研究工作，随着历史的发展不断深入。但是任何科学的进步，都受到 历史条件的限制。直至二十世纪三十年代，最优化这个古老的问题并未形成- - f 新的科学。四十年代以后，由于生产和科学研究突飞猛进的发展，特别是计算机 日益广泛的应用，使最优化问题的研究不仅成为一种迫切的需要，而且有了有力 的求解工具，因此最优化理论与方法迅速地发展起来。在1 9 4 7 年d a n t z i n g 提出 求解一般线性规划问题的单纯形方法之后，最优化正式形成- 1 3 独立的系统的学 科。 最优化问题的一般形式为 l 华中科技大学硕士学位论文 r a i n ，( x ) s 1 x x 其中工r “为决策变量，( x ) 为目标函数，x e r “为约束集或可行域。特别地， 如果约束集z = r ”，则最优化问题( 1 1 1 ) 称为无约束问题： r a m i n f ( 工) ( 1 1 2 ) 约束最优化问题通常写为 m i n ，0 ) s t c ，( x ) = o ，i 占， ( 1 1 3 ) c ，( x ) 0 ，i ， 这里e 和，分别是等式约束的指标集和不等式约束的指标集，q ( 砷是约束函数。 最优化发展至今，内容已相当丰富，分支也很多。根据目标函数和约束函数是否 为线性，最优化问题可分为线性规划问题和非线性规划问题；根据决策变量、目 标函数和要求的不同，最优化还分成整数规划、动态规划、网络规划、非光滑规 划、随机规划、几何规划、多目标规划等若干分支。 最优化问题的求解方法很多，而且时至今日，新的解法还在不断涌现。现将 主要的解法归纳如下： 问题方法 单纯形法，改进单纯形法对偶单纯形法，割平面法。 线性规划 分枝定界法。分解算法 非线性规划解析法，直接法，最速下降法，坐标轮换法，共轭梯度法，方向 ( 无约束)加速法变尺度法，步长加速法，n e w t o n 法 非线性规划可行方向法，罚函数法，中心方法。梯度投影。罚函数法，线性 ( 约束)逼近法障碍函数法，既约梯度法广义莱子法。可行方向法 近年来又出现了一些新算法，如信赖域法，极大熵法，精确罚函数法等。 2 华中科技大学硕士学位论文 1 2 多目标规划 多目标规划研究多于一个的数值目标函数在给定的约束条件下的最优化问 题。由于从一定意义上说，实际的最优化问题一般都含多个目标的，因此多目标 规划的理论和方法在现代经济和社会发展中具有十分广泛的应用范畴。它是进行 经济、科技、军事和文化中重大科学决策和规划的有利工具。 多目标规划的两个主要起源是“1 ：在经济学中f y e d g e w o r t h ( 1 8 7 4 年) 和 v p a r e t o ( 1 9 0 6 年) 关于均衡竞争和经济福利研究以及在数学中g c a n t o r ( 1 8 9 5 ) 和 f h a u s d o r f f ( 1 9 0 6 年) 的有序空间理论的建立。在5 0 年代h w k u h n 和 a w t u c k e r ( 1 9 5 1 年) 有关向量极值理论的研究，g d e b r e u ( 1 9 5 4 年) 结合评价均衡 方面的工作以及l h u r w i e z ( 1 9 5 8 年) 把问题提向抽象空间的尝试，为这一学科的 形成作了重要的前期准备。直至7 0 和8 0 年代经过众多学者的努力，终于建立起 多目标规划的基本理论基础，使之成为应用数学的一个新的学科分支。 多目标规划问题也称为向量极值问题。与只含有一个数值目标函数的单目标 数学规划不同，对于一个给定的多目标规划问题，同时使其中各个目标都达到最 优的最优解一般是不存在的。因此，在多目标规划的研究中，通常是考虑使它的 向量目标函数在某中意义下为非劣的所谓有效解。 多目标规划问题的标准形式为： ( v p ) y m i n f l ( x ) ，l ) 】7 ( 无约束) 或 ( v p ) v m i n f l ( x ) ，正( 工) 】r ( 有约束) s tc ( r ) = o ，i e c ，o ) 0 ，i ， 华中科技大学硕士学位论文 1 3 相关工作的发展现状 1 3 1 信赖域方法 在众多求解最优化问题的方法中，信赖域方法十分引人注目。它在近二十年 来受到了非线性优化研究界的非常重视，特别是最近几年，一直是非线性优化的 研究热点。目前信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主 要数值方法。 信赖域方法是为了克服线搜索方法可能出现的困难而提出的一类新的计算方 法。它有着很强的逼近背景，其基本思想是不进行线搜索，每次迭代在一信赖域 内找一试探步，然后取决该试探步是否接受。 信赖域方法的研究起始与m j d p o w c l l 。对于无约束光滑问题，信赖域方法 得到了深入研究 1 , 2 9 , 3 4 】，后来又出现了非单调信赖域算法1 9 。”舯- 2 ”，它是通常的单 调信赖域算法的推广。不象传统信赖域方法， 2 7 结合了信赖域技术和线搜索， 当迭代步长导致目标函数上升时，它不重解子问题，而代之以从失败点开始执行 一个往回的线搜索。跟无约束优化问题相比，约束优化问题的信赖域法及收敛性 则没有得到很好的解决，种处理方法是通过精确罚函数将之转化为无约束非光 滑问题，这促进了无约束非光滑优化问题的信赖域方法的发展。许多学者将信赖 域方法应用到非光滑优化问题上 1 6 , 1 7 , 3 , 3 2 j 。d e n n i s 】建立了无约束非光滑优化问 题信赖域方法的一般模型，并在目标函数为正则函数的情况下证明了算法的整体 收敛性。 1 3 2 非簟调技术 传统的迭代算法一般都要求迭代点对应的函数值单调下降。但是，研究表明 这一要求并不总是合理的，它有时会降低计算效率。使得迭代的收敛速率变得缓 慢。于是，非单调算法应运而生。 2 2 j 首次提出求解非线性规划问题的非单调算 华中科技大学硕士学位论文 法的概念，其算法是牛顿法。非单调算法的特点是，将新迭代试探点对应的函数 值与前面若干个迭代点对应的函数值中的最大者相比较，当满足一定的下降条件 时，即将此试探点作为新的迭代点。数值试验表明，这一技术对改善算法性能， 提高计算效率十分有效，特别是对具有所谓“狭长深谷”的目标函数的优化问题， 其效果更加显著。 2 3 2 6 是这一工作的进一步深入，且都是针对线搜索类算法 的。从此之后，掀起了一股非单调算法的研究热潮。 1 8 提出非单调信赖域算法， 改变了试探步的接受规则，并证明了新算法的收敛性。相关的工作有 9 1 3 、 1 5 、 1 9 、 2 1 。 1 4 本文的工作意义及工作安排 非单调算法的研究在单目标规划领域已有许多优秀工作，而对多目标问题的 研究尚无人涉及。由于多目标规划问题在社会生产生活、工程设计领域广泛存在， 因此设计求解多目标规划问题的有效算法是一项重要而有实际价值的课题。基于 已有相关成果，本文试图开发多目标规划的非单调信赖域算法。工作的意义是： 将非单调算法的概念推广到多目标规划，改善通常单调的信赖域算法的性能，提 高计算效率。 由于信赖域方法关于无约束和线性约束问题方面的研究发展得较为完善，故 本文仅对无约束多目标规划问题和线性约束多目标规划问题做讨论。 具体的工作安排如下： 1 无约束多目标规划的非单调信赖域算法及其收敛性。 2 一般线性约束多目标规划的非单调信赖域算法及其收敛性。 3 线性等式约束多目标规划的非单调信赖域算法及其收敛性。 4 数值试验。 5 华中科技大学硕士学位论文 2 1 引言 2 无约束多目标规划的非单调信赖域算法 信赖域方法是非线性优化的一类重要的数值计算方法。近二三十年来，它一直 是非线性优化研究界的潮流性课题。目前，对信赖域算法的研究大多集中在单目标 领域。文 7 针对无约束多目标规划提出了类信赖域算法，得到了与单目标情形 相似的全局收敛性结果。本章在 7 及参考 卜6 的基础上，给出了求解无约束多目 标规划的非单调信赖域算法，并证明了全局收敛性。 2 2 问题与记号 本章考虑下列无约束多目标优化问题： ( m o p ) m i n f ( x ) = “( 力，l ( z ) ) ，工r “ 其中，p 1 为一j 下整数，v 1 s i p ，( x ) 二次连续可微。 设 为当前迭代点，简记：邑( x ) = 可z ( 苫) ，g _ = v f , ( x 。) ，删= 0 也，孔是( m o p ) 的 k r 点是指： 3 a ：( ，乃) o ，且五0 ，使得杰 晶。：0 以对应的( m o p ) 的信赖域子问题为 卵( 也，毋，“m i n e r i ( d ) 2 恐鹭t 田+ d 7 b , d 5 0 d 临a 其中，鼠为给定的对称矩阵ta 。为信赖域半径。 s p ( x i ，b k ，a i ) 等价与下面的舻( 坼，b k ，t ) 一一 华中科技大学硕士学位论文 卯私。，眈，m 。i n 。，7 十吉d 氇d “i i d l i a 。 由s p ( ，b k ，a 。) 的最优性条件有 g i d 叩，i = 1 ，p 定理2 幺1 设( 以，仇) 为s p 。( 屯，b i ，) 的最优解，则j ( 砧，砖) 0 使得 ， 钟= 1 ，t l p ( 毋+ 2 ：1 ) d k + 2 f g 雎= 0 1 1 名( 。- i l e , 1 1 ) = 0 硝( 叩。一9 0 d 女) = o , i = 1 ，一，p 进一步，若阢( 以) = 0 ，则h 为( m o p ) 的k t 点。 设或为子问题卵( 以，b 。，。) 的解，删t p r e d 。= 帆( o ) 一帆( 巩) ，则对预 估量有以f 绪论： 引理2 2 1 【7 1 设以s p ( x 女，b k ，i ) 的解，则有： p r e d k 矿m i n 舭。物，l | 黾肛 ( 2 2 1 ) 其中妒2 ( 屯) a ，卿( 工) 2 馏胞d ) ，如d ) 一m 。a ，x g ，( 工) 7 d a 同【7 】，记：g ：圭霹g ，矿：圭? g ，则有矿= 悟4 ，其中为下述问 题的l a g r a n g e 乘子， m i l l 六( d ) _ m 。a x ，t g s , d l l a l i 7 华中科技大学硕士学位论文 ；= = = 目= = = 目= = = = = = = = = = = = = = = = = 易见，；g g = o 或妒( ；峪i i ) = 0 ，则“是( m o p ) 的k - t 点。 2 3 算法描述 设m 为非负整数， r e ( o ) = o ，m ( 七) = m i n k ( 七一1 ) + 1 ，鲋l 七= 1 ，2 ，记 ，= ：( 扎) ，( 七) 满足： 女一m ( 七) ( t ) t ，且使= 蛳m 柑( a x 。) k “7 ) 。f = l ，p 。 算法如下： 算法2 3 1 s t e p l 给定月”，a o 0 ，对称阵岛月默”，0 ，l r 2 1 r 3 , 0 0 p t ( “j = 1 , 2 ， 1 【 ，吩啦刈 ( 2 4 1 ) ( 2 4 2 ) ( 2 4 3 ) ( 2 4 4 ) 其中j 表示内循环的次数，于是 + i m , a = 0 ，! i m “e l l = 0 ( 2 4 5 ) 由( 2 4 3 ) 式得到 ：型m i l n f ( k ) - f _ ( x k + 一d ) 竺m i 生n f k - f ( x k 一+ d ) ( 2 4 6 ) prea；pred 其中 p d 2 ( o ) 一虮( 酬) = 一m 。a ：x 。t g t , a ) 一 ( 州) 7 b 0 ( 2 4 - 7 ) 因为o m 。i n 。 f , 一f ( x k + 彤) ，从而 ( 2 4 8 ) 因为f 取有限个值，故存在无穷指标集i ，c l 二，2 且3 如：1 o p ，当w ，有 9 华中科技大学硕士学位论文 m i n ，一，( z 。+ d f ) ) = 露一兀( x + d f ) i p 从而由( 2 4 5 ) 、引理2 2 1 及中值定理，当，j 且充分大时 上式中，0 “，于是，由的定义，易得 引理2 4 1 若假设2 4 1 成立，则v 1 i p ， ) 乙单调递减且收敛。 假设2 4 2v i i s p ，w ( 工) 一致连续 下面的引理对算法收敛性的证明十分关键。 y l q e 2 4 2 若假设2 4 2 成立，且了艿 o ，使恬忙正忙l 怿万，则3 p o ，使得 慨忙p z i ，v k = o 1 2 ( 2 4 1 0 ) 其中互= m 。a ) ( ，l b , i i 证明因为假设2 4 2 成立，所以对于 万( 1 - u ) ，j ，7 0 ，当m l ，7 时，v 1 i s p 型 等 匹 b d 一吼 丝矿灞 州一 华中科技大学硕士学位论文 d ：【1 e ，：( x + d ) 一1 r ，：( 工) j ( 1 一) 0 d 。0 ，v x r ”， ( 2 4 1 1 ) 令 = m i n r ) 6 ( 1 一) ，a o z o ，_ 叩z o ) ( 2 4 1 2 ) 下面我们用, j a 纳法证明( 2 4 。i 0 ) 式成立 当k = 0 时，因为内循环有限次结束，不妨设第m 次退出内循环，即 i ，= l ，2 ，m i 且p f ( 2 4 1 3 ) 如果脚= 1 ，若i 怫f i 1 ，则由算法中信赖域半径的迭代规则知 ，l m s 划s 也( 24 1 6 ) 【p g 1 ， ，= l ，2 ，m i 下面证明 粉忙z 。，= 1 “2 ，m ( 2 4 1 7 ) 由( 2 4 1 4 ) 和( 2 4 1 5 ) 式，我们已知当_ ，= 1 时，( 2 4 1 7 ) 成立现假设 ，= l ，1 ， m ，( 2 4 1 7 ) 式成立对于- ，= “l ，若j 睇“i i ，由酬“的最优性 有，酬“+ g o = 0 ，从而 华中科技大学硕士学位论文 峪。i i 可1 1 口o , 搿 1 1 = 丽i g 。1 1 昙 ( 2 s ) 若归0 = 譬1 ，则当忙州2 印时，有 雌1 忙罅1 1 _ ，7 = 私。i z 。2 , 8 z o ( 2 4 1 9 ) 当1 1 1 1 ，7 时，有肛划i = 醵1 - r 2 1 1 1 1 占( 1 一u ) m i n l l 毹8 ，2 占础玩0 一归邪 ( 2 4 2 4 ) 当帜8 万州鼠j l 时，由上式得l 怫1 1 曰o l l 占( 1 一) ，否则有4 酬忙, q l 占o l l ，- t - ；e j j 酬肛j f 风8 m i n 艿， 万( 1 一) ) = 万( 1 一) 1 ( 2 4 2 5 ) 从而 w 1 卜罅z , - , l a ：l _ 夕 4 1 a o l l = p z o ( 2 4 2 6 ) 由归纳法知，f 2 4 1 0 ) 式当k ：0 时成立 华中科技大学硕士学位论文 现假设( 2 4 1 0 ) 式对于k o 成立，对女+ l ，不妨设第m 次退出内循环，即 p 厶l 1 ，则由算法中信赖域半径的迭代规则 n 4 蔓喇也h 8 【以l 0 ，使得v 1 i s p ，“一，“士，巧m i n f l z i ，5 乙 ls l z i ，v k ( 2 4 - 3 4 ) 由( 2 4 3 4 ) 式及 五) 的单调性有 华中科技大学硕士学位论文 n2 。+ s i zk 铲1 + s z n ，“。枷工“+ s z “l “+ s l z i + + _ + 川：+ ，+ 。+ s z t + m + 村+ s z t + m + 由引理2 4 1 ，对上述不等式两边取极大有 ：m “ ，“，正“， k + m + l + s z “村“， v k ( 2 4 3 5 ) 利用，“”的定义易知，“”+ m a x k + - , “，+ ”+ ) ，v k ，从而有 一+ 。s z m + l ，v k( 2 4 3 6 ) 由( 2 4 3 6 ) 及) 厶的收敛性得 1 z ) -i 艿，则由引理2 4 2 、引理2 4 3 知 l z , 0 ，占0 , 0 1 , 0 吩 1 0 ，使对无穷多个k 成立：厶。2 艿，风声。记 1 7 _ k e p r e d 一, u r l l 2 ( 3 3 6 ) 但由假设3 3 5 知，( 3 3 6 ) 式不可能对无穷多个七成立，此矛盾说明引理成立e 定理3 3 2 若假设3 3 1 3 成立，则k 必有一个聚点是( l l 奠m o p ) 的k t 点。 证明若定理不成立，据引理3 3 1 有： ! 鳃t5 0t + 从而存在一无穷子标集足。使得：v k k ：p 。 ，不妨设 盥为x t = 量，r v k ：t 1 ( 3 姗 据假设量不是k t 点，令d 是问题 ( p ) ：m i n 懋 g j ( 主) 7 田+ - 詈1 1 4 2 “口7 d ：0 , i e a ，。( 主+ d ) 屯，i j i d l l 。l 的髌，则由0 是( p ) 2 的可行解知 毋= 秘) 7 缸删2 o ( 3 3 1 1 ) 华中科技大学硕士学位论文 p r p 以一罂野( 扎) 一z ( 以+ 以) ) = 一磷 铂一扣7 b 以一啤叭一胁t 嘲) ) s 一。( _ ) 7 巩一丢巩7 仇矾_ ，。( 以) 一厶( 以+ 巩) 】 其中f 0 是使得，( 孔) 一z ( x 。+ 以) 取得最小值的f 。f o 与七有关，又考虑到f 取有限 个值，我们可认为它与七无关。由 毋) 一致有界及中值定理知，3 0 k o ，l 】使得 p r e d , 一m 。；i n 。 f i , ( x , ) 一( 砟+ d k ) ) s 昙口i i , ，, 1 1 2 + ，( 以+ 8 , d ) 7 以一瓯( 以) 7 d k 二 p r e d t m i n c ，：( x , ) 一：( + 以) ) 可i 可一 昙a 1 i 以肛l i ( 孔+ 以以) 一瓢( _ ) l l ( 3 3 z 2 ) 另一方面，由k 的定义得 婴竖型二坐：型丝 0 ，0 “ 1 0 1 7 2 ，k ：= 0 s t e p l 求解子问题艘”( h ，风，a 。) 得矾，若忙。i i - 0 。 定理4 3 1 算法是良定的。 证明只需证明，对一切非k - t 点屯，算法中内循环经过有限步必终止。 反证之，设以不是k t 点且内循环不终止，则 吼 0 ( 4 3 2 ) p f u ，j = 1 , 2 ， 胪= 塑- 面一 从而 由( 4 3 6 ) 式知 m 。：i n ，( , ( 瓢) 一，( + d f ) 卜p d f o ( 4 3 6 ) 一f _ 坚m i n z ( x , ) - f 面, ( x k 广+ d 一) - p r e d p r e d f m 。：i n 。 f ，( x k ) 一z ( + d 埘 ：= - - - 。1 “。一 p r e d 因为f 取有限个值，故存在无穷指标集，c 0 , 2 ，) 且存在f 0 ：1 i o p ，当w j 有 m 。；i n ， f , ( x k ) 一，( h + 酬) ) 2 ( 以) 一无( 以+ d f ) 于是，由中值定理、引理4 3 1 及( 4 3 5 ) 式知，当，j 且充分大时 一- 卜型ra _ s * t 南mx r n 溉d j 糍产幽1 i 一 仇m i i l ，吼，0 既1 ) 其中0 o 显然，互t 乜是s p ( x ) 的可行解，所以 一群珏瓦卜髂 z 所以，当k k 譬k 且充分大时 ”一瞬k t 孙争。 这与引理条件l i m 仇= 0 相矛盾，引理得证。 i t h + 为了证明