（运筹学与控制论专业论文）求解一类mpec问题的abs算法研究.pdf

摘要 m p e c 问题( m a t h e m a t i c a lp r o g r a m sw i t he q u i l i b r i u mc o n s t r a i n t s ) 可以被认为是 双层规划问题的一般化推广，因而比双层规划应用更为广泛。它起源于经济问题，与著名 的s t a c k e l b e r g 对策论有着紧密的联系因此，m p e c 问题的研究在经济、工程设计、 对策决策等许多领域中都起着重要的作用，这就使得对该问题的研究愈加有意义。然而 该问题又是难解的，原因在于它的可行域既不是凸的又不是连通的，所以不能直接用现 有的非线性规划理论来解决。针对该问题，早期的方法有s q p 方法、隐式规划法、罚函 数方法等但这些方法的计算量都较大，在实际问题的解决中还存在着一定的困难。本 文中我们的目的就是寻找在实际中行之有效的算法 本文主要讨论了应用a b s 算法求解一类带有平衡约束的数学规划闯题( m p e c 问 题) 的算法。该算法的主要思想是：首先利用a b s 算法求解m p e c 问题中的非平衡约 束，将解代回原问题得到转化后的问题，再利用f 1 精确罚函数法并借助于m a t l a b 软 件求解转化后的问题。文中给出了收敛性证明，证明罚函数的最优解收敛于转化后问题 的最优解在非平衡约束多的情况下，a b s 算法的使用将大大简化约束条件论文最后 对算法进行了数值实验，表明了该算法在实际计算中的有效性 关键词：m p e c ；a b s 算法；互补约束优化问题；隐式l u 算法；罚函数法；f l 精确 罚函数法 a b s t r a c t m p e c ( m a t h e m a t i c a lp r o g r a m sw i t he q u i l i b r i u mc o n s t r a i n t s ) c a p r ib ec o n s i d e r e da s ag e n e r a h z a t i o no fb i l e v e ip r o g r a m m i n gp r o b l e ma n db ea p p h e dm o r eg e n e r a l l yt h a n t h el a t t e r i ts t e m sf r o mt h ee c o n o m i c a lp r o b l e m ，a n dh a sc l o s er e l a t i o nw i t ht h ew e l l - k n o w ns t a e k e l b e r gg a m e c o n s e q u e n t l y , t h er e s e a r c ho fm p e cp l a y sav e r yi m p o r t a n t r o l ei nm a n yf i e l d s ，s u c ha se c o n o m y , e n g i n e e r i n gd e s i g n ，g a m e ，d e c i s i o n m a k i n ga n ds o o n h o w e v e r ，b e c a u s ei t sf e a s i b l er e g i o ni sn e i t h e rc o n v e xn o rc o n n e c t e d ，t h i sp r o b l e m i s i n t r a c t a b l e t h e r e f o r e ，t h en o n l i n e a rp r o g r a m m i n gt h e o r y c a n n o tb ea p p l i e dh e r ed i r e c t l y t h i sp r o b l e mh a sb e e ns o l v e db ys q pm e t h o d ，i m p l i c i tp r o g r a m m i n gm e t h o da n dp e n a l t y m e t h o de t c n o n e t h e l e s s ，t h ec o m p u t a t i o ni nt h e s em e t h o d si sc o m p h c a t e d ，s ot h e r e e x i s t sd i f f i c u l t yi ns o l v i n gp r a c t i c a lp r o b l e m i nt h i sp a p e r ，o u rg o a li st of i n daf e a s i b l e a l g o r i t h m i np r a c t i c e t h i sp a p e rd i s c u s s e sm a i n l yt h ea p p l i c a t i o no fa b sa l g o r i t h mi n t oa c l a s so fm p e c t h em a i ni d e ao ft h i sa l g o r i t h mi sa 8f o l l o w s f i r s t l y ，s o l v et h en o n e q u i l i b r i u mc o n s t r a i n s b ym e a n s o fa b s a l g o r i t h m ，t h e no b t a i na t r a n s f o r m a t i o np r o b l e mb yt a k i n gt h es o l u t i o n i n t ot h eo r i g i n a lp r o b l e m s e c o n d l y , s o l v et r a n s f o r m a t i o np r o b l e mb yu s i n gt h e1 1 e x a c t p e n a l t yf u n c t i o nm e t h o da n db yt h ew a y o fm a t l a b a p r o o fo fc o n v e r g e n c ei sg i v e n ， w h i c hs h o w st h a tt h eo p t i m a ls o l u t i o no ft h ep e n a l t yf u n c t i o nc o n v e r g e st ot h a to ft h e t r a n s f o r m a t i o np r o b l e m w h e nt h ep r o b l e mh a sm o r en o n - e q u i l i b r i u mc o n s t r a i n t s ，t h e l l s eo fa b sa l g o r i t h mw i l lr e d u c ec o n s t a i n t st oal a r g e re x t e n t a tl a s t ，t h en u m e r i c a l e x p e r i m e n ti sg i v e nt op r o v et h ev a l i d i t yo ft h i sa l g o r i t h mi np r a c t i c a lc o m p u t a t i o n k e yw o r d s ：m p e c ；a b sa l g o r i t h m ；c o m p l e m e n t a r 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 ；i m p l i c i tl u a l g o r i t h m ；p e n a l t y f u n c t i o nm e t h o d ；l l e x a c tp e n a l t y f u n c t i o nm e t h o d i n 1 绪论 这一章首先介绍m p e c 问题产生的背景及其发展状况之后介绍a b s 算法产生的背景及其应用方面的进展。这里着重介绍a b s 算法在求解线性 方程组中的应用状况。最后简要介绍本文中所提出的算法中要用到的罚函 数法在求解约束规划方面的应用情况 1 1 m p e c 问题产生的背景及其发展状况 带有平衡约束的数学规划问题( m a t h e m a t i c a lp r o g r a m s w i t h e q u i l i b r i u mc o n s t r a i n t s ， 简记为m p e c ) ，是约束中含有带参数的变分不等式或带参数的互补系统的约束优化问 题它的应用十分广泛，可用于进行复杂的宏观与微观经济分析，在包括工程设计、经 济平衡、多层规划以及它自身的数学规划理论中都起到了很重要的作用因而，近年来 对此问题的研究引起了国内外学者的广泛兴趣 m p e c 问题一般被描述为带有两类变量的优化问题，一类是上层变量x ( e 渺) ，另 一类是下层变量y ( eg p ) ，数学模型为： r a i n f ( x ，y ) s t ( 。，y ) z ， y s o l v e s v i ( f ( x ，- ) ，o ( 。) ) 其中，zc 舻+ “，：舻+ ”一跣，f ：咿+ “一跪“，c ：舻一2 ”，v m ( f ( z ，) ，a ( 。) ) 代表 由f ( 。，) 定义的变分不等式问题。这样，ys o l v e s ( f ( z ，) ，g ( z ) ) 当且仅当y g ( z ) 并且满足 一g ) 7 f ( x ，y ) 0 ，v c ( x ) 我们注意到对于变分问题v i ( a ，y ) ，如果用g 表示一个可微函数g ：g p 一虢的梯 度，并且y 是跪“上的凸集，那么w ( c ，y ) 就是优化问题 1 大连理工大学硕士学位论文t 求解一类m p e c 问题的a b s 算法研究 m i n 9 ( f ) s t ， y y 一阶必要条件的另一种表达形式因此，m p e c 问题可以被认为是双层规划问题的般 化。当对任意的z 满足e ( z ) 兰乳? 时，带参数的变分不等式约束退化为带参数的互补约 束，那么，m p e c 问题等价于下述的互补约束规划问题( m p c c ) ： m i n f ( x ，y ) 8 t 扛，y ) z ， y 0 ，f ( x ，y ) 0 ， y t f ( x ，y ) = 0 ， 由于m p e c 问题的可行域既不是凸的叉不是连通的，因而此问题是非常难解的另 外，在任意可行点，它的约束都不能满足线性无关或m f c q 等约束规格因此，现有的 线性规划理论不能直接被应用到解决m p e c 问题中于是，针对此问题，正在被广泛使 用的方法就是寻找m p e c 问题的近似问题以便通过求解一系列的子问题得到它的解 一类方法是应用某种光滑或松弛技术，例如f a c c h i n e i 等【1 4 ，f u k u s h i m a 和p a n g 2 9 利用f i s c h e r - b u r m e i s t e r 函数来产生m p e c 问题的某种光滑近似。之后，s c h o l t e s 也提 出了一个类似的模型；另一类方法是利用罚函数技术例如，h u a n g 等利用f i s c h e r - b u r m e i s t e r 函数惩罚所有的约束f 3 9 1 ，而h u 和a a l p h 3 s 提出了一种仅惩罚互补约束 的方法；其它的方法还有序列二次规划方法( s q p ) 、隐式规划方法、内点法以及可行有 效集方法等 本文研究求解如下最广泛的一类互补约束优化问题 m i n f ( x ) s t 。q ( 。) 0i = 1 ，m ， 凰( 。芏， 江1 ，巩 ( ) g i ( z ) t 氆( z ) ：0l = 1 ，m ， 。 鲫( 。) 0 j = 1 ，一，p ， ( o ) = 0 = 1 ，q 第1 章绪论 其中， ，是r “上的实值连续可微函数，并且g ；，h i ，卯，h f 都是r “上的实值仿射函数 3 0 j 对于此问题已有许多算法，但是这些算法一般都只能在假定非退化的条件下保证计 算出b 一稳定点。然而这样的假设在实际中是比较严格的；或者是只能计算c 稳定点， 而得不到想要的b - 稳定点s c h o l t e s 和s t s h r 提出了一种信赖域方法，证明了在信赖 域半径不趋近于0 的情形下，此方法收敛于一个b 稳定点然而，在退化的情形下不能 保证信赖域半径不趋近于0 在s t s b _ r 的博士论文中给出了这种方法的改进算法1 9 9 9 年，f u k u s h i m a 和p a n g 2 9 】提出了一种基于m p e c 问题光滑逼近的连续方法在l i c q 和渐进弱非退化的假设下，当光滑系数趋近于0 时，光滑化的问题的二阶稳定点收敛于 m p e c 问题的b 一稳定点然而，这些算法也都是概念性的 2 9 3 6 】，在实际计算中存在 着困难。 1 2 a b s 算法产生的背景及其发展状况 a b s 算法是一类最初用于求解线性方程组的含有三个参量的投影算法，是由a b a f f y ， b r o y d e n 和s p e d i c a t o 于上世纪八十年代初完成的该算法在精确的意义下有限步终止 这一算法类覆盖了上世纪二十年代以来的与矩阵的降秩校正，投影阵结构、正交化与分 解以及求解线性方程的有限次迭代的直接法等有关的许多结果该类算法目前不仅可用 于构造求解线性与非线性方程组的具体算法等有关数值代数的问题上，而且还可以用于 求解线性和具有线性约束的非线性规划等问题从统一模式的观点来看，该算法类具有 很强的潜在的统一功能 a b s 算法现已被用于求解最小二乘问题，求解非线性方程组等关于优化中的a b s 方法的工作则最早见于s p e d i c a t o 与a b a f f y ( 1 9 8 7 ) 的一篇报告及诸梅芳( m f z h u ) 的一 篇文章中当a b s 算法用于求解具有线性约束的极小化问题时，发现众多的经典和有 教算法的原型，尤其是同投影和可行方向有关的算法类都对应着相应的参数选择。而从 s p e d i c a t o 等于1 9 9 0 年首次用a b s 算法研究构造求解线性约束最优化问题的可行方向 方法始，a b s 算法在最优化中的应用已取得众多进展如拟牛顿法统一公式的研究， s p e d i c a t o x i a 1 2 1 ，稀疏拟牛顿方程的研究，s p e d i c a t o & z h a o 7 ，可行方向法的研 究，夏尊铨、刘玉龙 6 0 】，s p e d i c a t o x i a 1 2 】线性规划中的a b s 算法研究，二次规 划、线性约束优化问题中的a b s 算法研究等等已有的成果表明，无论是在计算上还是 在理论上，a b s 算法是一类有发展前途与潜力的算法 3 大连理工大学硕士学位论文，求解一类m p e c 问题的a b s 算法研究 1 3 求解约束优化问题的罚函数法 由最优性条件可知，约束优化问题的求解要比无约束问题的求解复杂得多，也困难 得多。因而，我们自然想到，如何把约束优化问题转化为无约束问题来求解事实上，求 解非线性规划的最早进展就是基于罚函数的序列最小化方法，并且无约束优化问题的求 解目前已有一些比较有效的算法，如线性搜索法、最速下降法、共轭梯度法、牛顿法以 及拟牛顿法等 罚函数法就是通过求解若干个罚函数之极小来得到约束优化问瓢的极小点的方法 罚函数的基本点就是每次迭代增加罚因子，直到使整个罚项缩小到给定的误差范围这 里我们介绍如下几种基本的罚函数法：外罚函数法( 外点法) 、内罚函数法( 内点法) 、乘 子法、精确罚函数法 1 3 1 外罚函数法( 外点法) 对一般非线性规划问题： 定义罚函数 其中 r a i n ，( 。 s t c f ( z ) = 0z = i ，r - ，m q ( z ) 0i = m 7 + 1 ，一，m p ( ，口) = ，( z ) + 口多( 茹) ( 1 3 1 ) 通常取d = 卢= 2 。 显然，如果有了求解无约束最优化问题的好的算法与程序，用外罚函数法求解约束 问题是很方便的但是，该算法本身存在着比较严重的缺点比如说，每一个近似最优 解。往往不是可行解，而只是近似地满足约束，在某些实际问题中，这样的结果是不能 用的。其次，外罚函数法的主要缺点是目标函数的病态性质，面这种性质是由罚因子无 4 一 p 一 nz 盘 0n皿 。一 十z 臼 “：l | | z _ p 第1 章绪论 限增大所引起的在一系列的无约束极小化过程中，不断增大，当迭代过程趋于收敛 时，钆常常是很大的，这就引起了在计算机上实现的困难 1 3 2 内罚函数法( 内点法) 旭点罚函数法是利用内点罚函数求解不等式约束问题。如 m i n f ( x ) s t q 扛) 0t = l ，- ，m 内点法与外点法同样，具有海色阵病态的缺点，从而使求无约束极小越来越困难， 而且，内点法在线性搜索时，要控制步长以免跑出可行域外，使得线性搜索变得十分困 难，且对于一般的二次或三次差值的线性搜索法效果也很差在本文中不使用内点法的 原因是内点法仅适合不等式约束问题，不能处理等式约束 1 3 3 乘子法 乘子法虽然仍要求解一系列无约束极小，但由于o - 可取某个有限值，而且l a g r a n g e 乘子收敛到有限极限，因而没有罚函数法常常出现的病态性质，已有的数值试验也表明， 它远比其它罚函数法优越，收敛速度也快得多，所以至今仍是解约束最优化问题的最好 算法之一 在乘子法中，如果最优解处拉格朗日乘子为已知，则增广拉格朗日乘子函数的无约 束极小点就是原来约束问题的最优解但是，最优拉格朗日乘子总是无法事先知道，因 而，实际上只能通过求解一系列无约束极小问题来逼近最优乘子和最优解这就导致了 我们需要通过其它途径，构造出一个函数，它不需要依赖某些确定的而又未知的参数， 但它的无约束极小点恰好就是原来约束问题的解这样的函数就是精确罚函数这就是 本文中要使用它的原因 1 3 4 精确罚函数法 对于一般非线性规划问题( 1 3 1 ) 可以构造如下形式的精确罚函数 、p ( 叩) = m ) + a ) 1 + f i i n ( o ，岛( 。) ) m ( 1 舢) = 1 扛= m + 1 这种精确罚函数是z a n g w i l l 首先提出的，但他假定了( 1 3 1 ) 是凸规划问题，之后， p i e t z y k o w s k i 对一般情形证明了( 13 2 ) 是精确罚函数( 通常又被称为f 1 精确罚函数) 5 大连理工大学硕士学位论文：求解一类m p e c 问题的a b s 算法研究 精确罚函数的好处之一是可通过求解有限个无约束问题来精确求解一个约束优化问 题。基于非光滑精确罚函数( 1 3 2 ) ，对一般非线性规划问题( 1 3 1 ) 有： 算法1 3 1 ( 非光滑精确罚函数法) ( 步1 ) 初始化。给出。1 舒，设e 0 ，口l 0 ，c 1 为给定实数，k = 1 ( 步2 ) 利用初值口求解m i n p ( z ，f ) 来得到解x ( f f k ) ( 步3 ) 如果口k 声( x k ) e 则停止，x k 为原问题( 1 3 1 ) 的近似最优解；否则， 令f f k + 1 = c 9 ，k = k + 1 ，转步2 该算法与利用简单罚函数( 外罚函数、内罚函数) 的算法类似，所不同的是，由于 乒( o ，a ) 是精确罚函数，所以只要a 足够大就可得到精确解 f 1 精确罚函数( 1 3 2 ) 的主要缺点是；在约束边界，即使某个q ( 孟) = 0 的点孟处， 是不可微，而我们知道约束最优化问题的最优解一般是在边界处达到的，因此，这就导 致了不能采用无约束优化中的梯度型算法，如变尺度法等来求它的解为了弥补这一缺 点，可以从两方面来改进一是考虑可微的精确罚函数第一个可微的精确罚函数是由 f l e t c h e r 提出的，f l e t c h e r 精确罚函数的一个主要缺点是用到了目标函数与约束函数的 导数，因此当采用梯度型算法去求罚函数极小时就要用到这些函数的二阶导数，这就大 大增加了无约束极小化过程的工作量，因此，在实践中并不是一种有效的方法；二是研 究适合于这种不可微罚函数的方法，这也是本文中所采用的策略这里我们采用光滑化 的方法来将求解光滑化后的不可微罚函数近似为求解原不可微罚函数 1 4 论文结构及本文所做的工作 本文研究求解线性不等式组的a b s 算法和z - 精确罚函数法以及这些方法在求解 m p e c 问题中的应用本论文除绪论外由三个章节组成，论文结构及主要工作如下： 1 第二章介绍了求解m p e c 问题的历史发展、研究进展以及几种常用算法，主要侧重 于介绍本文中所要使用的罚函数方法。 2 第三章综合介绍了a b s 算法及其性质，以及介绍本文中的所给出的算例1 中所使用 的隐式l u 算法而且给出了a b s 算法的m a t l a b 化 3 第四章给出了a b s 算法在求解m p e c 问题中的应用，讨论了结合罚函数法算法的 收敛性。最后给出了算法的数值实验 6 第1 章绪论 4 第五章给出了一些后继的研究问题。 本文的结构框架图 2 求解 m p e c 问题的 几种 算法 7 2 求解m p e c 问题的几种算法 本章概述目前求解m p e c 问题的几种算法，它们的基本思想都是把平衡约 束问题转化为影式上相对简单的等价最优化问题，并在此基础上对已有的求解最 优化问题的有效算法加以改进这里我们侧重于介绍罚函数技术在求解m p e c 问题中的应用 2 1 s q p 方法 序列二次规划法( 简记为s q p ) 是求解非线性约束优化问题的有效方法，国内外学者 对此进行了大量的研究并取得了许多成果因此，如何有效的利用这些方法来解m p e c 问题，并且使得算法的条件减弱或使算法具有更好的收敛性，是近年来学者们研究的热 点之一以下介绍两类s q p 方法 2 1 1 磨光逐步二次规划法( s s q p 方法) 对如下的平衡约束优化问题： i n i n ，( 茁，翟) s , t 0 ，y ) z ， f ( x ，y ) + ：1 a ，v 幽( 。，y ) = 0 ， 、11 。 f 2 ) 0 a 上9 ( o ，y ) 0 定义2 1 1 磨光函数0 。：r 2 一冗 o “( ，b ) 三o + b 一、0 2 + b 2 + “，肛0 以下介绍一种求解m p e c 问题的s q p 方法一一磨光逐步二次规划方法( s m o o t h 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 ) 1 6 3 1 】。它的基本思想是利用磨光函数将问题( 2 1 1 ) 9 大连理工大学硕士学位论文t 求解一类m p e c 问题的a b s 算法研究 转化为如下的普通约束优化问题进行求解： m i n ，( o ，y ) s t ( o ，y ) z ， f ( x ，y ) + ：= 1 九v v 矾( z ，) = 0 ，( 2 1 2 ) w = 9 ( x ，g ) ， 丸( 埘，a ) = 0 其中， 。( ，a ) e ( 审。( w 1 ，a 1 ) ，庐。( 叫2 ，a 2 ) ，一，咖。( z ，a ) ) 1 假设上水平约束不含变量y ，且z 为紧集，上水平约束为一致强单调变分不等式，文献 14 】提出了求解( 2 1 1 ) 的磨光连续方法其基本思想是给定的正参数序列 鲰) ( 一o ) ， 精确求解x j 链的非线性约束优化问题( 2 1 2 ) 的点序列，并在适当条件下证明了该序列的 聚点为原问题的k k t 点f u k u s h i m a 等人指出 3 1 ，对每一个m 精确求解( 2 1 2 ) 的 k k t 点一般来说是费时的因此，【3 1 】提出了求解下列线性互补约束优化问题的一种 不同于f 1 4 的s s q p 算法 m i n ，( z ，y ) s ，t ， g x + 口0 ， w = n x + m y + g 0 上u 0 其中，n 尼“，m r “”，q 月“为已知矩阵和向量 该算法对给定参数m ，仅执行一次s q p 迭代步，通过调节蜥一0 和利用对某个 精确罚函数的某个线搜索，在适当条件下证明了算法具有全局收敛性，但该算法也要求 上水平约束中不含有y ，迭代序列的聚点满足严格互补条件 将s s q p 方法推广到求解非线性互补约束优化问题其中，上水平约束可以含有变 量y ，但不含有非线性等式约束。虽然 1 6 】指出了上水平约束中含有等式约束的重要性， 但算法中子问题的相容性问题使得该方法用于求解后者还存在着一定困难此外，在严 格互补的条件下，建立了类似 3 1 的收敛性结果 2 1 2 分片逐步二次规划法( p s q p 方法) 以下介绍另一种求解m p e c 问题的s q p 方法分片逐步二次规划法( p i e c e w i s e s e q u e n t i a lq u a d r a t i cp r o g r a s n m i n g ) 5 3 。该算法是将求解普通约束优化问题的逐步二次 规划方法的思想用于求解平衡约束优化问题( 2 1 1 ) 1 0 第2 章求解m p e c 问题的几种算法 假设，只g 二次连续可微，下标集 ，如是集合 1 ，2 ，z ) 的一个划分，且满足 三 ，m ( 。) 0 ) ， ( 2 1 3 ) 如24 ( z ， ) 三 i g i ( z ) = o 0 ，v i = 1 ，2 ，m 。对给定的牙，定义下列问题为问题( 1 1 1 ) 的松弛问题； m i n ，( z ) s t g ；( 。) = 0 b ( 。) 0 甄( 。) 0 甄( z ) = 0 鲂( o ) = 0 衄( o ) = 0 i 丘， i 口， e 序 i 彳， j i ； 1 ，2 f j 1 ，2 p ) 订 ( 2 3 ，2 ) 称互补约束优化问题( 1 1 1 ) 在可行点孟处满足线性无关约束规范性条件( 简称 l i c q ) 是指如下向量组线性无关： v g ( 岳) ：i a u 口 u v 上矗( 牙) ：i 厅u 彳) u v 毋( 孟) ：j du v f ( 孟) ：lej 在该条件下，松弛问题( 2 3 2 ) 的任何局部极小点一定是该问题的k k t 点不难写 出问题( 2 3 2 ) 的k k t 条件是： 1 4 第2 章求解m p e c 问题的几种算法 v ，( z ) 一炬地v g t ( z ) 一e f 口吼v & ( z ) 一e z w w h d x ) 一讵，w w h d x ) + e j x v g j ( x ) + e t j p i v f 如) 啪0 ，g 口( z ) 0 ，u 吾唧( ) = o ， 叫口0 ，鳓扛) 0 ，叫吾月j ( z ) = 0 ， a 0 ，9 ( 。) s0 ， r g ( x ) = 0 ， g a ( 。) = 0 ，上l ( z ) = 0 ，h ( x ) = 0 ， 如果原问题( 1 1 1 ) 的可行点圣满足上述k k t 条件，l u o 等 5 3 在线性无关约束 规范性条件下证明了孟一定是( 1 1 1 ) 的b - 稳定点因此，要寻找原互补约束优化问题 的b 一稳定点，只要寻找松弛问题的k k t 点。为此，构造如下的非精确子问题： l l f 5 ( 嚣，u ，a ，p ) l i o ( 2 - 3 - 3 ) 其中，s 是问题( 2 3 1 ) 中的磨光系数。矿= 。( e ) 表示求解子问题的非精确程度，函数 f 5 ：r “+ m + p + g _ r “+ m 押+ q 定义为： v ，( z ) l f r ( z ，u ，a ，卢) = l 【 如果令 则函数p 可简写为 銎l u i v 垂i ( z ) + e j j v 彩( 。) + e ! e g # l v h z ( x ) 舻( z ) 1 5 ( z ) zh p + 茁 田， 入 阿 +嚣壬u 。 一z ， 兰 p uzl 大连理工大学硕士学位论文：求解一类m p e c 问题的a b s 算法研究 v 。上5 ( z ，让，a ， 垂5 ( z ) r a i n ( a ，- g ( x h ( x )i ) 定理2 3 1 如果非精确子问题( 2 3 3 ) 的解x 具有以下性质： ( i ) 中( 矿) = r ，且l 惦| i 0 ，函数的 水平集为： 工( 6 ) = ( 髫，y ，w ，z ) r ”兄罂r 2 ：曲( z ，y ，w ，z ) 6 ) 其中，6 0 是任意常数。另个函数是问题( 2 4 4 ) 的罚函数 r 扛，f ， ，z ) if ( x ，y ， ，；) + o 咖扛，y ， ，z ) ，v ( x ，y ， ，z ) r “r 罂刷 其中，q 0 是算法中要适当调节的罚参数与【5 3 】中用到的罚函数( 2 4 3 ) 相比，这里 的罚函数r 是j 1 精确罚函数，而且仅方向可微 设0 ，为n 阶对称正定阵，它也是目标函数的近似海色阵，第v 步迭代过程是指解 下面关于变量如兰( 如，d y ，d w ，d z ) 的二次规划问题： 1 8 ” 丁 叫+z叫 v 嚣 n m ：l 十 、， o0 第2 章求解m p e c 问题的几种算法 r a i n 。：”， d f 。d s + ；( d 。) t 仉d x s t g i d x a l g i x ”， g t d z 0 ， g i d x 毗一g i z ”， e d x + a d y + b d w + c d z = 一r ” 肌d y + k d w = 一匕w ”+ 口，e 其中，盯，( 0 ，i ) 为给定常数，兰r ( ，y ”，w ”，) ， 下定义： 其中 不等式 p ( ) ! i ：a i g i x ” o ) o ( ) j 0 ：a i g t = o ) 一( ) i i ：o t g i x ” 0 ) | 1 d 尹| | 、 i ，+ ( o ”) ， j 。( ) ， ( 2 删 i i - ( ) ， 下标集p ( ) ，j o ( ) ，r ( ) 如 c 惶c ( ( g t 一。；) + m 。，y ，w ，z ) i + ( 矿) h y ) 卜b ”) b 1 当不等式( 2 4 6 ) 不成立时，则要求解问题( 2 4 7 ) ： ( 2 4 6 ) m i n ，。：d f s d s + ( 出) 7 吼d x s t g f d x a l g t z ”，i j + ( 。”) ， g ，d x 0 ，i i o ( ) ， g i d z 漏( 啦一o i x ”) ， i 一( z ”) ， ( 2 。4 7 ) e d x + a d y + b d w + c d z = 一， 肌曲+ k d 训= 一k u ”+ o 肌e ， ( 如) 7 d x c ” 1 9 大连理工大学硕士学位论文：求解一类m p e c 问题的a b s 算法研究 算法2 4 1 ( 改进的内点罚算法) ( 步1 ) 初始化。适当选取初培值( x o ，y o ，w o ，z o ) r ”r 罂r 2 使得 芦掣r a i n 谚w 。l 1 ；取口，m i n 厅，西，q o 舻“为对称正定阵，置= 0 。 ( 步2 ) 求解子问题( 2 4 5 ) ，得到唯一解( 挣，妒，d 驴，d 尹) 。如果d 妒 j 、，歹，则令( 如”，d 旷，d 矿，d z ”) = ( d 护，d 严，d 舻，d 尹) ；否则，求解子 问题( 2 4 7 ) ，令它的解为( d ，d y ”，d w ”，d z ”) 利用( z ”，y ”，w ”，) 和( 如”，d y ”，d w ”，d z ”) ，修正罚参数为q ，。 ( 步3 ) 计算f ，如果于：= 1 ，则令f = 1 一，且jt l , p l t ”。其中，是 使下述不等式成立的最小非负整数： 咖( ( r ) ，旷( 7 - ) ，叫”( r ) ，( r ) ) 机 r ，( 扩( 7 - ) ，旷( r ) j ”( r ) ，( r ) ) 一只。( 矿，y 7 ，w ”，z ”) ，y ，丁f m ，：( c 蟛) r d ，口。( 一。“一扛一) g d x ”) + r i 9 1i n ( ，u ，z ) i + ( 1 一。) ( g ”) r w ”1 一7 7 _ p ( 步4 ) 令( 。”+ 1 ，y ”+ 1 ，t 廿”+ 1 ，z ”+ 1 ) = ( x ”，y ”，w “，z ”) + _ ( d 茁”，d ”，d t u ”，d 2 ”) ， 并检验新的迭代点( x v + 1 ，y ”1 ，w ”1 ，z ”+ 1 ) 是否满足给定的终止条件 如果满足则停止；否则，重新选取对称正定阵q 蚪l 以及常数o + 1 使之满足0 盯，+ l 盯。，置1 - = + 1 ，转步2 2 4 3 精确罚函数法 除了上述两种详细介绍的罚函数法外，通常在求解m p e c 问题中被使用的罚函数 法还有精确罚函数法。精确罚函数在求解约束优化问题中已有很长的一段历史 5 4 ，在 b u r k e 2 6 1 的一篇文章中曾做出过有关精确罚函数理论的全面回顾，并且给出了一种较好 的方法，可以导出许多结果。精确罚函数是求解普通约束优化问题的重要方法之一，有 关这方面主要研究成果可参看文献【3 4 1 1 3 7 1 1 5