（运筹学与控制论专业论文）一类二次规划反问题的研究.pdf

大连理工大学硕士学位论文 摘要 在优化模型中，目标函数和约束集中经常有一些参数和决策变量当解决优化问题 时一般假定参数值是已知的，以便来求解己知模型的最优值然而在实践中还有一些问 题，只知道参数的估计值，但是通过经验、观察或是实验的方法知道最优值最优化模 型的反问题就是找到参数的解使得己知的最优解尽可能的靠近估计值本文主要是对一 类二次规划( q p ) 的反问题进行研究 本文的一些主要结果可以概括为： 1 第2 章给出一些非光滑分析的结论，对于收敛性分析有帮助还给出对偶理论的一些 重要知识点，并介绍了l a g r a n g e 对偶及k k t 系统 2 利用 1 】的结果，第3 章给出二次规划反问题对偶问题的一种线性互补约束最优化问 题的形式，简写成i q p ( a ) ，并且这个问题是一个s c l 的凸目标函数并且含有的决策 变量要比原二次规划反问题的少很多同时还给出投影算子的一些性质及求其b 微 分的公式 3 不同于 1 】中的扰动方法，第4 章给出一种新的扰动方式求解问题i q p ( a ) 我们给出 并给出c 稳定点的概念，证明扰动问题的解的极限点是c 稳定点最后给出光滑牛 顿算法求解辅助问题，并证明其全局收敛性 关键词：二次规划；反问题；扰动方法；光滑牛顿法 一类二次规划反问题的研究 t h es t u d yf o rac l a s so fa ni n v e r s eq u a d r a t i cp r o g r a m m i n gp r o b l e m a b s t r a c t i na no p t i m i z a t i o nm o d e l 。u s u a l l yt h e r ea r ep 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 b j e c t i v ef u n c t i o no ri nt h ee o m u a i ms e t 、h 既s o l v i n gt h eo p t i m i z a t i o np r o b l e m , w e u s u a l l yf 1 $ $ 1 1 i n et h a tt h e s ep a r a m e t e rv a l u e sa r ek n o w n i no r d e rt os o l v eo p t i m a ls o l u t i o nf o r t h ek n o w no p t i m i z a t i o nm o d e l h o w e v e l t , t h e r ea r em a n yi l l s t a n c c $ i nt h ep r i c e ：i nw h i e h w 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 rv 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 l s o l u t i o n sf r o me x p e r i e n c e ，o b s e r v a t i o n s0 1 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 s t of i n dv a l u e so fp a r a m e t e r sw h i c hm a k et h ek n o w ns o l u t i o n so p t i m a la n dw h i c hd i f f e rf r o m t h eg i v e ne s t i m a t e sa sl i t t l ea sp o s s i b l e o u rm a i n l ys t u d y i n gi s0 1 1ac l a s so fi n v e r s eq u a d r a t i c p r o g r a m m i n gp r o b l e mi nt h i sd i s s e r t a t i o n n l 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 j z e 蛆笛f o l l o w s ： 1 hc h a p t e r2 ，w eg i v es o m ec o n c l u s i o n sf o rs e m i - s m o o t h i n ga n a l y s i s ，t h i sw i l ld oh e l pf o r c o n v e r g e n c e w ea l s oi n t r o d u c et h ec o n c e p to f l a g r a n g ed u a l i t ya n dk k ts y s t e m 2 w i 血t h eh e l po ft h er e l a t e dr e s u l t so f 【l 】，c h a p t e r3i sd e v o t e dt or e f o r m u l a t i n gt h e i n v e r s eq u a d r a t i cp r o g r a m m i n gp r o b l e ma sal i n e a r c o m p l e m e n t a r i t y c o n s t r a i n e d o p t i m i z a t i o np r o b l e m n a m e l yi q t ( a ) w h i e l ah a sa 跖1c o n v e xo b j e c t i v ef u n c t i o na n d f e w e rd e c j s i o l r lv a r i a b l e st h a n1 h eo r i g i n a li n v e r s eq u a d r a t i cp r o b l e m ，w ea l s o 翊v es o m l ! g e n e r a lp r o p e r t i e so f t h em e t r i cp r o j e c t o r 3 d i f f e r e n tf r o mt h ep e r t u r b a t i o na p p r o a c hp r o p o s e di n 1 】，i nc h a p t e r4 ，w ep r o p o s e8n e w p e r t u r b a t i o nw a yt os o l v ep r o b l e mi q p ( a ) w ei n t r o d u c et h ec o n c e p to fc s t a t i o n a r y p o i n t s a n ds h o w t h a t a n y l i m i t p o i n t o f s o l u t i o n s t o p e r t u r b a t i o n p r o b l e m s i sa c - s t a t i o n a r y p o i n t f i n a l l y w eu s es m o o t h i n gn e w t o nm e t h o dt o s o l v et h ea t t x i l i a r ye q u a t i o n sa n d p r o v et h eg l o b a lc o n v e r g e n c eo f t h es m o o t h i n gn e w t o nm e t h o d k e yw o l r l ：l s = q u a d r a t i cp r o g r a m m i n g ；i n v e r s ep 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 m o o t h i n g n e w t o nm e t h o d 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：董耋巫日期：型z ：兰：! 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 采用影印、缩印或扫描等复制手段保存和汇编学位论文 作者签名 导师签名 童亏减 ! 醯坠 上丑年月盟目翌年月旦目 大连理工大学硕士学位论文 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 ) 川对交通网络中最短路径和分配的反问题进行了 研究，并用来预测地震运动从那以后研究组合优化反问题的文章大量出现，为反问题 的研究工作作出了巨大贡献2 0 0 0 年a h u j a 和o r l i n 口1 研究最优值的反问题，他们提出： ( 1 ) 如果最优值问题p 是多项式可解的，那么标准的最优值反问题在或乙范数下也是多 项式可解的；( 2 ) 如果问题p 是最小成本流程问题，那么它的反问题在范数和单位权的 情况下减化为解决单位容量最小成本流程问题；( 3 ) 如果问题p 对于线性成本函数是多 一类二次规划反问题的研究 项式可解的，那么p 的反问题在或乙范数下也是多项式可解的z h a n gj i a n z h o n g 研究 最优值最佳问配问题，进一步说明反问题在或乙范数下也是多项式可解的随后2 0 0 3 年c h e u b e r g e r 研究一类最优化反问题，其目标函数是，o ；日) ，并i ；tf ( x ；o ) = 矿工，其 中是p 未知的，这类反问题被称为线性反问题( l p s ) ，通过线性对偶理论可以知道，要使 线性反问题再用线性问题形式表示出来，则需要范数l | | | 是或乙范数【3 矧2 0 0 4 年 s h a b b i r a h m e d 和y o n g p e ig u a n ”1 对最优值反问题进行研究，在这篇文章里，虽然仍是 对线性规划的反问题进行研究，但是仅知道目标函数的最优值，而不是最优解这样研 究起来就很有实际意义了他们将成本向量集定义在凸的紧致集上，并证明了这是个 n p - h a r d 问题，同时还证明了最优值的反问题是多项式可解的 又如2 0 0 4 年c h e u b e r g e r 的文章 2 】和参考文献中的【5 】，【6 】，【7 】， 4 0 】等都是对反 问题进行研究研究线性优化反问题的还有【8 】和【9 】【1o 】是对锥优化反问题的研究，这 篇文章主要是利用一类称为锥规划 3 7 1 反问题的对偶问题类似l p s ，因此将线性规划反问 题的对偶问题用锥优化的对偶问题代替，进而研究锥优化的反问题最近z h a n g i a n z h o n g 和张立卫f 1 1 】用增广l a g r a n g e 函数方法研究二次规划的反问题，他们对二次规 划目标函数的两个参数g 和c 同时进行变化，并用对偶理论求得对偶问题是半光滑可 微的凸问题，对偶问题的变量个数大大减少，同时他们运用半光滑牛顿法和a m i j o 线搜 索证得对偶变量是全局收敛和局部二次收敛的以上对各种反问题的研究一个共同的特 征是未知参数只出现目标函数中，而本文研究的问题未知参数不仅出现在目标函数中， 还出现在约束集中 1 2 本文的进展及主要结果 本文中研究的是另一种类型的二次规划的反问题，未知参数出现在约束函数中 本文考虑的二次规划问题的形式是： q p ( g ，c ，b ) n l i n ，( 功：= 芦1 礅+ c r z s t x e q ，：= x r ”1 4 工6 ( 1 1 ) 其中g r ”是对称矩阵，c 彤，a r ，和b 仨r ”其中 a ：= ( q ，a 2 ，) 丁，4 f r ”，i = 1 ，2 ，m 2 大连理工大学硕士学位论文 表示月行对称矩阵空间，q ，是可行域，并且s o l ( p ) 是问题( p ) 的最优解集给定一个 可行解扩q ，它是问题q p ( g ，c ，b ) 的最优解，并且给定未知参数( g ，c ，b ) 的初始解 ( g o ，c o ，6 0 ) s ”x r ”x r ”，在本文中是找二次规划反问题的解( g ，c ，6 ) e x r ”x r ”使 其满足： r a i n 寺i i ( g ，c ，6 ) ( g 。，c o ，b 。) 1 1 2 s t 一s 0 1 ( q & g ，岛丘6 ”( 1 2 ) ( g ，c ，6 ) 熨x r ”x r ” 其中霹是中的正半定对称矩阵锥，并且定义为 i i ( g ，c ，) l l ：= 4 m g 4 g ) + 一c7 + 6 ，7 b 其中( g ，c ，6 ，) r ”x r ”r ” 本文的一些结果：第2 章给出一些非光滑分析的结论，对于分析收敛性有帮助还 给出对偶理论的一些重要知识点，并介绍了l a g r a n g e 对偶及k k t 系统；利用 1 】的结 果，第3 章给出二次规划反问题对偶问题的一种线性互补约束最优化问题的形式，简写 成i q p ( a ) ，并且这个问题是一个s c l 的凸目标函数的问题，并且含有的决策变量要比原 二次规划反问题的少很多同时还给出投影算子的一些性质，最后给出其b 微分的公式 不同于【1 】中的扰动方法，在第4 章给出一个新的扰动方法求解问题i q p ( a ) ，给出c 稳 定点的概念，并证明扰动闯题的解的极限点是c 稳定点，最后给出光滑牛顿算法求解辅 助问题，并证明其是全局收敛的 大连理工大学硕士学位论文 2 预备知识 2 1 半光滑映射的理论知识 在这一节里，首先回忆关于半光滑映射的非光滑分析的一些结论及半正定矩阵锥的 一些性质，这些都将在以后的几章里有重要的用处设x 和y 是两个有限维的实向量空 间，并且8 是x 中的开集，设：s x y 在口上是局部l i p s c h i t z 连续的，通过 r a d c m a c h c r 定理。在口上几乎处处f r i c h e t 可微我们用d 击表示巾在9 上的f r 誊c h e t 可微 集，用钆o ( z ) 表示中在x s 处的b o u l i g a n d 次微分， a 口西( z ) ：- p ) 个点埘1 ，2 ，7 ( ) ，y 7 ) 和h 7 0 2 r ( c 0 ) ( f - l ，2 ，z ) 使得 v r ( y ) = v f ( y ) + f ， 一力 ( 2 7 ) t = l 其中o ，f = 1 ，2 ，- z 并且+ f 2 + + = l 2 2 对偶理论知识 首先介绍l a g r a n g e 对偶，详见例，对于一般的非线性最优化问题 原始问题( p ) r a i n f ( 功 s j g ，( x ) 0i = 1 , 2 ，k 吃( 功= 0i = m e + 1 ，m x x 其中彳是可行解 记e = ，肌又记j ( 功= f i 岛( 功= o ) 为积极约束指标集 对偶问题( m 7 一类二次规划反问题的研究 m a x o ( u ，v ) s t 群0 rm ，w1 其中 o ( u ，v ) = i n f 厂( x ) + u , g ，( x ) + v 魄( x ) 畦x l i = i ，r “ j 引理2 2 1 ( 弱对偶理论) 设工是原始问题( p ) 的可行解，即工x ，g ( 功0 ，h ( x ) = 0 并设眩v ) 是对偶闯题( d ) 的可行解，即材0 则厂( 力8 ( 掰，v ) 匡论1 i n f 厂( 力j x x ，g ( z ) o ，而( x ) = 0 ) s u p o ( u ，v ) l 0 推论2 如果，( i ) 9 ( 厅，哥) ，其中磊o ，并且i 仁工k ( x ) s o ，厅( 工) = o 则i 和何，哥) 分别是原始和对偶问题的最优解 引理2 。2 2 ( 强对偶理论) 设x 是r ”中非空的凸集，并设，：掣_ r ，g ：酞”_ r 4 是 凸函数，h ：彤r ”一是仿射函数，即 ( x ) = a x b 若下列条件成立：存在童x ，使得 g ( 章) 0 使得x 十耐石，v t “o ，占】，则称d 是 z 在x 处的可行方向x 在x 处的所有可行方向的集合，记为f d ( 了，x ) 定义2 2 3 设z 彳，d r ”，如果 d 7 v g 。( ，) 0i l ( x ) d 7 v 鱼( x ) = 0i e 8 大连理工大学硕士学位论文 则称d 是工在x 处的线性化可行方向，工在，处的所有线性化可行方向的集合记为 l f d ( x , x ) 定义2 2 4 设x z ，o d r ”，如果存在序列以( j i = 1 ，2 ，) 和殴 o ，使得 x + d 6 k 石，v k ，且有蟊一d ，& 哼o ，( _ | = 1 ，2 ，) 则称d 是z 在x 处的序列可行方向，z 在，处的所有序列可行方向的集合记为 s y d ( x ，z 1 引理2 2 3 ( k k t 定理) 闭设x + 是问题( p ) 的局部极小点，如果 l f d ( x ，工) = s f d ( x ，x ) ，则必存在甜= ( 西，”：，碗) e r ， v = ( v 二j + l ，t ) r ”嘎， 使得： v f ( x ) + “瓢，( x ) + 观( 工) = o i - i ，哪k + i 西2 0 ，“? g f ) = o ，i = 1 ，2 ，m 。 对于二次规划q p ( g ，c ，a ，b ) ，有下面的引理 引理2 2 4 f 定理9 1 1 l 1 设茹+ 是二次规划q p ( g ，c ，a ，b ) 的局部极小点，则必存在 l a g r a n g e 乘子，( i = 1 ，2 ，m ) ，使得 c + 靠= i q ( x ) t = l 甜q 7 x 一6 ，】- 0 ，f = 1 , 2 ，m 疋2 0 ，i = 1 , 2 ，m 9 大连理工大学硕士学位论文 3 对偶问题 3 1 二次规划反问题的对偶问题 类似于文献，这一节我们推导二次规划反问题的对偶问题表达式 如果g 霹，由引理( 2 2 4 ) ，那么x oe $ o l ( g ，c ，a ，6 ) 的充分必要条件是：存在 u e r 所，使得 c + g 譬。一彳r u = o 。，0 。s 甜上( 4 x o 一6 ) 2 0 。 所以问题( 1 2 ) 等价于以下形式 i n i n 抓g ，c ，6 ) 一( g o , c o , 6 0 ) | 1 2 s t c + g - x 。一彳7 甜= 0 。， ( 3 1 ) 0 ，上( 4 x o 一6 ) o 。， ( g ，c ，b ，“) s ? x r ”x r ”x r ” 设v = 出。一6 和v o = a x o b o 我们会得出下面的含有线性互补约束的p s d 锥约束最优化 问题： m i l l 钏( g g o ，c - - c o , v - - v o ) l f 2 盯抖白。一u = o 。， ) 0 。z f 上v 0 ， ( g ，c ，“，v ) r ”x r ”x r ” 为了简化等价公式( 3 2 ) ，我们需要引入一个有限维空间n ，让k 譬x r 丹，并且有下 面的内积 ：= t r ( g 1 7 g 2 ) + c l r c 2 ，v ( g ，c 7 ) k ，i = 1 ，2 并且引入范数是： i l ( g ，c ) l = j t r ( g r g ) + c r c ，( g ，c ) k 定义一个线性算子互：k - - h r 以为： 互( g ，力# ( ( 三。，( g ，呦，( - - ，( g ，呦) 7 ，v ( g ，力k 其中三f _ ( 华，气) ，f ：1 ，2 ，疗 一类二次规划反问题的研究 并且气r ”是第i 个元素是l ，其余的元素全是0 的单位向量经过计算会得到： c + g x o a 7 i t = 0 n 三( g 力一a 7 “= 钆 先考虑( 3 2 ) 的子问题： n f m 三l i n g g 0c - - c 0 ) 1 1 2 s j 量( g ，c ) - a 7 u = 0 。，( 3 3 ) ( g ，c ) 。s n r 珂 这是一个含有参数“r 研的凸规划问题设它的最优解为 ) ，也就是： 工( “) ：= j i n f 9 g g 。i 2 + l i c c 。8 2 l 互( g ，c ) 一彳= ，( g ，c ) r ”) ( 3 4 ) 定义 ，( “，v ) # 兀 ) + 劲v v 。i f 2 ( 3 5 ) 如果对任意的u r m ，三：k r 咒是满射，那么 | ( g ，) i 似霹x r ”) ，使得e ( g ，z - ) 一u = 0 。 这就是说广义的s l a t c r 条件关于问题( 3 3 ) 成立因此对于凸规划由【2 l ，定理1 7 ，定理1 8 通过经典的对偶理论知道问题( 3 3 ) 和对偶问题之间没有对偶间隙那么( 3 3 ) 的l a g r a n g e 对偶是： 瑚x ，( 功- r a i n z ( g ，c ，工)( 3 6 ) x r 玎 ( g ，c ) 贮r ” 其中l ：e x r 栉_ r 是问题( 3 3 ) 的经典的l a g r a n g e 函数： 上( g ，g x ) ；( 8 g g 。1 1 2 + i j c c 。1 1 2 + 0 ，使得 厂【( i r ) ( “，v ，) + t ( u , v ) 1 ( 1 一t ) f ( u ，v ) + r f ( u , v ) 一o t ( 1 一，) 0 一“，矿一v ) 0 2 其中t ( o ，1 ) 并且( ，v ) ，( “，功f 3 。2 投影算子的性质 从上面引理3 1 1 中可以看出需要计算投影算子的b 微分，下面给出投影算子的一 些重要结论 设k 是y 中的闭凸集，以后般取k 为凸锥熨或皿：，通过可以知道是l i p s c h i t z 常数为1 的l i p s e h i t z 连续函数因此v y ，a r ) 是有意义的 下面给出o i l f ( ) 的一些性质： 引理3 2 1 ( 性质1 ) 冽设k y 是闭凸集，则渺y ，y o i l xo ，) 有： ( i ) 矿是自伴随的算子 ( i i ) ( d ，v d ) 0 v d y ( i i i ) ( v d ，d v d ) o v d y 一类二次规划反问题的研究 设z s ”，z + = n ，( z ) ，e z 有谱分解z = 尸人p 7 其中人。是对角阵，其对角元素是a 的对应元素的绝对值 3 0 3 1 1 口一 f h o ) ，卢p h = o ) ， ，：= 0 h 0 是常数，则 日( 力芝9 ( 力+ v p ( x ) 7o ，一工) + 去仃f f y x l l 2 ，v x ，y e r “ 引理3 3 2 在定理3 3 1 的条件下，我们有： ( i )对任意的x o 掣，水平集 如v p ：= 工r “：p ( 功v o ，v o = 口( 工o ) 是紧致凸集 ( i i ) 任意的紧致集s 互r “，存在一个正的常数乓，使得 p ( y ) p ( x ) + v 日( x ) 7 ( y - - x ) + 去岛 i y 一卅1 2 ， v x ，y s 下面用阻尼牛顿法和a f m i ) o 线搜索来求解问题( 3 2 1 ) 算法3 3 1 ( 阻尼牛顿法) 第0 步选一初始点r ”，参数p o ( o ，) 卢( o ，1 ) ，令七# o 第1 步如果0 v 日( 矿) l l = o ，则停止否则转到步2 第2 步取0 2 0 ( x ) ，并从下线性系统中计算方向d v d = 一v o ( x 、 第3 步取，是最小的非负整数，使得 o ( x + 卢7 d ) 一o ( x ) p o 卢7 v o ( x ) 7 d 1 7 ( 3 2 2 ) ( 3 2 3 ) 一类二次规划反问题的研究 并令膏。“= 工+ a k d ，其中a ：= 卢7 令k ：= k + l 转到步1 由于p ( ) 是连续可微函数，d 是使得日( ) 在点处下降的方向，因此我们可以证明 算法3 1 是全局收敛的，如下： 定理3 3 1 设0 ：r ”_ r 是s 函数，满足： a “。( 功仃，v v 0 2 0 ( x ) ，v x r 其中仃 0 是常数，则算法3 3 1 产生的序列 矿 收敛到问题( 3 2 1 ) f 懈 证明： 设= 口( ) 令 心- - - - o 。1s u pl i v o o r ，v v e a 2 p ( x ) ，、q k r ” 其中仃 0 是常数，并且映射v p 是强半光滑的，则存在一整数，使得步长 吼= iv k 云 证明：对充分大的k ，有： i i x t + d 一i 8 = 0 x i 一 矿。 。v o ( x ) 一i = l c 矿 4 ( v 8 ( 工) 一v 9 ( i ) - v * ( x l i ) ) 0 r h 于v o 是强半光滑的，所以 i x k + d 一i i = 。( 0 x - i l l 2 ) 又由引理3 2 【3 s 】，有 l i m t o = 1 0 x t + j 一i l l ：。( 1 l d 1 ) 再由中值定理及中的性质2 7 和引理3 2 ，有 对充分大的七，存在厅。a 2 p 0 ) 和矿a 2 口加。) 其中矿 ，矿+ ) 并且7 1 ( i ，矿) ，使得： 坼锄) 叫班妒一习7 膏。( “弘i ) 1 9 一类二次规划反问题的研究 p ( x ) = p ( i ) + x k - - i ) 1 旷x 一孑) 联合上面的两个式子，有 p ( 工女+ d ) 一口( ，) 一j 1v 口( x ) 7 d 。= 一圭( x j i ) 7 旷x k - - i ) 一j 1v 口( x ) 7 d + 。( 8 d 。0 2 ) = 一圭( 一i ) 7 矿x ki ) 一扣7r e ( ) 一v 岖) 一矿( 孑) + o ( m f 2 ) = 伸。n 所以 o ( x k + ) 川矿) = j 1v 8 ( ) v + 妒) = ( 圭一风) v p ( 咖v + 。咿u 2 ) + 风v 坼丫 又由d s ) 中的定理3 3 知 9 c 工i + d ，一日c 工，成v p c x 。，7 d l ( 圭一p 。) d 1 2 + 。( 1 l d 1 2 ) p o v o ( x r d 所以对v 七云，有a t = 1 ，从而满足a r m i j o 准则 命题得证口 又当系统在b d 正则解处是半光滑时，有下面的定理 定理3 3 3 设性质3 3 1 的条件成立，则算法3 3 1 产生的序列 ) 二次收敛到i 用算法3 3 1 解问题( 3 2 1 ) t f j ，函数8 ( x ) = 甲( 功+ 枷一( 扩一五7 甜) i 1 2 是强凸的，并且v e 是强半光滑的所以定理3 3 1 和性质3 3 1 都满足，因此算法3 3 1 用来解问题( 3 2 1 ) 时 有二次收敛速度算法3 3 1 在整个计算过程都是内部迭代，所以在用算法3 3 1 时，“扩) 用近似迭代是合理的 用算法3 3 1 时的困难是：在第k 次迭代时，如何找到 a 2 v ( 工) + 咕一( c o - a r u ) 喇k ，的元素，以便产生下降的方向事实上，在实践中不是 直接选取的，而是求其近似值 由第3 1 节很容易知道： a 2 甲( 力+ 忙一( c o - a r u ) 9 2 l 。，2 ，+ 2 h a 。n 霹( 弓( 缸”) ) ) 壳 大连理工大学硕士学位论文 令，z ( z ，“) ：= 2 1 + 2 h a 口n p ( 石( “甜”) 壳 从而在算法的第2 步中，取v z ( ，“) 并用下面的线性系统计算方向d 。 言矿= 一壳n ( 百) ) + 工一c o + 彳 ( 3 2 8 ) 很容易证得这样产生的序列f l 仍然是全局收敛9 j 1 a 7 t n ( 3 2 1 ) 的解只是收敛速度变慢 了在算法3 3 1 中，需要( 3 2 8 ) 以一个更为明显的式子表示出来用否( 矿) 代替第3 2 节 中的z ，又由( 3 2 0 ) 及引理3 2 2 知道：v w 0 b i i ，( 承矿) ) 存在q ，使得： 矽。( 材+ ) = p ( p 7 生竿p 。q 。z 9 ， 令 p = ( 暑，昱，只) 2 ， = p r x o 由 的定义及o 2 9 ) 式，得到： h w ( t w l ) = ( 弓。( q ( 妒) ) ) ( 。( q ( _ o o i 。) ) ) p = ( q ( i 。i 。) 1 ：) 。p 7 p 7 d = t 。( q ( i 。i 。) ) 7 。尸 p d 所以( 3 2 8 ) 可以写成： l + 1 。( q ( i 。i 。) ) 7 。p i p 7 d = 一a n 肆( 弓o 。) ) + 工t c 。+ 彳7 “( 3 3 。) 2 1 大连理工大学硕士学位论文 4 扰动方法及收敛性 4 1 扰动方法 构造问题i q p ( a ) 的扰动问题，如下 r a i n 似力= 卅2 妒b o e i i 圭q ：、= i i ( c 0 - - a r u ) 盯 + s e ) o ( v + e ) 2 s 2 e “o v s e 2 e 其中e = ( 1 ，1 ，1 ) 7 r ” i 殳r * n r , 分别是( 3 1 3 ) f 1 ( 4 1 ) 的可行解集，z = 7 ，矿) 7 r “， 丸j ( z ) = ，+ e x v , + s ) 一2 ，纯j ( z ) = q v 一8 2 ， 并且 屯( z ) = ( 屯，( z ) ，屯：乜) ，噍。( z ) ) 1 ， 亿( 2 ) = ( ，0 ) ，纯：( ：) ，0 ) ) 因此 r e , j ( z ) = ( v + g ) q + ( “，+ s ) e m + ， v 吼j 乜) = v i e s + “，e ，“， ( f = 1 ，2 ，哟 v 丸( z ) = ( r e , 。( z ) ，v 屯，( z ) ) ， v 吼( z ) = ( v 见j ( ：) ，v 吼，( z ) ) 其中t r 2 ”( f = 1 ，2 ，所) 是第f 个元素是l ，其余的元素全是0 ， 对于函数f ：砒- - i t r “，定义函数，在点z r “的积极约束指标集为： i ，( 力= f ( 力= o 定理4 1 1 我们有f = 亿。e ，并且任意的s 0 ，有 k ( z ) n i “( z ) = 彩 证明：首先，显然有l r , - n 。目职，设z n 。e ，则对v s o ，有 m 叶s 2 ，u y , + ( 坼+ u ) 0 因此，有e + ( 虬+ v j ) 0 ，让占_ o ，则有 坼v f = 0 ，和q + h 2 0 f = l ，2 , - - - , 辨 从而有z f ，所d g f = n 。e ( 4 1 ) ( 4 2 ) ( 4 3 ) ( 4 4 ) 类二次规划反问题的研究 ( 反证法) 设对于某 o ，存在z e ，i e i t , ( z ) n i ( z ) 则 u y , = s 2 ， u , v , + s ( u j + h ) = 0 从而有 占+ 虬+ e = o 因此，o = 占2 m 一- - - - 8 2 + v 2 + = + 詈) 2 + 了3 s 2 o 矛盾 叶 定理得证口 定理4 1 2 对v 三f ，如果向量集合 v 峨，v v , l i e i 。( 刁n i ，( d 是线性独立的， 则对v 0 ，存在z 的邻域玑( 三) ，使得问题( 4 1 ) 在任意的z 以口) n e 处满足l i c q 证明：对坛f ，显然有。( 刁 0 ，存在芽的邻域阢( 三) ，使得， 对z 以g ) n e ，则 ( z 1 t ( ；) ，r ( z ) ( 三) 因此，屯，i f ) ，吼( 刃，i 仨。( 孑) n ，( 习，_ ，= 1 ，2 ，脚在点孑处是非积极的 所以，有 z + 占0 ， 叶+ 占0 ， i ( 劢 故而，由( 4 2 ) 知，定理成立 口 推论： 如果i f 是非退化的或下半水平严格互补的，即。伍) n ，g ) = o ，则定理4 i 2 显然成立 定理4 1 3 对坛f ，如果问题( 3 1 3 ) 的l i c q 在孑处成立，也就是 v u ，矾o l i 。( 刃，j ，( 刁 是线性独立的，则存在孑的邻域以( - ) 和常数于 0 ，使得问 题( 4 1 ) 在沈u ( i ) n e ，p ( o ，芎) ) 处满足l i c q 证明：由于“，v 的连续性，则存在i 的邻域以( _ ) 和常数f o ，使得v s ( o ，i ) 及 比u ( _ ) n e ，有i 。( z ) i 。口) ，i ，( 二) i ，( 习 设 a 7 v 屯( 力+ 卢7 v 纯= o 即 v 屯，( z ) + 只v 纯，( 力= o 。d k ( ：) ，e k ( ：) 1 ：1 ：t ( 4 2 ) ，“3 ) 知 【( 一+ p ) q + ( + g ) + ，】+ 只f ”巴+ 约。】= o( 4 5 ) k ( 7 ) j k ( z ) 由于 i ( ：) n i ( z ) = o 大连理工大学硕士学位论文 从而( 4 5 ) 式中i ， 又由于f 七( z ) 时坼+ o ，_ + s 0 ，所以 = 0 类似的可以得出歹k ( z ) 时，只= o 从而a = 0 ，p = 0 命题得证 口 4 2c - 稳定性 首先给出问题( 4 1 ) 的l a g r a n g e 函数 、 l ( u ，v ，a ，p ) = ，( “，v ) + ( 兄，屯 ，v ) ) + ( p ，吼( v ) ) ( 4 6 ) 其中f ( u ，d 是f 1 3 ( 3 1 3 ) 和( 3 1 4 ) 给出，a ，芦是足的l a g r a n g e 乘子 令f ：r “x r 一取“为 f ( u ，a ，弘，s ) 净 v 。z ( u ，u a ，) v 。z ( u ，v ，j ；l ，p ) m a x - ；t ，晚( 虬v ) m a x - # ，识( “，d ( 4 7 ) 如果何，可) r 2 ”是只的局部解，则l i c q 成立，因此存在l a g r a n g e 乘子 ，万) r ? ， 使得k k t 条件在何，市，| j ，豆，s ) 处成立，因此f ( 石，瓦a ，瓦占) =