（运筹学与控制论专业论文）线性规划的一类反问题的扰动方法.pdf

大连理工大学硕士学位论文 摘要 在优化模型中，目标函数和约束集合往往含有一些参数。优化正问题指的是参数值 是已知的求解优化的最优解和最优值的问题。然而在实践中还有另外一类问题，这类问 题的特点是只知道参数的估计值，但是可以通过经验、观察或是实验的方法来得到问题 的最优解或最优值，目的是找到参数的值，使它尽可能地靠近估计值。这类问题是优化 反问题。本文主要是对一类线性规划( l p ) 问题的反问题进行研究。 本文的主要内容可以概括为： 1 第二章主要是给出一些非光滑分析的结果，这些结果是收敛性分析所需要的。其次 我们给出了对偶理论的一些相关知识，并介绍了l a g r a n g e 对偶及问题的k k t 系统。 2 第三章我们利用k k t 条件给出了线性规划反问题的对偶问题，并进一步转化为一种 具有线性互补约束的最优化问题。 3 第四章给出问题的扰动模型，并证明可以通过求解一系列的扰动模型来求解反问题。 4 第五章主要是由第二章的知识，利用半光滑牛顿法来解扰动模型，进而给出具体的 算法及其局部收敛性和全局收敛性的证明。 5 第六部分根据第五章的算法做数值实验，验证了算法的有效性。 关键词：r 线性规划，反问题，扰动方法，半光滑牛顿法。 线性规划的一类反问题的扰动方法 ap e r t u r b a t i o na p p r o a c hf o rac l a s so f i n v e r s el i n e a rp r o g r a m m i n gp r o b l e m s a b s t r a o t a no p t i m i z a t i o nm o d e l u s u a l l yi n v o l v e sp a r a m e t e r sa s s o c i a t e dw i t hd e c i s i o nv a r i a b l e si n t h eo n e c t i v ef u n c t i o no ri nt h ec o n s t r a i n ts e t t h ef o r w a r do p t i m i z a t i o np r o b l e mi st of m d o p t i m a ls o l u t i o n st ot h eo p t i m i z a t i o nm o d e li nw h i c hp a r a m e t e rv a l u e sa r ek n o w n 。h o w e v e r , t 1 1 e r ea r em a n yi n s t a n c e si nt h ep r a c t i c e ，i nw h i c hw eo n l yk n o ws o m ee s t i m a t e sf o rp a r a m e t e r v a l u e s 。b u tw em a yh a v ec e r t a i no p t i m a ls o l u t i o n sf r o mo u re x p e r i e n c e ，o b s e r v a t i o n so r e x p e r i m e n t s a ni n v e r s eo p t i m i z a t i o np r o b l e mi st of i n dv a l u e so fp a r a m e t e r sw h i c h a r en e a r t ot h eg i v e ne s t i m a t e sa n dm a k et h ek n o w ns o l u t i o n so p t i m a l t 1 1 i sd i s s e r t a t i o nf o c u s e so i l s t u d y i n gap e r t u r b a t i o nm e t h o df o ra c l a s so fi n v e r s e1 i n e a rp r o g r a m m i n gp r o b l e m s t h em a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r t a t i o n ，m a yb es u m m a r i z e da sf o l l o w s ： 1 i nc h a p t e r2 ，w ei n t r o d u c es o m er e s u l t sf r o ms e m i s m o o t ha n a l y s i sw h i c ha r en e e d e di n c o n v e r g e n c ea n a l y s i s w ea l s oi n t r o d u c et h ec o n c e p to fl a g r a n g ed u a l i t ya n d k k ts y s t e m 2 。i nc h a p t e r3 。w ed e v o t et or e f o r m u l a t i n gt l l ei n v e r s el i n e a rp r o g r a m m i n gp r o b l e ma sa l i n e a rc o m p l e m e n t a r yc 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 3 i nc h a p t e r4 ，w ep r o p o s ean e wp e r t u r b a t i o nw a yt os o l v et h i si n v e r s ep r o b l e m 4 i nc h a p t e r5 w ep r o p o s et h es e m i s m o o t hn e w t o nm e t h o dt os o l v et h ee q u a t i o n s a n dw e p r o v et h el o c a lc o n v e r g e n c ea n d t h eg l o b a lc o n v e r g e n c eo ft h i sm e t h o d 5 i nc h a p t e r6 ，n u m e r i c a le x p e r i m e n t sa r er e p o r t e dt ov e r i f yt h ee f f e c t i v e n e s so ft h em e t h o d k e y w o r d s ：l i n e a rp r o g r a m m i n g ，i n v e r s e n e w t o nm e t h o d p r o b l e m ，p e r t u r b a t i o na p p r o a c h , s e m i s m o o t h i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名盔篁皇 撕躲堡堑 塑l 年上月上日 大连理工大学硕士学位论文 1 绪论 目前反问题求解是国际上一个十分活跃的研究领域，具有重要的理论探讨意义和工 程应用价值反问题研究是现代优化理论中的一个领域，它的理论正在日趋成熟，其实际 应用已遍及很多领域最初反问题主要有两个方面的应用： 一个重要的应用是来自地球物理科学和对地震运动的预测。为达到这个目的，地质 区域被离散为许多小单元，相毗邻的联系是由弧塑造的一个对应的网络模型。虽然一些 传输时间的估计值是已知的，但精确值是很难获得的通过观察地震和地震扰动在不同 点的到达时间，并假设地震运动沿最短的路径，问题变为重新估计在不同单元之间的传 播时间。这就是最短路经的问题。 另一个重要的应用是改变真正的费用。假设有一条道路网络和一些设备。目的将使 用的设备在到顾客最大距离的情况下是最小的。但是，经常遇到的情况是设备已给出， 使得无法合理的安排成本花费。在这样情况下，要尽可能少的修改网络，而使得设备是 最优的。这是中心地点反问题。当构造交通网络模型时，一个进一步选择是增加费用以 便加强对网络的充分利用。( 见d i a l ，1 9 9 9 ) 目前反问题求解不仅在工程学中有广泛应用，而且其他领域，如航空、海洋工程、 医学、地质学等方面也有广泛的应用。由于求解反问题的复杂性，理论知识还需进一步 完善。在优化模型中，目标函数和约束集中常含有一些参数和决策变量。当我们解决优 化问题时一般假定参数值是已知的，以便求解己知模型的最优值。然而在实践中还有一 些问题，比如只知道参数的估计值，然而会通过经验、观察或是实验的方法得到最优值。 最优化模型的反问题就是找到参数的解使得己知的最优解尽可能的靠近估计值。 1 1 反问题的发展及现状 1 9 8 7 年地球物理学家t a r a n t o l a 就研究过地球物理学数据参数的反问题，开了研究 反问题的先河。b u r t o n 和t o i n t ( 1 9 9 2 ) 4 对交通网络中最短路径和分配的反问题进行了研 究，并用来预测地震运动。从那以后研究组合优化反问题的文章大量出现，为反问题的 研究工作做出了巨大贡献。2 0 0 0 年趾l u a 和o r l i n 3 研究最优值的反问题，他们提出： ( 1 ) 如果最优值问题p 是多项式可解的，那么标准的最优值反问题在f 1 或乙范数下也 是多项式可解的： ( 2 ) 如果问题p 是最小成本流程问题，那么它的反问题在厶范数和单位权的情况下减 化为解决单位容量最小成本流程问题； 线性规划的一类反问题的扰动方法 ( 3 ) 如果问题p 对于线性成本函数是多项式可解的，那么p 的反问题在或乙范数下 也是多项式可解的。 j i a n z h o n gz h a n g 研究最优值最佳分配闻题，进一步说明反问题在或乙范数下也是 多项式可解的。随后2 0 0 3 年c h e u b e r g e r 研究一类最优化反问题，其目标函数是f ( x ；o ) ， 并且厂( x ；秒) = 0 7 x ，其中是乡未知的，这类反问题被称为线性反问题( l p s ) ，通过线性 对偶理论可以知道，要使线性反问题再用线性问题形式表示出来，则需要范数 i | j 是厶或 乙范数 3 ，3 6 】。2 0 0 4 年s h a b b i ra h m e d 和y o n g p e ig u a n 3 9 对最优值反问题进行研究， 在这篇文章里，虽然仍是对线性规划的反问题进行研究，但是仅知道目标函数的最优值， 而不是最优解。这样研究起来就很有实际意义了。他们将成本向量集定义在凸的紧致集 上，并证明了这是个n p h a r d 问题，同时还证明了最优值的反问题是多项式可解的。 但是对线性规划的反问题研究主要是关于目标函数参数的逆问题，本文所要做的是 关于目标函数及约束条件中的两个参数的反问题研究。将这种类型的反问题最终转换为 一个具有互补系统的m p e c 问题，并利用半光滑牛顿法求解。 2 本文的主要研究内容 考虑如下形式的线性规划问题： 妒( 啪) = t 二 t ， s 月工2d 其中c r 玎，彳r ”删，6 r 朋。设x 。q p ：= x r 丹卜x 6 ，x 。是驴( c ，6 ) 的 最优解，并且给定未知参数( c ，b ) 的初始解( c o ，b o ) r ”x r m ，则其反问题就是尽可能 小地调整( c ，6 ) ，使x o 成为最优解，即求解； f l i n 抓啪) 一c o 如 f 2 j 。x 。s o l ( l p ( c ，6 ) ) “2 o 【 ( c ，b ) r ”r m 其中l | - i l 定义为i l ( c ，6 ) l i ：= c r c + b r b 。 本文的结构如下。在第二部分，我们将给出一些非光滑分析及对偶理论中的一些结 论，以用来求解问颢和证明收敛件：第= 部分丰耍是将反问颢转让。为一个具有线件互补 2 大连理工大学硕士学位论文 约束的优化问题，以简化原始的逆问题；在第四部分中，将构造一个扰动问题只，来逼 近所求的逆问题；第五部分主要致力于用半光滑牛顿法求解扰动问题兄，并给出算法的 局部收敛性及全局收敛性的证明。 大连理工大学硕士学位论文 2 预备知识 2 1 半光滑映射的理论知识 在这一部分，我们将给出非光滑分析中的一些结论。 设x 和】厂是两个有限维实向量空间，o 是x 中的开集，：o x y 是一个局 部l i p s c h i t z 连续函数，瓯定义为在o 上的f 一可微点。那么，在x o 处的b 一次微 分 a 占o ( x ) ：= 妇( 石) p 风，寸石 l 其中，( x 。) 为在x 七处的j a c o b i n 矩阵。 定义2 1 ( 1 6 1 ，1 7 1 ) ：设o 是彳中的开集，：o x y 是一个局部l i p s c h i t z 连续函数， 称在x o 点是半光滑的，如果： ( 1 ) 在x 是方向可微的； ( 2 ) 对v a x x ，v a o ( x + 缸) ，且缸一o ，有 ( x + 缸) 一o ( x ) 一矿( 缸) = o ( 1 l 缸1 1 ) 进一步的，西叫做在x 点强半光滑的，如果在x 是半光滑的，且对缸x 和 v a o ( x + 缸) ，当缸专0 时， 西( x + x ) 一( x ) 一矿( x ) = 0 ( 1 1 缸1 1 2 ) 。 引理2 1 ( 1 1 0 1 ) ：假设巾是局部l i p s c h i t z 连续函数，则下面的结论等价： ( 1 ) 在z o 点是半光滑的； ( 2 ) 方向可微，并且对任意的x + 缸玩都有 ( x + x ) 一( x ) 一，( x + x ) = o ( 1 l 缸1 1 ) x 一0 ； ( 3 ) 中方向可微，并且 7 ( x + a x ，a x ) - 7 ( x ) = o c l l 缸1 1 ) a x 一0 ； ( 4 ) 任意的v 锄( x + 血) ，a x 专0 y ( 血) 一( x ；止) = o ( 1 l 缸1 1 ) 。 引理2 2 ( 1 8 1 ，1 9 1 ) ：设h ：x yjx 是( i ，歹) x xy 的一个开邻域上的局部l i p s c h i t z 连续函数，且h ( z ，习= 0 。如果对任意的阳( 牙，罗) 到石的投影映射1 - i j 汨( i ，歹) 都是 非奇异的，那么存在歹的一个开邻域o y ，和一个局部l i p s c h i t z 连续函数x ( ) ：o ，一x ， 线性规划的一类反问题的扰动方法 满足x ( y ) = i ，且砂0 y ，日 ( y ) ，y ) = 0 。进一步的，如果h 于( 瓦歹) 的开邻域内 的每一点是( 强) 半光滑，那么x ( ) 在o ，内每一点也是( 强) 半光滑的。 引理2 3 ：设x ，x7 和y 均是有限维实向量空间。f ：z y 是舅o y 上的连续可微 函数，且：o y 专x7 是包含歹= f ( i ) 的开集o y 上的局部l i p s c h i t z 连续函数和半光滑 函数。假设在o ，内的每一点都是方向可微的，那么 a 占( 垂。f ) ( i ) a 占( 歹) 腰( 芽) 另外，如果历( i ) ：x 寸y 是满的，上式中的“”为“= ，即 a 占( 巾。f ) ( z ) = a 口( 歹) 历( 牙) a 证明：设y = 中。f ，则丫在o 】，上几乎处处可微，任意v a 占y ( 牙) ，存在一个序列收 敛到i 的可微点 x cq ，使得 v = l i m j y ( x 七) g - - t r a 因为在0 y 内的每一点都是方向可微的，对任意的h x j y ( x 。) 办= ( f ( x 七) ；f ( x 。) 乃) 又在f ( x 七) 处是半光滑的，因此存在w a b ( f ( x 七) ) ，使得 ( f ( x 七) ；z f ( x 。) 办) = w7 j f ( x ) ( 向) 因此 j y ( x 七) 办a 8 0 ( f ( x 。) ) j f ( x 。) ( 乃) 又因为丸的上半连续性，得出 i i mj y ( x 七) 向a 占( f ( x 七) ) f ( x 。) ( 乃) 引理得证。 引理2 4 ( 【5 1 ) ：设x 和y 是两个有限维实向量空间。f ：x 专y 是o 上的局部l i p s c h i t z 连续函数，其中x 0 ，g ：y r 是o 上的连续可微函数，f ( x ) 0 。那么，复合函 数妒：= g 。f 是x 附近的l i p s c h i t z 连续函数，且矽在x 点的c l a r k e 广义梯度为 a p ( x ) = w 2v 宫( f ( x ) ) ：w o f ( x ) 。 定义2 2 ( 1 1 1 ，1 1 2 1 ) ：函数f ：r 户专r 在开集p r 尸被称为是己c 1 函数( 半光滑可微简记 为s c l ) ，如果f 在开集d 上连续可微的并且vr 在d 上局部l i p s c h i t z 连续( 半光滑) 。r 在 x 处的广义h e s s e n 阵定义为p p 矩阵a 2 r ( x ) 铲r ( x ) = c o o b vf 】( x ) 其中a 占 v f 】( x ) 是v f 在x 处的b 一微分，可以表示为 6 大连理工大学硕士学位论文 a 暑 v r l ( x ) = 日r e 。p i 丑七一x 爿f r v r e x 七处可微，v 2 r ( x ) 一日) 。 对于定义在开集0 r 尸_ f ：i 约l c l 函数f ，我们有以下二次类似泰勒公式和中公式。对 于区间 y ，y 】c0 ，在某一点国( y ，y ) 处存在矩阵h v 2 r ( c o ) ，使得 r ( y ) = f ( j ，) + ( v f ( y ) ，y 一少) + 去( y 7 - y ，h ( y 一y ) ) 并且存在j ( p ) 个点国1 ，彩2 ，c 0 7 ( y ，y ) 和h 7 a 2 r ( c 0 7 ) ( i = 1 ，2 ，) 使得 v r ( y 7 - - _ v 丁( y ) + t t h b - y ) i = 1 其中i = 1 ，2 ，并且+ 乞+ + = 1 。 定义2 3 ( 1 2 1 ) ：设h ：r ”一r “是局部l i p s c h i t z 连续函数。称它在x r ”是b d 正则的， 如果对所有的矩阵矿g h ( x ) 都是非奇异的。 引理2 5 ( 1 2 1 ) , 如果日在x r ”是b d 一正则的，那么 ( 1 ) 必存在x 的一个邻域n 和一个常数c 0 ，使对v y k 和v a s h ( y ) 都有y 非奇 异，且扩1 1 1 - 0 ，使x c v y k 7 ，椭- i i h ( y ) i l , o l l y - x l l 。 证明：( 1 ) 首先我们证明，存在x 的一个邻域k 和一个常数c 0 ，使得对v y n n ， h 7 ( y ) 非奇异且1 日( y ) 一1i 1 - c 。 用反证法，即假设不成立，则必存在一个序列y 七一戈，y 七d 日，使得或者 日7 ( y 2 ) 奇 异，或者l | ( 少) 8 一0 0 。因为日是局部l i p s c h i t z 连续，所以御在点x 的一个邻域内有 界。于是必可选出一个子列 岛) ，使得日7 ( y 岛) 一v 。此时矿必奇异且矿g h ( x ) ，这 与b d 正则性矛盾。 从上面的结论及a 占日的定义，对k 和矿a 君日( y ) ，y 非奇异且杪一1i i - c 。 ( 1 ) 若日( x ) = 0 和日在点x 半光滑，则对任何靠近x 点的y ， 日( y ) = h ( x ；y x ) + o ( 4 y x 1 1 ) 对方向少一x ，必存在一个v g h ( x ) ，使得 y ( y x ) = h7 ( x ；y x ) 7 线性规划的类反问题的扰动方法 郎 l l y - x i i - 0 ，使得 x + + 皖以x ，v 尼，且有畋- - + d ，反- - - ) o ( k = l ，2 ，) ，则称d 是xw _ x 处的序列可行 方向，x 在x + 处的所有序列可行方向的集合，记为s f d ( x , x 1 ) 。 引理2 2 3 ( k k t 定理) ( f 1 5 1 ) ：设x 是问题( p ) 的局部极小点，如果 l f d ( x , x ) = s f d ( x * , x ) ， 则必存在“+ = ( ，屹，) r ，v = ( v l 也+ ，) r 肛，使得： 所。聊 v f ( x ) + 吩+ v g , ( x + ) + u v h , ( x ) = 0 i = l i = m e + 1 0 ，“f g f ( x ) = 0 ，持l ，2 ，拂。 9 大连理工大学硕士学位论文 _ - 一_ _ 3 反问题的转化 类似于文献【1 】，我们来推导线性规划反问题的对偶表达式 由第二部分，如果x o s o l ( l p ( c ，6 ) ，根据k k t 条件，等价于存在甜r m ，满足： c - a 7 掰= 0 ，就0 ，a x o 6 ，且“7 ( a x o 一6 ) ：0 。 则( 1 2 ) 等价于如下形式 嘲三1 1 c - c 。1 1 2 + 扣- 6 0 1 1 2 c a r “= 0 s t 扰o ，a x o 一6 0 u t ( 出。一6 ) = 0 jm i n 妄1 1 c - c 。n h o l l 2 i l 卜掣 fm t n 三8 c 一彳7 “1 1 2 + 三l l v v 。1 1 2 卜 差。 由此我们可以得到，如果( 3 1 ) 有最优解( “，v ) ，则( 1 2 ) 的最优解就是 ( 彳7 “，a x o v ) 。因此我们所要求的逆问题，就转化为求解具有互补约束的优化问题。 大连理工大学硕士学位论文 4 扰动问题 4 1 构造扰动问题 问题( 3 1 ) 是一个典型的l c p 优化模型，对于此类问题，k k t 条件有可能在某个 局部极小点不成立，为了克服这个困难，类似于文献【l 】，我们来构造( 3 1 ) 的扰动形 式。 对于如下形式的互补约束；a o ，b 0 ，a b = 0 ，其扰动函数有这样几种形式： 纯( 口，b ) = 口+ b 一4 c 1 2 + b 2 + 2 s 2 ； a o ，b 0 ，a b 占； ( a + 占) ( 6 + 占) 占；6 占2 。 在本文中，我们采用下面的互补松弛函数：尸， l r n j n m m = 扣kc 。| 1 2 + 吾f - o l l 2 “p ( ) 1 柳( 4 1 ) i s t v p ( ) l 。 【 “o1 ，1 1 肌 其中9 ：r - - - 皿满足： 夕( o ) ：0 ，i i m s u p 型= 0 ( 4 2 ) ，0 0 f 或者p ( f ) = o ( f ) ，l 胁：= ( 1 ，1 ) 7 r 册，且铋。v = ( 强v 1 ，“m v m ) 丁。 令q ( ) ：= ( “，v ) 户( ) l 册，o o ) 2 l 掰。v z l 掰 为乞的可行域，并定义： ，口( 弘) ：- - i ：, t i = 夕( ) ) ， 也( v ) ：= z ：e = 夕( ) ， 三“( 甜，1 ，) ：= f ：u i v i = ) 为乞的起作用约束集。 下面的定理表明，线性无关约束规范对尸，成立。 线性规划的一类反问题的扰动方法 引理4 1 ：在( 4 2 ) 的条件下，有对任意的必 0 ，存在一个觞 0 ，满足对v d ( o ，鳓) ， v ( u ，v ) 0 2 m , a 2 册】nq ( ) ， ( 甜) n 三卢( 掰，1 ，) = ( 4 3 ) ，“( v ) n 三( “，v ) = 且线性无关约束规范在( “，v ) 处成立。 证明：对任意的m o ，令 o 刺f f 4 、以满足夕( ) 上m ，对任意的( 0 ，心) 成立。 令( “，1 ，) 【0 2 m a 2 m inq ( ) ， 对任意的i i u ( “) 及j 以( v ) ， u i v f = 夕( ) v 夕( ) m 0 巧【如】，+ 弦【咖】f = o , i 乙( “，v ) ，且互 0 成立着 ( z ( 如，a v ) ，( d u ，a v ) ) y 0 ( 如，咖) 1 1 2 ，v z a 2 ( ) l ( 瓦，v ，石，7 - ，丁) ( 4 8 ) 其中 0 ，那么( 一，矿) 是乞的严格局部极小点。 4 2 扰动逼近的收敛性 首先，我们引入下列记号： ( 毛：= ( “，v ) r ? r ：t u o v = 0 拼 弛v ，) ： 他，v ) 一- q ( ) l 。 o t f l e r s x ( u ) = i n f f ( u ，v ) i ( “，v ) q ( ) f ( ) = a r g m i n f ( u ，v ) l ( u ，1 ，) q ( ) 命题4 1 若p ( f ) 满足条件( 4 ，2 ) ，那么对v m 0 ， l i m 。q ( ) n 0 2 掰，m 1 2 脚】= qn 0 2 m ，m 1 2 掰】 ( 4 9 ) 证明：令吃= 一1 2 m ，1 2 册】，熊 0 ，满足： p m ，且p ( ) 0 ，炙j0 ，令 g = q ( 总) ，厂。( 甜，1 ，) ：f ( u ，v ) + 万( ( “，v ) j q ) f a r g m i n # ：= z i ( z ) i n f # + f ) 参考文献 1 ，那么可以得到下面几个性质： 命题4 2 以下结论成立： ( 1 ) l i m q 七= f 2 ( o ) ( 2 ) e l i m 七略= 矗( o ) l i m q 七= q ( o ) ( 3 ) e l i m 量f 。( ，) = 厂( ，o ) ( 4 ) l i m 女i n f f ( ，) = i 1 1 f 厂( ，0 ) ( 5 ) 对v f 0 ，l i m ts u r , f a r g m i n f 2 ( ，) cf a r g m i n f ( ，0 ) ( 6 ) 对v 氕 0 ，l i m s u p 磊一a r g m i n f 。( ，) ca r g m i n f ( ，0 ) 。 1 6 大连理工大学硕士学位论文 5 半光滑牛顿法来解扰动问题 由前面的结论可以得到，线性规划的反问题可以通过解一系列扰动问题只来解决。 在这一节，我们来讨论怎么去解决乞。类似于文献 1 】，首先，我们先给出该函数的 l a g r a n g e 函数： 三( 扰，y ，名，f ，j ) = f ( u ，1 ，) + ( 力，甜。，一1 脚) ( f ，u - p ( a ) l 历) 一( j ，一p ( a ) l 历) ( 5 1 ) 定义f ：r 5 m r 5 脚 f ( u ，y ，名，t ，s ) = v 。l ( u ，1 ，力，t ，s ) v 。l ( u ，y ，力，f ，s ) m a x 一五，“0 1 ，一l 。) m a x 一t ，p ( a ) l 历一“) m a x 一s ，p ( ) l 嬲一v ) ( 5 2 ) 如果( 瓦，矿) r 2 用是只的个局部极小点，那么因为线性无关约束成立，存在唯一的 l a g r a n g e 乘子( 万，- ，了) 满足k k t 条件，因此，( 万，矿，无f ，f ) = 0 5 m ，事实上，找乞的k k t 点就是解方程尸( 万，矿，见，_ ，f ) = 0 5 臃。因为f 是强半光滑的，我们可以用半光滑牛顿法来 解方程。然而这要求f 在解( 瓦，矿，无_ ，f ) 处的b 微分的元素必须是非奇异的，下面的引 理给予了肯定的回答。 引理5 1 ：设彳是行满秩的，且( 历，矿，无丁，f ) 是只，的一个k k t 点，满足引理4 3 的二 阶充分条件，那么0 s f ( f i ，矿，万，f ，歹) 中的每一个元素都是非奇异的。 证明：由( 5 1 ) 得，v 。三( “，v ，名，f ，s ) = a ( a7 1 “一c o ) + 旯1 ，一f v ，l ( u ，1 ，五，f ，j ) = ( v v o ) + 2 u s 设h a 占f ( 瓦，矿，旯，_ ，- s ) ，则 h = 其中天= 旃昭( 互) ，矿= d i a g ( v ，) ，口= 旃昭( 砭) o 厶o o k o一，o o 皿 o o乩o 3 一矿一沙巩o o 天l如。如 钟天虬乩。 一一 线性规划的一类反问题的扰动方法 。一 一：一_ = 一 h 3 1 = a i a g ( h 3 1l ) h 3 2 = d i a g ( e h 3 2 l ) 也3 = d i a g ( e h 3 3 】订) h 4 l = d i a g ( e h 4 l l ) 乩= d i a g ( h 4 4 l ) h 5 2 = d i a g ( h s 2l ) 致5 = d i a g ( h s 5 l ) ，一 卜悸 l r 一 h 3 ：b = 竺 【u 【也，l = t0 。 l 上 叭= 佬 乩】打= t o , l 1 r 一1 f 马z l - t - o j 吼，l ：f ! 【一l f 1 3 o t h e r s i j 3 o t h e r s i j 3 0 t h e r s f o t h e r s f o t h e r s i j 、 o t h e r s f o t h e r s 其中以相应于m a x ( - 2 i ，一一) 中由v ，一z 所确定的指标，z 相应于 m a x 一，p ( ) 一 中由p ( ) 一略所确定的指标，以相应于m a x 一s ，p ( ) 一v i ) 中由 p ( ) 一e 所确定的指标。 令 e ( _ ) ：= f ，( 历) ，百 o ) 以( - ) ：= f ( 矿) ，葛 0 乞( _ ，矿) ：= f l u ( 瓦，矿) ，乃 0 那么由互补约束条件得： ，p ( 万) 以2l 口q - ( 瓦) ； 厶( 矿) 以2e ( 矿) ； 乙( 万，矿) 2 以乞( 瓦，矿) 假设( _ ，矿) m 0 ，1 2 m ，m 0 ，且( o ，岛) ，其中硒符合引理4 1 中的条件，那么 ，- n 以= ，以n 以= 。不失一般性，设= l ，2 ，厶 ，以= 1 ，2 ，乞) ， , 1 3 = 1 3 + 1 ，7 , _ ，其中乞z l ，毛乞。 令以= l ，2 ) 以，i = 1 ，2 ，3 ，则 1 8 大连理工大学硕士学位论文 天- i 矧矿= 学最 人。天，l肚k 矿i 扩= x 衅最 风：三呒0-j蝣一习 风z o 巧，i乜。= l 3of l - ，3j l v v j 。厶i 。= 一l 01 兰 k = 三一 ：= 一吕 ，= 3 一羔 令日( y f ，一，菇，订，菇) 丁= 0 ，y ，r m ，i = l ，2 ，3 ，4 ，5 。 要证日非奇异，就要证”= 0 ，i = 1 ，2 ，3 ，4 ，5 。 由日( y f ，露，一，m t ，) 丁= 0 ，得： 么彳7 y ，+ 三五：，3 y ：+ 意考， y ：一乳= 。 。0 五乏 m + 虼+ 奢曼 y ，一y ，= 。 。0 甚 夕，+ 吕z ， 照+ 一兰 y ：= 。 一吕 y ，+ l 三一l y 。= 。 降o ii o 一斗= 。 得 y 1b = 0 ，眺k 20 ， y 4 7 1 = 0 ， 少s k20 ， f y ，1 了：0 ，( ，o 矿) 弘+ ( o 巧，) y ，：0 1 9 ( 5 3 ) ( 5 4 ) 线性规划的类反问题的扰动方法 将( 5 3 ) 和( 5 4 ) 写在一起： 硕寸什 用( y 。7 ) 作用上式得： ( 圳撇) _ o 卜、1 l y ；】以l = o 5 5 h ：f j 由于( y l 7 一) 符合引理4 3 中的条件，所以由二阶充分条件 | a a l | f 万 i = l ，2 ，3 ，4 ，5 ，结论得证。 儿) ，( y ， y ：) 8 ( y 。 ) | | 2 ， 由( 5 5 ) 知 弘】 = o ， y 5 】，：= o ，【y 3 l = 0 ，故y ，= o ， 下面用半光滑牛顿法来解只。 记z ：= ( 刮，v ，么，t ，s ) ，第七次迭代点z ：= ( 影后，v 七，力，t k , s ) ， 0 ：= f ：p 群- p ( u ) ，五：= 泓v ? h k ： 州7 a 日3 1 七 人量 i m h 3 0 风2 矿七 u 七 h 。0 0 0 - p ( p ) ) ，片 - i m 0 0 一i 能 oo h 4 , 0 o ：= f ：硝 一扰? t ( 5 6 ) h s 其中人。= d i a g ( a i 。) ，v 。= d i a g ( v ? ) ，u = d i a g ( u j ) f t i 一 3 1 乜2 七= d i a g ( h 3 l k 】甜) d i a g ( h 3 z k 2 0 马，七l ( 也：正】。， = 骺 = 诺 i j ； o t h e r w i s e i j ； 0 t h e r w i s e ( 5 7 ) 、，0， 吲，胛 n a 1 o ，。l 一 rili，j 1lii，l_1 “ n l i ，3 l 么 唯d 心 y lii、 、0i一 一a ， 一以 c 以。一以 o c = 儿为 = 因 只 故 峨。 大连理工大学硕士学位论文 也3 七= d i a g ( h n k f f ) 凰l = d i a g ( h 4 1 k 】打) 乩七=