（电力系统及其自动化专业论文）一种求解最优潮流的过滤器—信赖域内点方法.pdf

af 1 1 月e r t r u s tr e g i o ni n t e r i o rp o i n t m e t h o df o ro p t i m a lp o w e rf l o w a b s t r a c t o p t i m a lp o w e rf l o w ( o p f ) i sa ni n d i s p e n s a b l en e t w o r ka n a l y s i s a n do p t i m i z a t i o nt o o lf o re l e c t r i cp o w e rs y s t e m so p e r a t i o n i t sv i t a lt o t h es y s t e m se c o n o m y ，s a f e t ya n dp o w e rq u a l i t y t h e r ea r es e v e r a lw a y s t os o l v eo p f ，s u c ha sn o n l i n e a rp r o g r a m m i n g ，q u a d r a t i cp r o g r a m m i n g ， l i n e a rp r o g r a m m i n g ，a n di n t e r i o rp o i n tm e t h o da n ds oo n m o d e mi n t e r i o rp o i n tm e t h o di so n eo fi m p o r t a n ta l g o r i t h m sf o rt h e o p f ，w h i c hh a ss o m ea d v a n t a g e sl i k eg o o dc o n v e r g e n c ea n dp o l y n o m i a l t i m ec o m p l e x i t y i ti se x t r e m e l yb ea no u t s t a n d i n ga l g o r i t h m b u tw h e n t os o l v en o n - c o n v e xo p t i m i z a t i o no rw h e nt h er e s t r i c t i o n so fo p f b e y o n d t h eb o u n d ，t h ec o n v e r g e n c eo fi n t e r i o r p o i n t m e t h o di s c h a l l e n g e d s ol o o k i n gf o rw a y st os o l v el a r g e s c a l eo p f i nq u i c k l ya n d e f f e c t i v e l yh a sb e c o m ea h o tr e s e a r c h i nr e c e n ty e a r s ，t h e r ei san e ww a yc a l l e df i l t e rm e t h o dc a ns o l v e a b o v ep r o b l e m s w o r l d f a m o u sm a t h e m a t i c i a nr f l e t c h e ri n t r o d u c e d t h ec o n c e p to fd o m i n a t ea n dt h ei d e o l o g i c a la b o u tf i l t r a t eo ft h ef i l t e r s i n c et h e n ，c o m b i n i n gt h ef i l t e rm e t h o da n do t h e rm e t h o d st os o l v e n o n l i n e a rp r o g r a m m i n gp r o b l e m sh a sb e c o m ean e wh o t s p o t t h i sp a p e rp r e s e n t saf i l t e r - t r u s tr e g i o ni n t e r i o rp o i n ta l g o r i t h m ， s o l v i n gt h ep r o b l e mt h a ti n t e r i o rp o i n tm e t h o dc a n tc o n v e r g e n c ew h e n r e s t r i c t i o n sb e y o n dt h eb o u n di no p f i nt h i sa l g o r i t h m ，t h es q ps u b m o d e li ss o l v e db yt h em o d e mi n t e r i o rp o i n tm e t h o d ，a n dt h et r y i n gs t e p i sc o n t r o l l e db yt h et r u s tr e g i o n ，w h e t h e rt oa c c e p ti to rn o ti sd e c i d e db y t h ef i l t e r n u m e r i c a lt e s t so nf i v es t a n d a r di e e es y s t e m sa r ev e r y e n c o u r a g i n g c o m p a r ew i t ht h ep r i m a l d u a li n t e r i o rp o i n tm e t h o d ，t h i s n e wa l g o r i t h mc o n v e r g e n c ew h e ns o m er e s t r i c t i o nb e y o n dt h eb o u n d t h i sr e s u l ti ss u i t a b l et op r a c t i c a la p p l i c a t i o n s k e yw o r d s ：f i l t e r ；t r u s t - r e g i o nm e t h o d ；i n t e r i o rp o i n tm e t h o d ；s q p ；o p f - i i i 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的 成果和相关知识产权属广西大学所有。除己注明部分外，论文中不包含其他人 已经发表过的研究成果，也不包含本人为获得其它学位而使用过的内容。对本 文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名： 幸笔盘 m 3 年6 月坫日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 函口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：辛兰杰、 导师签名瑚年占月谚同 广西大学硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方法 第一章绪论 1 1 课题的意义 随着世界电力系统规模的不断扩大和电力市场改革的不断深入，如何保证 电力系统安全、稳定、优质运行成为电力工业急需解决的重要课题。从社会发 展的角度出发，电力工业是国民经济的命脉，国家工业的发展和人民生活水平 的提高要求不断提电能质量；从经济角度出发，降低燃料消耗、减少生产及输 送过程中的电能损耗，从而提高电力系统的经济运行，也一直是电力工业研究 的热门话题。最优潮流( o p t i m a lp o w e rf l o w , o p f ) 问题就是基于以上要求， 综合体现了电力系统运行的经济性、安全性和电能质量，是电力系统运行、分 析、控制和规划的不可或缺的网络分析和优化工具。 建立在严格数学基础上的o p f 提出之后，广大学者对其求解方法、收敛性、 计算速度和内存需求量等方面进行了深入研究，取得了很多成果。至今求解o p f 的方法很多，如非线性规划法、二次规划法、线性规划法及近年出现的内点算 法【】等。在众多研究成果中，现代内点法具有收敛性好、多项式时间复杂性等 优点，是极具潜力的优秀算法之一。但理论上，内点法【4 j 求解非凸优化问题时 的收敛性受到质疑，且当约束条件变得更为严格时，可能导致不收敛。其中线 性化选取步长和尽大步修正步长是影响收敛性的主要原因。因此寻找能够快速 有效地求解大规模o p f 问题的方法，已成为研究的一个热点。 近年来，过滤器( f i l t e r ) 法的提出和信赖域法( t r u s tr e g i o nm e t h o d ，t r ) 的发展为解决以上问题提供了新的途径。 信赖域方法与传统的线性搜索方法不同，它在每次迭代时都要重新生成子 模型，在当前点的信赖域范围内寻找试探点，然后用某种标准判断是否接受此 点。接受的标准一般采用由目标和约束构成的罚函数，但是如何选取合适的罚 因子是困扰此法的一个难题。故本文不通过信赖域方法判断试探步是否可接受， 而是采用过滤器法。 过滤器法是非线性规划领域的研究热点，由世界著名的数学家r f l e t c h e r 提出，他定义了优于( d o m i n a t e ) 的概念并给出了滤点的思想，是一个可以促 进全局收敛的优秀算法。 广西大掌硬士学位铡誓 一种求解最优潮流的过滤器一信赖域内点方法 本文结合过滤器法和信赖域方法的思想，用现代内点法求解最优潮流。这 一方面已有相关研究，例如，文献 7 首次引入过滤器一信赖域方法，文献【8 】 结合过滤器法和内点法，为有效求解大规模o p f 问题做了很好的尝试。本文在 文献【7 】的基础上改进。文献【7 】采用线性规划( l i n e a rp r o g r a m m i n g ，l p ) 子模型， 本文采用较精确的( s e q u e n t i a lq u a d r a t i cp r o g r a m ，s q p ) 子模型，即将o p f 模 型转化为具有二阶收敛性的s q p 子模型，通过现代内点法求解之得到试探步后， 用过滤器法作为其是否能被接受的标准，而如何调整步长取决于信赖域法。本算 法不仅简单、易于理解，而且是促进全局收敛的一个有效策略。 用过滤器一信赖域法求解o p f 是一个全新的课题，处于电力系统计算研究 的前沿。与传统求解o p f 的算法相比，它能够解决当约束条件越界时算法失效 的问题，具有良好的收敛特性，因此拥有良好的应用前景。 1 2 课题的提出及研究现状 1 2 1 最优潮流问题 o p f 问题未被提出之前，提高系统运行的经济性是人们研究潮流问题的主 要目的。基于协调方程式的经济调度方法就是提高经济性的手段之一，它形成 于上世纪3 0 年代，其核心是等微增率法则，此法则只考虑发电机有功功率的越 限约束，由于不考虑其他约束条件，因此脱离了实际系统运行的要求。随着电 力系统规模的不断扩大和电力市场改革的不断深入，对系统运行安全性和电能 质量的要求也日益提高。如何将系统运行的经济性、安全性和电能质量等要求 加以协调统一，从而决定全系统的运行方式，成为电力系统最优运行问题的重 要内容。 o p f 问题是一个复杂的非线性规划问题，由法国学者c a r p e n t i e r 于2 0 世纪 6 0 年代初提出。它要求在满足电力系统运行和安全约束条件下，通过调节系统 中可控制设备达到预定目标最优。o p f 是电力系统运行、分析、控制和规划的 不可或缺的网络分析和优化工具，关系到系统运行的经济性、安全性及电能质 量。 同经典的调度法相比，o p f 具有全面规划、统筹考虑等优点。在大系统互 连、电网规模扩大等安全经济运行变得同趋尖锐、复杂的情况下，它首次将电 力系统对于经济性、安全性及电能质量的要求完美的统一起来，满足了系统规 2 广西大掌硕士学位嵌誓走 一种求解最优潮流的过滤器一信赖域内点方法 划设计人员、运行调度人员的要求。 o p f 是电力系统经济调度和潮流计算的完美结合，它以潮流方程为基础进 行系统安全与经济的全面优化，是一个大规模、复杂的多约束非线性规划问题。 目前，人们利用o p f 能将电力系统的可靠性和电能质量量化成相应的经济指标 的优点，对现有资源实现了优化利用，降低了发电、输电成本，对提高用户的 服务质量有重大的技术经济意义。 从电力系统的构成情况来看，o p f 问题主要包括以下6 种： 1 纯火电系统的o p f ：此类型是传统o p f 研究最多的。其中，发电费用、 废气排放等因素都是针对火电厂的一些研究； 2 纯水电系统的o p f ：水力发电具有清洁干净、不污染环境、充分利用自 然资源等优点，而且缓解了我国能源缺乏的短期危机。但我国水利资源分布不 均、而且有的梯级水电厂受水库来水量的约束，是个动态的非线性优化问题， 处理相当麻烦，故有了以下的o p f 类型； 3 水火电系统o p f 9 - 1 0 1 ； 4 交直流混合输电系统的o p f ； 5 互联系统的o p f ：现代的电力系统将各小系统互联成较大的系统是为了 提高稳定性、运行的灵活性和保证供电的可靠性。电力市场环境下的互联系统 的电能传输和交易都是在一定的协议下进行，因此，一般采用并行计算技术计 算； 6 含有同一潮流控制器【1 1 啦】( u n i f i e dp o w e rf l o wc o n t r o l l e r ，u p f c ) 的o p f - 此类o p f 集并联、串联补偿和移相功能于一体，能同时控制母线电压和线路潮流； 但也使得潮流控制变量变得更复杂，对约束条件的处理也更为繁琐，需要经过 特殊处理后才能用现有的o p f 模型来计算。 随着电力工业解除管制，原先组织化垂直整合的电力公司变成相互独立和 受市场规则驱动的经济实体，电力系统运行优化工具一o p f 的地位发生了显著变 化。由于受到电力市场竞争机制等因素的影响，只考虑某一时段的稳态运行情 况的传统o p f 已不能满足稳定性要求，因为实际电力系统是个动态变化的系统， 如发电机组出力爬升率、火电厂燃料贮存量、水电厂水库贮水量、某一时段电 力市场上电量的交易量和电量电价等都是动态变化的。为了适应电力系统安全 运行的需要，o p f 增加了一些新的约束条件，如动态约刺1 3 】等。而对于暂态稳定 约束【1 4 】，传统o p f 只考虑了系统的静态安全约束，在电力市场竞争机制下，考虑 广西大掌司n b 学位论文 一种求解最优潮流的过；良器一信赖域内点方法 系统安全性，特别是考虑系统暂态安全性与经济性的统一，也是当今各国电力 学者广泛关注的焦点。 由于最优潮流是一个非常复杂的非线性规划问题，其实用化研究尚未得到 公认的满意成果，故根据最优潮流问题的特点结合其它方法，并且充分利用现代 计算机技术是解决最优潮流问题的潜在研究方向。9 0 年代以来，一些人工智能 方法如模拟进化规划方法、模糊集理论、模拟退火算法等先后应用于求解电力 系统o p f 问题。其中，模拟进化规划方法是模仿生物进化过程得到的一类优化 方法，擅长处理离散变量，具有并行处理性、全局收敛性、鲁棒性及通用性， 它包括进化规划和遗传算法；模糊集理论可用于解决具有可伸缩约束的多目标 优化问题；模拟退火算法原理简单，它通过模拟金属退火的过程来寻优，可得 到算法的全局最优解。人工智能方法解决了寻找全局最优解的问题，能精确处 理问题中离散变量，为有效求解o p f 提供了新的途径。 虽然以上介绍的方法在o p f 领域一度产生过辉煌的成果，但由于o p f 问 题存在一些特殊性，如多目标、多变量、多约束、高度非线性和非凸性等，加 上现有各种优化算法自身的缺点和局限性，如内点法不能准确处理离散变量问 题，对于非凸的非线性规划问题不具有全局收敛性；人工智能方法均属于随机 搜索方法，其先天缺陷是计算速度慢，难以适应在线计算及电力市场的要求等； 且电力系统不断发展，电力市场化以及对电力系统运行及电能质量要求的提高 等原因，导致现有的优化算法无法圆满解决电力系统o p f 安全，经济及电能高 质量的完美协调，无法兼顾最优问题的特殊性和电力系统的发展要求，目前还不 能从根本上克服自身的局限性，所以，如何提高o p f 问题求解的速度和可靠性 还有待于进一步的研究和探索。 1 2 2 信赖域法 信赖域法是一类重要的方法，它一直是非线性优化领域的研究热点。目前， 信赖域方法已经和传统的线性搜索方法并列为非线性规划领域的两类主要数值 方法【1 5 】。 信赖域法最早可追溯到l e v e n b e r g m a r q u a r d t 方法，它对一类非线性最小二 乘问题所设计的每一次迭代，实际上就是求解一个信赖域子问题，只是当时没 有明确提出修正信赖域半径的具体方案。 1 9 7 0 年，p o w e l l 1 6 】提出了真正意义的信赖域算法，他明确给出了信赖域子 4 一种求解最优潮流的过滤器一信赖域内点方法 问题、接受方向准则、校正信赖域半径准则和收敛性定理。1 9 7 5 年，p o w e l l 给 出了第一个信赖域的收敛性证明。1 9 8 4 年，p o w e l l 1 7 j 证明了信赖域方法的全局 收敛性。1 9 8 7 年b y r d 等基于二阶校正步，保证了约束优化信赖域算法的超线 性收敛性。 无约束最优化信赖域算法由于其性能可靠，引起了很多学者的注意。1 9 8 2 年s o r e n s e n 研究了结合n e w t o n 算法的信赖域算法。1 9 8 4 年p o w e l l 将他1 9 7 5 年 的工作做了很大的改进。1 9 8 9 年c a r t e r 给出了一个不用精确梯度的信赖域方法。 约束最优化信赖域方法的子问题可分为逐线性规划子问题( s e q u e n t i a l l i n e a rp r o g r a m m i n g ，s l p ) 及逐二次规划子问题( s q p ) 两种。s l p 信赖域法收 敛速度快，且不用生成海森矩阵，但精度不及s q p 信赖域法。1 9 8 5 年，z h a n gj 和l a s d o n 1 8 】等人给出了第一个s l p 算法的收敛性证明，从理论上肯定了此算法， 但他们求解子问题的信赖域范围是矩形的。在其信赖域半径选择规则下，z h a n 8 证明了算法中罚参数的选取影响子问题的精度和效率。1 9 9 1 年，p o w e l l 和y u a n l l 以增广的l a g r a n g e 函数作为价值函数，证明了s q p 信赖域法的超线性收敛性， 促进了信赖域法的发展。 内点法求解非凸的非线性规划问题不具有全局收敛性，而信赖域方法是可 以保证问题全局收敛的策略，因此结合信赖域方法和其他技术后有机地融入到 内点法中提高算法的收敛性，也是当前内点方法新的发展方向。近年来，关于 这方面的研究得到很大发展。 1 9 9 8 年，f o r s g r e n 和g i l l 2 0 】基于求解某种增广惩罚一障碍函数的无约束优 化问题，引入一种原始一对偶内点方法，通过线性搜索方法确保算法在求解非 凸问题时具有全局收敛性。 1 9 9 9 年，g e r t z t 2 1 】基于信赖域、线性搜索混合的方法，提出一种求解非约束 优化问题的新方法，该法可以处理非凸性的问题且保证算法的全局收敛性。 2 0 0 4 年，g e r t z 等【2 2 】提出一种求解非凸的非线性规划问题的原始一对偶信 赖域方法，该法在求解子问题时融合了信赖域和线性搜索技术的二阶牛顿型法， 保证原始一对偶内点方法的全局收敛性，且在c o p s 系统上测试表明该方法可 推广应用于大型优化问题的求解。但该法的算法非常复杂，并且涉及复杂数学 软件包使用和理解等问题，使得其实用价值和通用性受到质疑。 和线搜索方法相比，信赖域方法还不够成熟。有效的信赖域方法实用软件， 特别是对于求解约束优化问题的软件，依然十分缺少。所以，目前在实践应用 广西大学硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方秘 中信赖域方法还没有线搜索方法那样广泛o 但是，信赖域方法具有两个很好的 性质，一是它有很好的可靠性和鲁棒性；另一方面是它有很强的收敛性。毫无 疑问，信赖域方法将受到更大的重视，应用将更广泛。 1 2 3 过滤器法 对于目标和约束均为光滑的非线性规划问题，当初始点远离最优点时，用 基于牛顿迭代的算法求解不一定收敛。解决此问题一般的方法是采用罚函数法， 即将目标函数和约束违反度线性结合为一个目标后求极值。假设目标函数和约 束分别为f ( x ) 和c ( x ) ，令h ( x ) 纠ic ( x ) 一i i ，其中| lc ( x ) 一惴im i n ( c ( x ) ，0 ) | | o 则罚函 数可表示为p ( x ；万) _ 厂( x ) + 砌( 石) ，其中万 0 为罚参数。对于罚函数法，如何 寻求合适的罚参数是一直困扰它的难题，若7 的值大，迭代的下降量亦大，但 可能造成问题越病态；若刀的值小，又会造成收敛速度慢1 2 引。 1 9 9 6 年，世界著名的数学家r f l e t c h e r 2 4 】提出了过滤器( f i l t e r ) 法，明确 给出了过滤器的概念和滤点的思想，避免了寻求罚参数的难题，为有效求解非 线性规划问题提供了新的途径。 过滤器法算法新颖，是非线性规划领域的优秀算法。在初始点远离最优点 的情况下，它依然可以保证算法全局收敛2 5 。0 1 。因此，过滤器法成为一个研究 的热点，其应用也日益广泛。 1 9 9 8 年，r f l e t c h e r 证明了s l p 过滤器法具有全局收敛性【3 ，为过滤器法 的广泛应用奠定了基础。 2 0 0 0 年，1 lf l e t c h e r 证明了s q p 一过滤器法具有全局收敛性【2 5 j 。 2 0 0 2 年，f l e t c h e r 等证明了s o p 一信赖域一过滤器法具有全局收敛性1 3 2 。， 为结合过滤器法和信赖域方法求解优化问题提供了理论依据。 2 0 0 4 年，u l b r i c h 证明了s q p 一过滤器法具有超线性收敛性【3 3 1 。 同年，u l b r i c h 等结合过滤器及内点法求非线性规划，并证明了其全局收敛 性【2 8 】。 2 0 0 3 年，刘盛松、侯志俭等【7 1 在国内最先引入过滤器法求解电力系统最优 潮流问题，为有效求解o p f 做了很好的尝试。 2 0 0 7 年，孙英云掣列结合过滤器法和内点法求解o p f 。 过滤器法原理简单、算法新颖、易于理解且具有全局收敛性，结合过滤器 法与其它优化算法求解非线性规划问题具有重要的研究意义。本课题引入过滤 6 广西大掌司n b 掌位论文 一种求解最优潮流的过滤器一信赖域内点方法 器法作为判断试探步是否可接受的标准，避免了单独使用信赖域方法求解时选 取罚参数的难题。 1 3 本文的研究内容 经广大学者多年的研究，已提出一些能快速求解大规模o p f 的方法，如具 有收敛性强、多项式时间复杂性的现代内点法就是其中之一。但是当o p f 的约 束条件变得更为严格时，现代内点法【4 】可能不收敛。本文研究的任务是寻求一 种能快速、有效求解此问题的策略。 过滤器法和信赖域方法由于能促进算法的全局收敛而备受关注。本文结合 二者，用现代内点法求解o p f 。其中，先将o p f 模型转换成s q p 子模型，通 过现代内点法求解得到试探步，用过滤器作为判断此试探步是否可接受的标准， 再采用信赖域方法决定步长。本文选取五个i e e e 系统，压缩约束条件的两界 使得问题出现越界点，分别用本文的算法和原始对偶内点法进行测试，比较其 收敛性。 1 4 本文组织结构 本课题是运用过滤器一信赖域内点方法求解电力系统最优潮流问题的一次 成功的尝试。论文第一章首先介绍本课题的研究意义和o p f 问题、信赖域方法、 过滤器法的提出及研究现状；第二章和第三章分别介绍了信赖域方法和过滤器 法的概念、基本原理、算法过程及目前在电力系统中的一些应用；第四章介绍 了o p f 问题的技术经济意义、目前仍存在的问题和今后的发展趋势，并介绍其 模型及目前求解之的一些有效方法；第五章对现代内点法进行简要介绍，给出 其分类、原理、公式推导、算法流程和在电力系统优化领域的应用等。第六章 介绍本文所提出的过滤器一信赖域内点方法的具体模型和算法过程，并用它求 解o p f 问题，同时给出仿真的结果；最后在第七章对全文进行概括性的总结， 指出存在的不足，并对未来的研究和发展进行探讨和展望。 7 广西大学硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方法? 第二章信赖域法 2 1 引言 信赖域方法与线性搜索方法是当前非线性规划领域的两类主要数值方法。 传统的线性搜索方法在求解过程中，可能会因问题本身的病态使得搜索方向是 非常大的向量，或在目标函数非线性很强的情况下找不到数值上更好的点，或数 值误差使得理论上应为下降方向的搜索方向变为上升方向，这些问题都可能会 导致线性搜索失败。 信赖域方法是为了克服线性搜索方法可能出现的困难而提出的一类新的计 算方法。以下分别介绍二者的算法原理。 2 2 线性搜索与域搜索的比较 2 2 1 线性搜索的原理 0 x 7 x ( t ) 厂 l “。 | 。 v0v 7 图2 - 1 线性搜索过程 f i g 2 - lp r o c e s so fl i n e a rs e a r c h 用线性搜索技术求解非线性规划的主要思想：在当前迭代点处生成一个搜 索方向，沿此方向做一维搜索，从而得到下一个迭代点。如图2 1 所示：从当 前点x 出发，寻找下降方向后选择一个合适的步长缸，得到下一个迭代点 8 一种求解最优潮流的过滤器一信赖域内点方法 x “1 ，如此循环迭代，直到找到最优点。 对某一函数( 称之为效益函数) ，若为无约束问题，效益函数是目标函数本 身。而对于约束问题，效益函数往往取准确罚函数或增广拉格朗日函数，但无 论效益函数如何选取，一般总能保证搜索方向是效益函数的下降方向。 线性搜索方法的一个关键问题是步长的修正方法( 步长规则) 。步长规则的 形式有很多种，包括精确的一维步长( w o l f e 步长规则、h r m i j o 规则及变形、 g o l d s t e i n 步长规则等) ，单调的步长规则和非单调的步长规则等。 线性搜索方法是求解非线性规划较成熟的一种方法，但在解域窄或问题病 态的情况下很难收敛。此时，域搜索发挥着重要的作用。 2 2 2 域搜索的原理 图2 - 2 域搜索过程 f i g 2 2p r o c e s so f r e g i o ns e a r c h 域搜索的基本思想与线性搜索不同，它改变了传统线性搜索的搜索模式。 域搜索在每次迭代时，都在当前点处建立原问题的近似子模型，求解之并在一 定范围内寻求下一个迭代点。以图2 2 为例介绍信赖域法：首先给出信赖域的 范围( 以当前点x 为圆心，信赖域半径p 为半径的广义球域即为信赖域) ，在x 处建立一个近似子模型，并认为它只在信赖域范围内可信；然后在此域内寻找 最优下降方向得到试探步长，强制控制步长在信赖域范围内，即l i ( 血) 临p ； 最后迭代得到新的迭代点x “1 ；得到的新点需通过某种标准判断其是否可接受， 判断的标准往往是由目标函数和约束条件构成的不可微精确罚函数( 评价函 9 广西大掌硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方法 数) ；若新点被接受则表示建立的子模型可以很好的反映原问题，扩大信赖域半 径，反之减小信赖域半径。 域搜索可以解决线性搜索的一些弊端，但由于求解步骤增多、搜索范围增 大，故对于同一个问题，域搜索的求解速度比线性搜索慢。 2 3 信赖域法的基本思想 信赖域方法要求在每次迭代时重新建立当前点处的子模型，并强制性地要 求新迭代点与当前迭代点之问的距离不超过某一控制量( 信赖域半径) ，引入控 制步长的目的是为了解决传统的线搜索方法常常由于步长过大而导致算法失效 的问题，特别在问题病态时尤其如此。 对于如下非线性规划： m ，i n 厂( 引 ( 2 1 ) s d c ( x ) 0 设当前点为x ，首先建立x 处的近似子模型，以s q p 子模型为例： m i n 。( x ) 4 - w ( x ) 7 1 d + k ，、d 7 h d z s ， v c ( x 。) 7 d - t - c ( x ) 0 ( 2 2 ) i i d l i p 其中，d 为试探步，日为海森矩阵，耵( x ) ，v c ( x ) 分别为f ( x ) ，c ( x 。) 的一阶 导数。步长控制0d 临p 实质等价于在以x 为中心、p 为半径的广义球域内对 一个近似于原问题的简单模型求极值。这种技巧可理解为只在这个邻域内认为 近似模型可信，所以此邻域被称为信赖域。利用这一技巧的方法也就称为信赖 域法。信赖域方法只在信赖域范围内考虑子模型，这是基于任何模型的近似函 数只在局部才与原函数很好吻合的思想，也就是说只在信赖域内相信子模型， 因此，信赖域方法有着很强的逼近背剥15 1 。 信赖域的大小在迭代过程中逐步调节，若当前近似模型能较好地逼近原问 题，则信赖域半径可扩大，否则应缩小。后来，研究学者发现信赖域方法的基 本技巧在一定意义下等价于十分著名的求解非线性最小二乘问题的 l e v e n b e r g m a r q u a d 方法【1 5 】。 信赖域方法的另一个重要思想是对牛顿型法的改进。牛顿型法的基本原理 1 0 广西大学硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方法 如下：根据二次模型产生下降方向，通过线性搜索方法在此方向上选取可接受 的步长，从而得到新的迭代点。即先求出当前点x 处二次逼近函数达到最小时 的步长d ，再根据x “1 = x + d 得到下一个点。当目标为非线性函数时，该法 要求只有海森矩阵是正定的情况下，其二次函数在点x 的邻域里对原问题的近 似才有意义。尽管牛顿型法在实践中已被证明是有效的，但若二次模型不能充 分近似于原问题，基于该模型所确定的搜索方向上常常无法找到具有满意的下 降值的可接受点。 与牛顿型法不一样，信赖域方法迭代前首先指定一个信赖域，再用带约束 的二次模型来确定位移的方向和大小，即求解子模型得到试探步，再修正变量。 可以看出信赖域方法不进行一维搜索，所以它是不执行一维搜索而使牛顿型法 具有全局收敛性的方法。许多研究学者都认为，该法是非常有效、精确的整体 收敛性的最优化方法【l 5 。 以上的分析说明，信赖域方法是由线性搜索方法和牛顿型法发展得到的一 种新算法，其突出的优点在于思想新颖、具有很强的全局收敛性和二次收敛性 1 7 1 ，且因加上强制性约束条件，使得其在求解非凸【3 4 1 甚至非光滑问题【3 5 】时表现 出很强的收敛性。 除了构造子模型和选取步长外，如何快速、有效的求解信赖域子问题也是 信赖域方法的关键。由于内点法收敛性强，为此，许多学者把内点法与信赖域 方法结合起来，构造出一类新的算法一信赖域内点法，并将其应用于实际问题 的求解。目前已有学者 3 6 - 3 9 1 用此法求解大型电力系统o p f 问题，实践证明该算 法是快速、鲁棒的，具有实用意义。 2 4 信赖域法的算法过程 2 4 1 信赖域法的算法步骤 信赖域方法在每次迭代时于当前点的信赖域范围内重新构造子模型，求解 之得到试探步，通过价值函数判断试探步是否可接受并决定如何修正步长，如 此循环直至寻到最优解。主要算法步骤如下： s t e p l ：初始化参数x ( 们，p 0 ，后= 1 等； s t e p 2 ：计算收敛判据，若算法收敛则停机输出，否则转s t e p 3 ； s t e p 3 ：求解近似子模型得到试探步，得到下一个迭代点x 似“) ； 广西大掌硕士掌位论文 一种求解最优潮流的过滤器一信赖域内点方法 s t e p 4 ：建立价值函数，判断点x ( “1 是否可接受，若可被接受，转s t e p 5 ， 否则转s t e p 6 ： s t e p 5 ：修正变量x ( “1 ) = x ( + d ( ，增大信赖域半径，转s t e p 7 ； s t e p 6 ：不修正变量x ( “1 ) = x ( ，减小信赖域半径，转s t e p 7 ； s t e p 7 ：k = k + 1 ，转s t e p 2 。 信赖域方法的算法流程比较简单，此过程中较关键的环节是近似子模型的 建立、求解和如何建立价值函数。 2 4 2 信赖域法的近似子模型 信赖域方法要求在每次迭代时于当前点处重新建立近似子模型， 制步长控制约束。一般采用线性规划子模型或二次规划子模型【9 】： 1 、线性规划子模型( l i n e a rp r o g r a m m i n g ，l p ) r a i n v f ( x ) 。d s d v c ( x ( k ) ) 7d + c ( x ) 0 d p 并加入强 ( 2 3 ) l p 子模型由( 2 1 ) 的目标和约束在当前点x ( 。处分别泰勒一次展开，并加 入步长约束所得。该子模型因无需形成海森矩阵，故算法简单、计算速度较快， 但此法不够精确。1 9 8 5 年，z h a n gj 和l a s d o n 墙1 等人给出了第一个s l p 算法的 收敛性证明，从理论上肯定了此算法。 2 、二次规划子模型( s e q u e n t i a lq u a d r a t i cp r o g r a m ，s q p ) 1 m i n 厂( x 。) + v f ( x ) 7 d + 2 - d ，h d z s j v c ( x ) 7 d + c ( x ) 0 ( 2 4 ) l i d l l p s q p 子模型由( 2 1 ) 的目标和约束在当前点z 似处分别泰勒二次和一次展 开，并加入步长约束所得。该子模型更为精确，且具有二阶收敛性，但由于要 形成海森矩阵，故计算过程较复杂。 当然，还有其他的构造方法，如文献b 5 提及用如下罚函数法构造子模型。 但由于罚参数7 似) 的取值不好把握，故此模型不常用。 1 2 一种求解最优潮流的过滤器一信赖域内点方法 m i n v f ( x ) 7 d + 三d r h d + 7 - ( k ) l l ( c ( x ) + v c ( x ) 7 d ) 一8( 2 5 ) i i d l f p 2 4 3 信赖域法的价值函数 信赖域方法的价值函数用于衡量其子模型对于原问题的近似程度，且作为 如何修正信赖域半径的标准。一般采用罚函数作为价值函数。 1 9 9 8 年，y a b e 等【3 6 1 用等式约束的，范数构造惩罚项作为价值函数。 1 9 9 9 年，b y r d 等3 7 】【3 3 】；2 0 0 2 年，w a l t z t l 5 1 等均采用某种精确，范数作为s q p 一信赖域方法的价值函数。 2 0 0 0 年，c o n n 等f 3 9 】【4 0 1 采用某种带加权，范数的对数罚函数作为价值函数。 以下以s q p 子模型为例说明本文如何构造价值函数： 对于问题( 2 1 ) ，定义如下价值函数： y l ( x ( 。) = f ( x ) + q ( i ic ( x ) 忆) ( 2 6 ) 其中，瓦为罚参数。则求得预估计的下降量为： p r e d = y l ( x ) 一( x + 1 ) ( 2 7 ) 对于s q p 子问题( 2 2 ) ，定义如下价值函数： y 2 ( x 似，d ) = 厂( x 仕) + w ( x 似) r d + 圭d 7 日似d ( 2 8 ) + f 2 ( | | v c ( x 岁) r d + c ( x 。) 忆) 为罚参数，则求得实际下降量为： a r e d = y 2 ( x n ，0 ) 一2 ( x ，d ) ( 2 9 ) 定义实际下降量与预估计的下降量的比值： r k = a r e d ( 2 ) p r e d ( ) ( 2 1 0 ) 吒用于衡量( 2 2 ) 的近似性能，且在决定如何调节信赖域半径方面起关键的 作用。显然，r k l 时表示( 2 2 ) 的近似效果好，可以增大信赖域半径；r k 0 时，说明新的点x ( “1 比当前点x ( 好，此时可以接受试探步长， 修正变量并扩大信赖域半径： i7 7 i 见，r k o 2 5 岛+ l = 7 7 2 n ，o 2 5 0 为罚参数，但是如何求得合适的罚参数是一直困扰此法的难题【2 4 1 。 1 9 9 6 年，世界著名的数学家r f l e t c h e r 提出了过滤器( f i l t e r ) 法，给出了 优于( d o m i n a t e ) 的概念和滤点的思想，避免了以上难题。 本文引入过滤器法，将其作为判断试探步是否可接受的标准，并通过信赖 域方法决定步长。 过滤器法算法新颖、易于理解，具有很大的研究价值。但由于算法提出的 时间不长，相关的文献不多，在各方面的应用仍不成熟，故需要更多学者深入 的研究，使其更为完善。 3 2 过滤器法的原理 3 - 2 1 过滤器法的概念 如上节所陈述，对于( 2 1 ) 式的非线性规划问题，罚函数法的处理办法是 通过引入罚参数，将其目标函数和约束条件结合为一个目标后求极值。与之做 法不同，本文所引入的过滤器法将二者视为两个独立的目标值求解，即认为 ( 2 1 ) 存在两个相互矛盾的目标，一是目标函数的最小化，另一个是满足等式 约束和不等式约束，即最优性和可行性的矛盾。这两个目标分别表示如下【2 4 】： m i nf ( x 1 ( 3 1 ) m i ns ( c ( x ) ) ( 3 2 ) 卅 其中：s ( c ( x ) ) 4 1c + ( x ) | 1 1 ：= c j ( x ) ，c 4 - = m a x ( 0 ，c ，) 。 下面给出优于( d o m i 揣e ) 及过滤器的概念( 2 4 】： 广西大掌硕士学位论文 一种求解最优潮流的过滤器一信赖域内点方法 定义1 当f 7 且s s ( 7 时，称点( 厂，s ) 优于( d o m i n a t e ) 点 ( n ，一) 。 这意味着点x ( 至少和点x ( 7 ) 一样好，在此基础上，定义以下过滤器的概念。 定义2 过滤器包含( 厂n ，c ，) ) 这样的点集，其中的任何一个点不优于其余 的点。 定义l 和定义2 是过滤器法的精髓，可根据二者作为判断试探步是否可接受 的标准。 3 - 2 - 2 过滤器法的滤点思想 基于以上多目标规划的优于和过滤器的概念，将滤点的思想1 2 4 j 介绍如下： 以f ( x ) 为纵坐标，j ( c ( x ) ) 为横坐标的二维空间中，令空间内的点( 厂“，s ) 表示迭代点x 处的目标和约束( 厂( x ) n ，s ( c ( x ) ) ) 。若( n ，s ) 优于过滤器中 的任意一点，则认为点( 厂似) ，s 似) 能被滤掉。过滤器每滤掉一个新点，就切割出 一块区域，其中的点均不能被接受。由此可见，多滤掉一个点，就会增加一个 不被接受的区域，即切割面积增加，可排除的点增多。图3 1 为过滤器的示例， 阴影部分为切割出的区域，其中的点均不能被接受。 厂( x ) s ( x ) 图3 - 1 过滤器示例 f i g 3 1a ne x a m p l eo f t h ef i l t e r 3 2 3 过滤器法的滤点过程 过滤器在滤点的过程中，可能会出现迭代的累积现象，即( ，s ) 空间中非 k t 点的振荡现象。为避免此现象发生，规定只有下降量足够充分的点才能被 接受。令点x ( 川) 能被过滤器接受的条件为【4 3 】：f 川f n 一识s 7 或 1 6 广西大学硕士学位论文一种求解最优潮流的过滤器一信赖j i 6 t 内点方法 s ( k + l 办s ( n ，其中办和矽2 为预设的参数，以 0 ，矽2 0 ，k = l 等； s t e p 2 ：计算收敛判据，若算法收敛则停机输出，否则转s t e p 3 ； s t e p 3 ：求解s q p 子模型得到试探步，得到下一个迭代点x ( “1 ) ； s t e p 4 ：用过滤器判断点x “是否可接受，若可被接受，转s t e p 5 ，否则转 s t e p 6 ； s t e p 5 ：修正变量x ( “1 ) = x (