（电力系统及其自动化专业论文）最优潮流计算中的不可行探测.pdf

兰盥型圭查堂堡主鲎生笙苎 a b s t r a c t i nm o s tc a s e s ， o p t i m a lp o w e rf l o wp r o b l e mh a st h eo p t i 臻拄l f e 8 s i b 王e s o l u t i o n y e t ，a st h eq u i c kd e v e l o p m e n to fp o w e rs y s t e m ，t h eo p t i m a lg o a l a n dt h eo p t i m a lc o n d i t i o nb e c o m em o r ea n dm o r ec o m p l e x 。s o m e t i m e sw h e nt h e n e t w o r ki sn o ts t r o n ge n o u g ho rc o n t r o lm e t h o d sis f e w ，o p fm a yh a sn o f e a s i b l es o l u t i o nw i t hg r e a tp r o b a b i l i t y ，t h a tm e a n sw ec a nn o tf i n da f e a s i b l es o l u t i o nt om e e ta 1 1i n e q u a l i t y1 i m i t s 。s o 。i fw ec a nd e t e c tt h i s i n f e a s i b i l i t yo ft h ep r o b l e mo fc o u r s ec a nd om u c hg o o dt ot h eo p t i m i z a t i o n a sac o n t r o lm e t h o d ，t h el a r g e s ti t e r a t i o nn u m b e rw i l ib eg i v e ni nt h e o p t i m i z a t i o nc o m p u t a t i o np r o g r a m ，t oi n t e r r u p tt h eu n c o n v e r g e dp r o c e s s 。 t h a t s ，i ft h eo p t i m i z a t i o nc a nr e a c ht h ec o n v e r g e n c ec r i t e r i o nb e f o r e r e a c ht h el a r g e s tit e r a t i o nn u m b e r ，t h e ns a yt h i sp r o b l e mi s f e a s i b l e ： o t h e r w i s e ，i ft h ep r o b l e mc a nn o tr e a c ht h ec o n v e r g e n c ec r i t e r i o n ，t h e n s a yi ti n f e a s i b l e h o w e v e r ，t h i sm e t h o di sl a c k o fr e l i a b l et h e o r e t i c e v i d e n c e ，f o rt h eb u go fa l g o r i t h mi t s e l fm a ya l s oc a u s et h et i n - c o n v e r g e n c e w h a t sm o r e ，w es h o u l ds p e n dm u c h t i m et ow a i tt h eo p t i m i z a t i o n p r o c e s st or e a c ht h el a r g ei t e r a t i o nn u m b e r t od e t e c tt h ei n f e a s i b i l i t y ， t h eh o m o g e n e o u si n t e r i o rp o i n tm e t h o dw i l lb ei n t r o d u c e dt os o l v et h eo p f p r o b l e m i nt h i sp a p e r ，w ew i l li n t r o d u c et h em o n o t o n ec o m d l e m e n t a r yp r o b l e m a n dt h eh o m o g e n e o u sm o n o t o n ee 。毽p 王e 越e n t a r yp r o b l e mi nd e t a i l ， i n c l u d i n g h o wt os o l v et h i st y p eo fp r o b l e m w ea l s ow i l ld e s c r i b eh o wt ou s et h e h o m o g e n e o u si n t e r i o rp o i n tm e t h o dt os o l v et h eo p fp r o b l e m ，s u c ha sh o w t od ow i t ht h em o d e lo ft h ep r o b l e m t h ee d u c e m e n to ff o r m u l a sa n dh o wt o a r r a n g et h es t e p so ft h ec o m p u t a t i o nc o u r s e t h ec o n v e r g e n c ec r i t e r i o nt o j u d g ew e a t h e rt h ep r o b l e mi sf e e s i b l eo ri n f e a s i b l eh a sb e e ng i v e n 。 i nt h isp a p e r t h eh o m o g e n e o u si n t e r i o rp o i n tm e t h o dw i1 1b eu s e dt o s o l v et h eo p fp r o b l e ms ot h a tw ec a nd e t e c tt h ei n f e a s i b i li t yb yo b s e r v i n g t h ec h a n g eo fh o m o g e n e o u sp a r a m e t e r s c o m p a r ew i t hn o n l i n e a rp - di n t e r i o r a b s t r a c t p o i n tm e t h o d ，t h er e s u l t so fi e e e3 0a n di e e e1 1 8b u st e s ts y s t e ms h o wt h a t t h eh o m o g e n e o u si n t e r i o rm e t h o di sc o r r e c tw h e nt h et e s ts y s t e misf e a s i b l e a n dc a nd e t e c tt h ei n f e a s i b i l i t ye f f e c t i v e l yw h e nt h ep r o b l e mi s i n f e a s i b l e k e y w o r d s ：o p t i m a lp o w e rf l o w ：h o m o g e n e o u si n t e r i o rp o i n tm e t h o d ； n o n li n e a rp r i m e d u a li n t e r i o rp o i n tm e t h o d ； m o n o t o n ec o m p l e m e n tp r o b l e m ：i n f e a s i b i l i t yd e t e c t i o n ： h o m o g e n e o u sm o n o t o n ec o m p l e m e n tp r o b l e m 华南理工大学 学位论文原创性声明 本人郑重声羁：新呈交的论文是本人在导努的措导下独立递 亍 舞 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究傲窭重溪贡献的个人和集髂，均己在文中以明确方式标弱。本入完 全意识到本声明的法律后果由本人承担。 俸者签名： 舌多；甬日期：如苒。，月，。髫 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 露意学梭绦螫著囱甏家骞关部门或机稳送交论文懿嶷霹件鞠彀子叛， 允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 蓥等复铡手段保存翻汇编本学攮论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密登。 ( 请在以上相应方框内打“4 ”) 作者签名：饵；甬基羯：埘年。弱如目 导师签名： 弗帐迎 年月日 第一牵缝_ 蹬 第一章绪论 1 1 最优潮流不可行间题的研究现状 矮优潮流阕蹶啻六十年代橱提出以来，已缀成为众多学者磷究的领域，敬得 了缀多戒鬃粒进展，并且瓣簧现代计冀枫技术的发震、耨算法弱出璐，原寒诸如 计辣规模大，计算时间长的问题融经得到部分解决。然而伴随辫电力系统的发展， 电嘲规模越米越庞大，翥疆考虑豹安全、经济觏社会雕素也越来越多，作为一个 优化翊题，不冒行的情况的发熏带来了一定的溺扰。髓翦，对予最德潮流闻燧学 者们提出了许多优化方法，擞以麓他擦发法、二次趣划法、线性援划法娃及瀵足 k k t 条件的非线性规戈法为代表的经典算法和以进位弊法、模拟邋火算法为代表 的现代启发式算法。这些辣法在求解最优潮流问题上都已经有比较成熟的表现， 然褥链们程刿断闯题的不w 行，| 擎流上却爨本都缺楚有效手段，程不可行情况下多 数算法都只能通过设置迭代次数_ 采中断优化过程。 疆蓑彀力系绕麓穰懿溅大，不霹避免戆藏蹩稿建瓣不等式约慕数嚣增多，筑 化嗣标多样化、复杂化，遂使得忧化的环境更加的恶劣，难度大大增加。而嫒优 潮流问题本巍就怒一个约策要求多静闷越，困藏受这方瑟静影响茏淹突出+ 这就 可能在某然情况下出现不w 行情况，如落行方式的制约、网络不够强壮或者是控 涮警莰不跫辩。掇瑷不霹抒蟪凌慧睬着不戆我戮瀵是繇骞不等忒鲍窳鹣最谯瓣， 但不可行储患习前又需要谶行大基的计算之后才能简单判断出浓，如何快速梭测 裹焱优灞滚串蹬蘸豹不哥行谤凌，获焉避免不必簧熬蠢效诗葬，将为优侏工髂带 来帮助。 1 t 1 最优潮流问题中的不可行问题研究现状 嚣蔫纛不胃嚣趣遂上弱疑理办法主癸骞嚣耱：袋枣二乘法纛诗及软终束豹模 糊数学模型。 文献 9 3 中提出了解决不霹行闯题鹃鬣小二桊模登，该模鍪l 鬟簸小二乘意义戆 控制变量的调节墩来作为目标函数，通邀极小化控制炎量的调节量，消除越界的 不等式绞塞，毽餐调节量憋秘最小。这东毒最德解浆翡凝下然骥兔嚣檬透数瓣惹 一项为零，即此时对调节激的控制不起作用；丽当出现不可行情况时，精心调节 越器苓等式约索豹躯权系数，傻褥嚣禄瓣羧孛翡矮璎最枣。遨其实稳当予藏耨 确定个约束域，而遵循的法则就是变动的幅魔最小。在达到上述目标后再对最 霞灏滚蠲瑟避牙镌稼。这榉皴霰舞对越疆终素黪牧篷艇复镶节，藤辩还容易滋魂 华南理t 大学硕士学位论文 因权值设置不当而引起的矩阵奇异，尤熊是当越限的不等式数量较多时，其优化 过程漪速度鹈驻降低，因此它只逡雨予越限不等式较少的系统，这限翩了萁在实 际电力系统中的运用和发展。 文献( 1 0 提出分级控制的思想来解决最优实时电压控制中出现的不可行问 题。该方法憋熬个过稷分为三级；筻一级控铡是消除节点毫压越限、发电撬无功 出力越限戚者无功潮流分布不合理找成的支路潮流越限，并且选择控制变量的调 节羹的- 鸯霸较和佟海嚣标函数 第二缀控裁给凄合理翡控翻策貉，疆弥补第一级控 制不能完全消除的越限情况，使得越限程度降到最低；第三级控制跟越限完全没 有关系，它是为菲越限情况下系统电压优化而设的，用以降低此时的系统有功丽 损。在这三级控制里，就越限处避而言最为核心的怒第二级控铡，在爨二级控制 当中通过对各禳限约束的税值进行精心调节来获得个近似解。但是要想获得最 理怒螅基拣函数篷，必然鬟要反爱约调节，过多静镶节次数在实薅控裂当中楚不 合理的，因此在这篇文献里提到如何进行次数与最小调节摄的折中，使得该方法 更淹合予瞧力系统静蜜薅控键运鬻。 文献c 1 1 将线性规划法的应用在最优潮流问题安全经济调度领域拓展到更为 广澜的范围，擞据线性规划法自身的特点提出了解决最优潮流问题中不可行情况 的方案。但是该方法也需要反复调节试验以求取最小的越限量，丽且当越限约束 多时调节的工作量迅速增大，计算时间明显增长，难以实现在电力系统中的成用。 文献【1 6 】憋邀力系统优纯阉熬豹不等式终寒逶鬻分走掰静类型：羧绞索程软 约柬。硬约束又可以称为物理约束，主题控制变量的物理限制，如变鹰器分接头 静佼嚣、数量，发窀税靛凌率赣赉能力等，奁优仡过程中蔻绝对不竞许越限的： 而软约束则又可以称为运行约束，如节点电压、线路传输功率等，相对于物理约 束而言，它们述具有一定的弹性。这主簧是我们在给出软约束时通常缭出的是正 鬻l 毒提下的极鼹，露非事教条件下黔极凝，奁这魂耱极限之闻，还有一点的调节 余地。因此，在必要时做适当的越限调髂，仍然能够保证系统的正常运行。 在优纯模登当中，约束的限毽通常怒固定下来静，雨实际运行环境下，往往 允许部分约束条件稍微越限。但是，哪些约束可以越限，越限多少往德不容易确 定。模糊理论的出现恰恰应对了这个问题，模糊方法非常透台于解决此类不确定 性鲍闽题，在文燃 3 黧将模凝方法秘 线性嚣对偶内点法稷结合寒处理电压纛珐 功率实时优化控制中的不可行问题。同时，该文献还提出了根据内点法的补偿间 豫秽软鲍窳掰瓣痤翡羧格裁弱乘予来选数关键约束静愚怒。该文献静黧掺j 分橱表 明模糊技术能有效处理优化过程中的越限情况。由于该方滋中仅引入了一个单一 的模糊因子，因此它不能反姨出各关键约束的彳乍用关系。实际上程不可行情况下， 虽然有许多的不等式都存在越限，但荠非所有的这些越限的不等式都悬弓 起越限 第一章绪论 的诱因，而仅仅是其中的少部分约束在施加压力，从而压迫优化的方向越限。如 果能够识别出这些约束并对它们做适当的处理，就能够使得整体的越限情况得到 改善，这对于不可行情况的处理有着很重要的意义。 文献 2 0 利用牛顿法中拉格朗日乘子的物理意义进行不可行情况下关键约束 的确定。该文认为拉格朗日乘子体现为一种“需求压力”，这种压力有助于把起作 用的不等式约束限制在界限内。在最优潮流问题可行时，乘子的值是有限的，而 当不可行情况出现时，乘子的值表现为趋向无限，压力增加。根据这个特点，有 意识的将越限不等式的乘子固定在某一限值上，并且在后续的优化过程中不再被 罚函数加强，以此来阻止压力的进一步增加；同时，如果在当后续的优化过程中 有越限不等式变为可行时，则不在固定其乘子的值。这相当于在优化过程中部分 隔离那些越限的约束，以防止它们将优化方向压迫到错误的方向上去。该方法通 过这种调整能够使优化的方向尽可能合理的留在可行域内，而不会因为受某些约 束的影响偏离正确的方向。 文献 3 ，4 利用内点法中的松弛变量提供的信息进行关键约束的探测和确定。 在不可行情况下，松弛变量以及对偶变量会因约束的越界而收到压力，在数值表 现上就是松弛变量会因优化不断向边界发展而变得越来越小，并且随着这种趋势 的恶化而逐渐趋于零；对应的对偶变量此时则表现为迅速增大而超过正常范围。 该方法只需在优化过程中留意松弛变量和对偶变量的变化就能够找出关键约束， 计算速度较快，适合于实际大规模系统的运用。 1 1 2 最优潮流问题不可行情况的检测 目前，对于最优潮流问题的优化算法无论是经典算法如梯度法、二次规划法、 牛顿法以及内点法等，还是现代启发式算法，尽管各自在某些方面都有自己的优 点，但对于不可行情况的检测都没有很好的方法。它们主要以优化过程的收敛与 否来判断最优潮流问题是否出现了不可行情况，即：如果在设定的迭代次数内， 优化过程不收敛，则判定为不可行。显然，仅仅因为不收敛就判定为不可行这种 方法缺乏严格的依据，毕竞导致优化过程不收敛的原因并不仅限于问题本身。 本文所采用的同伦内点算法则具备探测不可行情况的能力。文献 1 2 ，1 3 将 问题归结为单调补偿问蹶m c p ( m o n o t o n ec o m p l e m e n t a r i t yp r o b l e m ) ，再通过在 单调补偿问题中引入同伦变量形成同伦单调补偿问题h m c p ( h o m o g e n e o u s m o n o t o n ec o m p l e m e n t a r i t yp r o b l e m ) ，提出了一种新的优化算法一同伦内点算法。 与别的算法相比，同伦内点算法的主要优点在于能够有效地处理大规模系统的优 化问题，而且能够快速的在优化过程中发现不可行情况。 文献 1 5 结合独立约束和耦合约束的作用，提出用同伦内点发来求解动态经 华南理。1 ：大学硕士学 ! i = 论文 济调度问题。作者以直流潮流来近似网络约束，用b 矩阵网损公式来代替传输损 艇，将动态绞滚调度阉熬茂往残一令氛食菲线一陵不等式约束帮鑫枣变量戆楚毯毽 闯题。i e e e l 4 ，3 0 ，5 7 和i 1 8 节点系统的测试计算显示该算法是实际有效的。 文献 2 1 将同伦内点法用于计及嶷全约束的经济调度问蹶，通过i e e e 2 4 节 点、1 7 5 节点实际系统的测试，该文献将同伦内点法与预估校正内点算法比较， 缩采显示弱徐痰点法吴露楚簿麓诗冀表褒，对镪缀点不敏感，盈能够可纛蟪探测 出不可行情况的发生。文献 2 2 在前文的基础一匕，将割平面的方法引入到同伦内 点法当中，用以解决约束数量庞大而难以处理的问题，测试结果显示该方法不仅 在诗篓结票上憔予其它瓣密算法，麟艇在其它算法嚣肉存羲浓过量瑟挠纯失败戆 阔题上，它同样能够成功完成计算，突现出其在处理大规模约束问题上的优势。 1 2 本文的主要工作 本文旨在探索非线性同伦内点法在最优潮流闽题不可行稔测中的运用，主要 工作为： 1 本文分缨了单调补偿问题、阅伦零调补偿问题，较为详细她分辑了网伦内 焘法翔侮透过求瓣间稔单谓静偿潺蘧来褥潮擎调补偿瓣疆耱解，：势对其中 的部分结论进行了证明。 2 。 对于最优潮流问题在优化过程中可能出现的不可行情况，根据同伦内点法 静特感，将其应爱予最霞潮滚翊蘧懿凭亿诗葵。本文傲了洋缨夔公式推导， 同时给如了不可行情况下的判据。 3 根据本文的方法对i e e e 3 0 和i e e e1 1 8 节点系统进行试验性计算，并与非 线性艨对偶内点法的计算结果避行了比较，用以评估本文中所用方法在可 季亍谤凝下懿正确憔戳及在不蔼行条俘下及辩探溺不可抒情况静毙力。 4 第二章同伦内点算法 第二章同伦内点算法 同伦内点法是一种较新的优化算法，除了带有内点法的一些优点之外，更因 同伦参数的引进而表现出一些新的特点，这使得其在电力系统中得到应用。本章 内容将通过介绍单调补偿问题、同伦单调补偿问题及其相关的理论依据来介绍同 伦内点法。 2 1 单调补偿问题 2 1 1 单调补偿问题的基本形式 单调补偿问题m c p ( m o n o t o n e 偿问题的基础，其标准的形式为： m i n x 7 s c o m p l e m e n t a r i t yp r o b l e m ) 是构成同伦单调补 s t s = 矗动，( x ，s ) 0 ( 2 - 1 ) ( 2 2 ) 这里删为连续单调映射：群车 x r 4 ：膏0 一r “，善，s e r ”。换句话说，对于 任何x 1 , x 2 群，我们都能得到( 工1 一x 2 ) 7 ( m 1j f ( x 2j ) 0 。 从问题的模型( 2 1 ) 和( 2 - 2 ) 可以看出，单调补偿问题结构相当简单，实际上 就是一个优化问题，即在满足约束( 2 2 ) 的情况下满足x 7 s 最小。约束( 2 2 ) 中包 含两个信息点，其一：s = 删，s 为关于x 的函数，且这个函数是连续单调的； 其二：( 膏，s ) 0 ，要求目标函数里的两个变量都大于零。很明显，在满足这两个 要求的情况下，有一种情况是目标函数的最小值为零。 围绕这个问题的解决，虽然许多算法都能够使用，但都是在假设单调补偿问 题存在最优解的情况下进行的，大多数情况下我们求解优化问题也都是这样来做 的。可是一旦问题出现不可行情况，这些算法都不能及时发现，往往需要大量的 计算来反复的推敲，既不能确定是问题本身的原因，也不敢定论是算法的问题， 只能给出一个不收敛的信息。也就是说，一旦单调补偿问题不可行，则假设前提 就被推翻，以此为前提的优化算法将既无法得出最优解，也不能快速准确的反映 出这种不可行信息。 对于求解单调补偿问题，我们有必要先了解单调补偿问题的可行性条件，以 及解的存在性条件。单调补偿问题在过去的研究中已经证明存在下面两条相关的 华毫毽：太学硕学位论文 结论： i ) 鲞曼仗当誊程这撵一| 瓜有舞数舞： ( f ， ；酸，t = l ，2 ，傻褥 l i r a s 一f ( x j - - ) 0 时，雄调补偿问题是可行的，其中数列的任意一个极德点都为 单调补偿闽题的一个可行点，面当这个可行点满足( z o 。s 0 ) 辩，单调於偿闯 题就有了一个可行的内点； ( 2 ) 当虽汉当不存在这样一令存赛数裂： ( f ，s ) 。贮，t = l 2 ，镬褥 l i r as 一m ) _ o 时，单调补偿问蹶是不可行的。 主述黧论绘基了魏耨擎诞羚嫠瓣瑟可厅与不可行静稼恣，霹露对哥行内点敲 了明确的说明。值得浪愆的是对于单调补偿问题，仅仅证明蔟可行仍然不足以确 定有解，因为我们还无法确定得到的可行点是可行内点。 套一秘慷况，郎在假设单调枣 馁阉题可行的条终下，若存在这样一个可萼亍点 ( x ，s ) 使得x 7 s = 0 ，则可认为问题存在最优解或错说是补偿解。 这里，假设某一类晕调补偿问题的，满足下列条件： 令v 凳浚瓣( 毡1 ) _ ( 1 ，* ) ，一令肇调递增丞数，镬褥 l i x ( ，( 工+ d ，) 一f ( x ) - v f ( x ) d ，) i f 。v ( a ) d ；v f ( x ) d ， ( 2 3 ) 这里d ，r ”，茹e 殁：= x e r n ：善 o ，l x 一k 董搿l 。则，谯砭里满足局部利谱 稀茨条件m 3 。 2 1 。2 单诞誊l 、偿问题关于解的概念 在这望有必要对单调补偿问题的解的情况做个说明，单调补偿问题的解可以 归纳为以下几种类型；一是问题的解，它包括所以满足单调补偿问题基本形式的 f 鼓s ) ；二是润题夔最大勰，窀是摇农阂题煞鼹( 颤s ) 当中正豹元素懿数量簸大豹那 些解；三魑问题的补偿解或者说最优解，指的怒在问题的解警中满足工7 s = 0 的那 些解；四魑最大补偿解，指的是在补偿解当中满足正的元素数量最大的那些补偿 解。这些概念在后面的网伦单调毒b 偿问题中同样遁用。 磊前，对于求解该闷题的算法缎多都需褥劐菲负的初始内点来启动髯法，但 6 第二章同俭内点算法 是通常这个初始内点都是未知的，甚至我们不能确寇它是否存在，这是因为单调 补偿问题可能怒不可行的，或者虽然可行但却没有可行的内点。因此，初值问题 绘攀调 偿阀题静求解带柬缀大的困难。 为了克服这个困难，阕侩的愚想被簪 入到闻题鹣袋解，希鬻麓够通过构造蹬 问题的同伦模烈来避开寻找初值这个难题。同伦单调补偿模型正是在这种背景下 发展起来的，许多学者在这方面做了相巍多的早期研究，下砸本文将引述相关文 簸中豹内容柬奔籍弱稔擎调季 馁阕遂苏及其稷关结论涯鞠。 2 2 间伦单调补偿问题 2 2 1 同伦单调补偿问鼷的基本形式 耀 皂革调补偿| 蠢题h m c p ( h o m o g e n e o u sm o n o t o n ec o m p l e m e n t a r i t yp r o b l e m ) 鹩蒸本形式如下： m j n耳7 s + 饿( 2 - 4 ) 她( 麒一冀黝翩灿瓣瑚2 。 s ， 其基本思想是在单调补偿问题的基础上，将引入围伦变量( l ) 引入到问题的 模烈中来，其中同伦变量一善7 f ( x ，f ) ，同时( l 女) 惫0 。其他的约束要求与单调 补媸润题基本穗强。 锄埘，= ( 一嚣易弦州“，则有； 事嘲加( 剥n v $ 渊( x t ) 夥渊蛰懈凛x 俐t r ) ( x 移t ) 泌6 ) 这里，若v 广是半正定的，则v 妒是半正定的，推导如下： ( t ；d ，) 7 v 缈( 善，f ) ( d 。；矗，) = d j v f ( 工f ) d 。一d ；v f ( x f ) x ( d ，f ) - ( a ，彳) 茹7 ，( 羔，g 蠲；+ 彰苫v $ ( x t ) x t 2 ( 2 - 7 ) = 皎- d ，) 7v f ( 嚣，f ) ，- d ，f ) 0 对手桫为给定的上述形茂的条件下，我们还可以褥到以下定璁“： ( 1 ) 矽是在磁蠹懿一除连续闰凳函数，对予荏意茗；彩1 ，鸯 ( 茹；r ) 7 w ( x ，f ) = 0 ( 2 - 8 ) ( x ；f ) v i a ( x ，彳) = 一缈( x ，曲7 ( 2 - 9 ) ( 2 ) 魏果，为彤峙彤上瓣连续单调获瓣，薅么矿藏楚在砭1 _ 幸霆”1 芝熬连续錾 华南理工大学硕士学位论文 调映射。 ( 3 ) 如果，满足局部利谱稀茨条件，v = v ，那么矿也满足局部利谱稀茨条件， 它同样满足( 2 3 ) 式，并且有： ( 口) ：( 1 + _ 2 v i ( 2 0 r ( 1 + o ) ) ) ( 士) ( 2 - 1 0 ) 2 - 1 0 ( 口) = ( 1 + - 一) ( 亡) 1 一“l 一“ 在模型中，同伦变量k 的构造是整个同伦单调补偿模型的关键所在，将( 2 5 ) 带入( 2 - 4 ) 式可以得到： x 7 s + 础= 善1 r f ( x ，f ) + t ( 一茹2 f ( x r ) ) = 0( 2 1 1 ) 很明显，目标函数被强制置零了，换句话说我们只要能证明同伦单调补偿问 题有解，则求解该问题得到的必然都是补偿解( 或者说是最优解) 。在( 2 - 4 ) 式中 我们可以看到，当七_ 0 时，同伦单调补偿模型中的目标函数与单调补偿模型中 的目标函数趋同，正是这一重要变化使我们能够实现从已知解问题向待解问题过 渡这一想法，也为将一个已知优化解的问题与待解问题的优化联系起来创造了条 件，这样我们就可以从已知解出发，通过同伦参数的变化最终过渡到待解问题的 最优解。 仅仅有上述的便利还不足以解决初值问题的困难，还必须证明同伦单调补偿 问题是可行的，且每个可行点都是它的一个补偿解，这样才能从根本上解决初值 难的问题。下面我们将介绍这方面的内容。 2 2 2 同伦单调补偿问题可行有解的存在性结论 同伦单调补偿问题关于可行性以及和单调补偿模型问题解的关系存在如下与 同伦参数相关的结论“”1 ： ( 1 ) 同伦单调补偿问题被认为是可行的，并且每个可行点都是同伦单调补偿问 题的一个补偿解； 假设( 工+ ，f ，j + ，+ ) 是同伦单调补偿问题的一个最大补偿解，那么： ( 2 ) 单调补偿问题当且仅当t 0 时有解，而( 工，f ，s + r ) 即为单调补偿问 题的一个补偿解； ( 3 ) 单调补偿问题当且仅当k + 0 时不可行。 第一条是关于同伦单调补偿问题可行性及解的存在性的结论，它指出同伦单 调补偿问题一定是可行的，而且可行点就是它的补偿解，也就是说，求解同伦单 调补偿问题已经无须再面对类似求解单调补偿问题那样的困难：既不能确定问题 是否可行，也无法确定一个初始的可行内点来启动算法。 第二和第三两条结论有一个共同的前提，就是必须是同伦单调补偿问题的最 大补偿解的情况下，这两条结论才成立。之所以要求是同伦单调补偿问题的最大 第二章同伦逡点冀法 补偿解怒因为只有在这种情况下，嗣伦参数豹组合才能反欧出撩统的可行性信息， 这从两条结论中关于同伦参数的表述里就可以看出。这两条结论给出了同伦单调 补偿问题与单调补偿问题之间解的关系，是实现从同伦单调补偿问题向单调补偿 闯题过渡的关键。这两条络谂分别给出了可行与不可行条件下网伦参数的表现， 为缮裂攀谖羚偿淹鬈懿簿缓及薅绘塞不可行签意撵貘了撵导蛙舔裂。 下颟是弓 述文献 1 2 中的相关证明。 结论( 1 ) 的证明： 令并；( 1 2 ) e ，一= ( 1 2 ) ，s = ( 1 2 ) e ，k = ( 1 2 ) ，这是一个有界的数列形 式，当t 叶o o 时，s 一f ，渖，) = ( 1 2 ) 和- f ( e ) ) _ 口， 嗣辩套k + ( ) 7 f ( x ，f f ) = ( 1 t 2 ) ( 1 + e 7 ，和) ) _ 0 帮糊伦单调章 接阖越 莩在可行煮，是可行的，同对氇说鞠同论单调补偿秘趱 的初始翮动点是很容易获得的。 设( 掌，f ，s ，k ) 0 为任意一个同伦单点补偿问题的可行点，代入( 2 - 4 ) 可得： x 葶+ f 乏= ( 善；0 2 ( 并，磅= 0 很爨然，这就是同伦单调补偿问题的个补偿解，因为目标函数被强制置零 了，只安是可行点，就是问题的一个补偿解。 结论( 2 ) 的证明： 镁竣( 善4 ，s ，k + ) 为阉豫肇诱枣 偿阉麓熬一个最大毒 偿群蕊矿 o ，那么我爨 可戳满筵下面两个等式： s + ，矿= f ( x i - c + ) 和( x 。) 7 s ( ，) 2 = 0 也就是说，( 善+ ，广，s ，矿) 怒单调补偿问题的一个解。 骰设( x ，s ) 隽蕈谲於嫠阏嚣鹃一夺毒 嫠髂，劐对予 王意f 0 , x = 五s = s ，k = o 嚣 是嗣伦单调补偿问题的补媸解，也就是说对于任意一个同伦单调补偿问题的最大 解都必须满足f 0 。 结论( 3 ) 的证明比较复杂，详细证明过程可以参阅文献 1 2 的相关内容，这里 不秀说瞬。 经过上述豹讨论，我锏已经褥单疆餐簇翊蘧静求解转纯兔对鞫稔单调羚嫠瀚 题最大补偿解的求解，下黼我们先讨论一下谯最大补偿解的条件下，同伦参数的 组合情况。 9 华南壤上天学硕士学佼论文 2 2 3 同伦参数的讨论 有了上面的三个结论和同伦参数的引入，不仅使得问题得以从己知优化解的 问题向未知问题过渡，同时结论( 2 ) 和( 3 ) 也为探测问题是否出现不可行情况提供 了方法和依据。上蘑提烈了两点关予闻伦参数驰结论，即在网伦单调 b 镁闯题存 在蕞大脊偿解的条 争下，分嗣给出了f ，女在不可芎亍帮有艇情况下静数俊寝现，结 合这两点结论可以得到下列四个组合，如表2 - 1 所示： 表2 一l 同伦参数的缀合 t a b 2 - lt h ec o m b i n a t i o no fh o 繁o g e n e o u sp a r a m e t e r s = o 0 = o 存在任何可能 不可幸亍 彝 霹籁窆集 可以看到，当f ，都为零的时候，既不能确定问题有解，也不能证明问题不 可行，而这种情况在问题为单调仿射函数时是不可能发生的；f ，七都大于零这个 组台，实舔在最大静臻条释下是不存在戆，这檄据最大 偿瓣翡撅念不难涯赘。 也就是说实际上在问题的优化过程中，需要关涟的是剩下的两个f ，女的组合，即 有解和不可行两种状态。我们只需分别就这两种状态设定t k 的收敛判据即可达 到快速捡溅不可行精况憨嚣豹。 2 3 原对偶同伦单调补偿问题 对予谯化润踅，饕线性等式约柬是缀经常爨现静，下溪我们给窭繁菲线往等 式约束的单调补偿问题的形式： m i n工7 s( 2 - 1 2 ) &。，：=，e，善，#fg纛(歹y,茹x)1jy ，e 膏，s ，0 e z t s ， & ，| l = 尹f ，善) ：= | 。| ，( 膏，s ) z 1 3 j l s 一 一。+ 这单。氘y 的维数分别为i n 和n ；s r “，是以松弛变量为分量的向量；f ( y ，工) 是连续单调映射r “戤_ 足“4 ；矗为映射r ”“- 4 r ”，霉为映射尺”“- 科。 这样，对于任意( ，) ，( ，2 ，善3 ) r “霹，我们有“： ( ( y ；工) 一( y 2 ；j 2 ) ) 7 ( ，( y 1 ，石) 一f ( y 2 ，搿2 ) ) ( 2 - 1 4 、 = ( y 1 一y 2 ) r ( i i | ( y 1 ，茗4 ) 一h ( y 2 , 茗2 ) ) + 善一x 2 ) r ( g y 1 ，毒) 一g ( y 2 , ) ) o 类似的，带等式约束的单调补偿问题当飘仅当存在这样一个有界数列 第二章网论内点算法 ( ，) r ”斌x r ：，t = 1 2 使得1 i m ( 0 ；s ) 一，( 几) _ o 时才魁可行的，对于可 tr一 嚣困点一样要求该可行点( 只善，s ) er “酸砭，当存在可厅点( 劳茗，s ) 满是茹s = 0 叭 ! = l 嬲r h ( y 。二c , 篡x r ) 伪卜e ， 蜘渤屯r f ( ，y 加r , x r ) 伪 ：l m 州嬲2 h ( y l z 2 , 嚣x t r ) 仡价) 翊 v w ( y ，x ，s ) * v f ( y i t )，( y c , x ，f ) 一v f ( 芦f r , x ，彩垒生 一，( y 忆并r ) 7 一盟x t v ，( ) ，l 工，力( ) i ，t x ，丁) 7 v ，( y 忆z f ) 业盟 fi 气t 同样的，同伦单调补偿问题的相关结论在这里一样适用。 2 ，3 霹趁摸型戆审心路经 从上面的缡论我们可以潜到，对单调补偿问题的求解可以通过寻找同伦单调 补偿阉题的最大补偿孵来完成。下面本文将介绍同伦路径的闽题。 首先选定一缌x 。 d ，s 。 敬1 o o 竞8 o ，同霹重令余差向量，o ；s 。一矿， 。，矿) ， z o = o + ( 工。) r f ( x o ，矿) ，再令；= ( ，o ) 7 王。十o f 。 为了篱单藤凳，我稍设善9 = g ，s 8 = 8 ，护= 1 ，k 。= l ，遮样就有x 。s 8 = g ，r 。k 。= 1 ， 这凰x o 是关于并。的对角矩陴。假设工o ，f o 为1 1 维响量，那么n = n 十1 。 犊羞我褒余缓凌下结论“”2 ”3 ：藏鬻稔荤诿蛰缮翊蘧瑟言 华南理】= 大学硕士学钕论文 ( 1 ) 对于任意0 0 1 ，存在一个严格的j 下的点，即x 0 ，s 口，f o ，k 0 ，满足： ( 扣琊，= ( 舂嚣捌= 旧 鲻 ( 2 ) 从点= 口，s o = 口，矿；l ，k o = 1 出发，对于任意0 0 1 ，存在一个唯一的严格的 j 下的点( x ( 护) ，5 ( 口) ，f ( 印，( 目) ) ，使得其满足( 2 - 1 9 ) 式的同时，也满足； i 淞江o e( 2 2 0 ) l 性 ( 3 ) 对于任意的。茎0 蔓1 ，结论( 2 ) 中所得的解( x ( 日) ，j ( 口) ，f ( 护) ，k ( o ) ) 是有界的，因 监( 2 - 2 1 ) 式嚣表示瓣映射爻迄续毒爨蛉辕绫。 c c 国：= c x ，s ，t k ，：( ：) - q t ( x , r ) = o l r 。l z o ，f x s l = 踟，。 0 ，可疆簿翻； i t w ( x 1 - o ( 2 - 2 2 ) x t v w ( x ) = 一妒( z ) ( 2 - 2 3 ) ( 2 - 2 2 ) 移( 2 - 2 3 ) 式掇豢冁稔摹调李 髅翊蘧夔捻瀵厥瑾霹班羹援雍篷，遮爨不箨 歪 明。对手逡代过程，假设选取其中的任意第k 次迭代，并且此时的逡代变量 ( 童。，$ 。) 0 ，则算法给出的修正方向为： 一v 妒( 浑弦，= 一蹿r 。 ( 2 2 4 ) 盖+ s = 搿2 e - x 2 s 2 ( 2 - 2 5 ) 其中和矿：垦善，仉，为在。到l 之间给出的变量。 n 十l 缳显然，逮蓑是牛顿攘素方逡，楚对( 2 一1 9 ) 移( 2 2 0 ) 式豹一狳泰勤鬏开式。 下面将引遮几个结论及冀证明“”以说明整个迭代过程豹要求，结论有： ( 1 ) 搜綮方向w 。，d 。) 满足：d ：d 。= d j v 缈q m 。+ r ( 1 - r - ( n + 1 ) ( 2 2 6 ) 证明；在式( 2 2 4 ) 两端同乘以可得 d t d , 一d ：v 妖善矽；= 一私：2 - v ( x 2 ) ) ( 2 2 7 ) 再在式( 2 - 2 4 ) 两端同乘以x 。，并将( 2 - 2 2 ) 、( 2 - 2 3 ) 代入，可得 第二章同伦内点算法 ( 工。) 1 d 。+ 矿( 工。) d ；= 一r ( x ) 7 r 。 = 一r ( x k ) ( s k - - 妒( 善。) ) ( 2 - 2 8 ) = 一r ( x 。1 s = 一r ( n + 1 ) 。 联立( 2 2 7 ) 、( 2 2 8 ) 、( 2 2 5 ) 可得 d r d 。= d ! v y ( x 。) d 。一叩( d ! s 。+ d j x 。+ r ( n + 1 ) 。) = d j v y ( x 。) d 。一r ( 一( n + 1 ) t 。+ h n + 1 ) z 。+ r ( n + 1 ) 1 。) ( 2 2 9 ) = d ：v 妒( x 。) d 。+ 7 ( 1 一y - 玎) ( n + 1 ) g 。 命题得证。 这样，每一步新的迭代，对于步长盯 0 有： x + ：= x 。+ 喇； 0 ( 2 3 0 ) s + ：= s 。+ 谢。+ y ( x + ) 一y ( x 。) 一a v w ( x 。) d ； 2 妒( x + ) + ( 8 。一y ( 1 2 ) ) + 口 s v 妒( 工。x ) ( 2 3 1 ) = w ( x + ) + ( s 一y ( x 。) ) 一a r l ( s 。一咿( x 。) ) = 妒( + ) + ( 1 一a r l ) r 。 ，+ = s + 一咿 + ) ( 2 - 3 2 ) ( 2 ) 设( 工+ ，s + ) 为由是( 2 3 0 ) 、( 2 3 1 ) 给出的新的迭代变量，那么有： ，+ = ( 1 一a r l ) r 。( 2 - 3 3 ) ( 茹+ ) 7 s + = ( z 。) s 。( 1 一a ( 1 一”) + 口2 珂( 1 一玎一力( n + 1 ) z 。 ( 2 3 4 ) 证明：由( 2 3 1 ) 式可以直接证明( 2 3 3 ) ，即 ，+ = f + 一缈( 善+ ) = ( 1 一a r l ) r 。( 2 - 3 5 ) 根据( 2 - 2 2 ) 、( 2 - 2 3 ) 和( 2 2 5 ) ，以及结论( 1 ) ，我们可以得到： ( 卫+ ) 7 s + = ( j + ) 1 0 。+ 嘲；+ 妒( z + ) 一妒( j 。) 一c 刀咿( x 。) d 。) = ( 工+ ) 7 0 。+ 删。) - ( x + ) 7 ( y ( 工。) + c 刃缈( 毒矽。) = ( j + ) 7 0 。+ 蒯。) 一( 工。+ 积。) 1 ( 缈( 善。) + 6 y ( j 。) d 、) = ( j + ) 7 0 。+ 谢。) 一口( 置。) 7 v u ( x 。) d 。一o f f 凡, ( x 。) 一盯2 d x r v 妒( x 。) d 。 = ( 工+ ) 7 0 。+ 谢。) 一瞳2 d ：v 1 f ，( j 。) d 。 ( 2 3 6 ) = ( 耳。+ o f f 。) 7 扣。+ 删。) 一盯2 d t v 缈( x 2 ) d 。 = ( 膏。) 7 覃。+ o t ( d ；r s 。+ d j 工。) 十c r 2 ( d ：d 。- d ( x 。) d 。) = ( 工。) 7 s 。+ 口( d ：s 。+ d j x 。) + 口2 7 ( 1 - 7 一”( n + 1 ) g 。 = ( 1 - c # ( 1 一力) ( 工。) s 。+ 口2 玎( 1 一叩一”( n + 1 ) l 。 由此，命题得证。 ( 3 ) 该结论较为复杂，简单来说就是在满足一定的条件的前提下，每次新的迭 代变量都满足x + 0 s + 0 。结论中所说的前提条件及该结论的证明可以参阅文献 1 2 中相关内容。 华南理工大学硕士学位论文 透过上匿螅这些结论，我们霹以大钵了解围俭内患法，麓嚣