（运筹学与控制论专业论文）非线性二层规划的过滤信赖域算法与乘子法.pdf

福建师范大学徐凌硕士学位论文 a b s t r a c t i nt h i sa r t i c l e ，w ed i s s c u s st h es o l v i n ga l g o r i t h m sf o rt h en o n l i n e a rb i l e v e lp r o - g r a m s t h i sp a p e rm a i n l yc o n s i s t so ft w op a r t s 、i nt h ef i r s tp a r t ，m o t i v a t e db yt h et r u s tr e g i o ns u b p r o b l e m ，w ep r e s e n taf i l t e r t r u s tr e g i o na l g o r i t h m sf o rt h en o n l i n e a rb i l e v e lp r o g r a m s w ec o n s t r u c tf i r s ta s p e c i a lq u a d r a t i cm o d e lf o rn o n l i n e a rb i l e v e lp r o g r a m m i n g s t h e nw et r yt os l o v e t h em o d e li nt h ef i l t e rt r u s tr e g i o nb a s e do nt h en o r ml l ，a n dt h es o l u t i o no ft h e m o d e lt h e ni sa c t e da st h es t a r tp o i n to ft h en e x ti t e r a t i v e m e a n w h i l e ，a ne x a m p l e i sg i v e nt oi l l u s t r a t ee f f e c t i v i t yo ft h ea l g o r i t h m ( f t ) i nt h es e c o n dp a r t ，w ep r o p o s ea n o t h e rs o l v i n ga l g o r i t h mf o rt h ep r o b l e mp r e - s e n t e di nt h ef i r s tp a r t t h a n k st ot h ed e t a i l e dd e s c r i p t i o n si nt h ef i r s tp a r t ，w e o b s e r v et h a tt h eb i l e v e lp r o g r a m m i n gc a nb et r a n s f o r m e di n t oas i n g l el e v e lp r o - g r a m m i n g d u et ot h ep a r t i c u l a rs t r u c t u r eo ft h ep r o b l e m ，w ed e s i g nam u l t i p l i e r a l g o r i t h m ( c z ) t os o l v ei t ，w h i c hi sb a s e do nt h en o n m o n o t o n i ct e c h n i q u e w ef u r - t h e rg i v ea ne x a m p l et oi l l u s t r a t ee f f e c t i v i t yo ft h ea l g o r i t h m f i n a l l y , w eg i v et h e r e l a t e dp r o o fa b o u ti t sc o n v e r g e n c e k e y w o r d s ：n o n l i n e a rb i l e v e lp r o g r a m m i n g ，t r u s tr e g i o nm e t h o d ，n o n m o n o - t o n e ，f i r s to r d e ro p t i m a l i t yc o n d i t i o n i i l 、 y v 。， 夸曩女一 t 、 l - 7 1 中文文摘 中文文摘 本文主要探讨非线性二层规划问题的求解算法研究的依据主要是非线性规划 求解算法的相关理论以及二层规划的相关理论文章的结构安排如下： ! 鼻 第一章概括了目前国内外学者关于非线性二层规划问题的研究情况和主要成 果，指出二层规划有着重要的理论意义和广泛的实际应用背景 第二章研究下层凸的非线性二层规划问题基于过滤信赖域模型的近似求解算 法本文研究的二层规划问题描述如下： m i n f ( x ，y ) s 乜q m ? l n 焉x 乙； 1 ， r l，凹j s t g ( x ，y ) 0 其中f ) 厂，g 一阶连续可微，g 二阶连续可微 首先建立问题的线性二次二层规划的近似模型： m l n z ，掣 s t 如果用( 虿，歹) 表示当前迭代点，则f m ，厶，疵表示ef ，g 在当前迭代点处展开 的t a y l o r 级数的一次近似，g m 表示g 在当前迭代点处展开的t a y l o r 级数的二次 近似 这个线性二次二层规划问题( 1 4 ) 可以转为一个混合整型规划问题m i p 求解 i i i 4 一 d 彤 彤 一 们们厶c 霎 口。眦唑甲随 r 这个m i p 问题可以表示为： m i n 蠢+ 透g 。，暑， 1口 s t f i z 一虿i i 。a k ， ij 矽一可i i 七 a l x + a e y a 1 虿+ a 2 y a ( e ，可) 皿z + h 2 y 研虿+ h 2 y 一9 ( 虿，动 0 九m 筋，i = 1 ，m 2 f 凰虿+ 凰可一夕( 虿，可) 一所虿一凰刳m 0 一旎) ，i = 1 ，仇2 兹 o ，1 ) ，i = 1 ，m 2 烈1v t l 2 + q 2 1 ) z + q 2 2 y + 可a + 1 2 = 0 其中 v 。f ( 虿，功酞m ， c 2 以g ( 虿，歹) p l n - ，a 2 v z f ( x ，可) 1 ，d 2 以夕( 虿，歹) 瓞m 2 m ，凰 v ：z ，( 虿，可) 跫竹- n ，q 1 2 v 玉厂( 虿，可) 瓞他， q 2 2 如一q i 2 虿一q i 2 歹豫m v ! ，f ( 虿，动酞m ， 以g ( 虿，歹) r m ，n 。， v ，( 虿，可) 跫竹：， 玩夕( 虿，功r m 。他。， v ：，( 虿，可) 娃n - n 。， v 品厂( 虿，可) 廷n 2 n 2 ， 求解这个线性二次二层规划，得到其解为( z 仇，矿) 将z m 代入下层问题 求解( 1 6 ) ，得到其解为y r a i n f ( x m ，y ) 可 s t g ( x m ，y ) 0 ( 1 5 ) ( 1 6 ) 这个下层问题需要求全局最优解，因此，若下层问题非凸，需要用全局优化方 法求解 以下简单描述这个算法( f t ) ： 1 给出初始信赖域半径o ，参数叼1 ，7 7 2 ，7 1 ， 7 2 ，满足0 7 7 1 7 7 2 1 且0 ，y 1 他 7 1 1 ，则令( z ( 南+ ，可( 七+ 1 ) ) = ( x m ，剪+ ) ，兀+ 1 = 氕否则，计算 g j = c ( x m ，可+ ) 若y g t 兀，3 i 1 ，佗 ，使得 g i ( z m ，+ ) i i g z ， i 二7 g i i g 吉i i ， 则令( z ( 后+ ，( 七+ 1 ) ) = ( x m ，+ ) ，将g 吉加到过滤集兀中并删除其中满足条件： g z ，“i g 蛳i ，v j 1 ，2 ，钆) 的向量形成y k + 1 否则，令 ( z ( 七十，可( 惫+ l ) = ( z ( 黼，可( 七) ，$ - k + 1 = 氕 n ， v 、 鼍 福建师范大学徐凌硕士学位论文 6 更新信赖域半径 若p k 7 7 2 ，则取a k + 1 ( 七，7 3 a 七 7 若以下任一条成立，则退出算法 ( 1 ) 在一次成功迭代之后忙( 七十1 ) 一z ( 七| | o ( i = 1 ，m ) ，允许误差0 ，常数 p ( 0 ，1 ) ，罚参数丌，正整数7 7 ，置k = 1 ； 、 3 以( z 七一1 1 ，y ( k - 1 ) , 入七一1 ) 为初点，解规划( 2 2 ) 对应的无约束问题 i 得解( z ( 舶，可( 肭，入( 知) ) ； m i n p ( x ，y ，a ，p ( 七一，盯( 七一1 ) ) z ，y ，a ( 2 7 ) 4 若l i c ( 一) ( z ( m ，可( 舢，a ( 七) 0 - 1 而且i i c ( 一( z ( 躺，秒( m ，入( 七) f l j 3 m a x jj c ( 一) ( z ( 七一，( 七一，a ( 知一1 ) ) ， i i c ( 一) ( z ( 后一，秒( 七一，入( 七一2 ) 怯，l i c ( 一( z ( 知一什1 1 ，秒( 知一计1 1 ，a ( 七一叼+ 1 ) ) 怯) ， 则称非单调条件成立； 对i = 1 ，7 7 5 ，令 a ：t m ) _ - - o ( i = 1 ，m ) ( 2 ) c ( 一) ( z ) = m i n 0 ，c ( z ) ) ( 3 ) 算法中对于函数f m i n s e a r c h 而言，e x i t f l a g 是一个描述退出条件的输出型 参数 e x i t f l a g = 0 代表函数评价次数超出m a t l a b 预设值m a x f u n e v a l s 或算法 迭代次数超出m a t l a b 的预设值m a x i t e r 接着，若f ，g ，厂，g 都是二次连续可微函数，且下层规划中，和9 都是对y 的 凸函数，则有以下两个结论： 定理1 ：( 有限终止性) 设问题( 2 3 ) 的可行域非空，则对任何e 0 ，算法( c z ) 必有限终止或者产生的点列 ( z ( m ，可( 肭，入( 南) ) 满足1 i mi n fh ( x ( 肼，秒( m ，a ( 知) = 一。o 定理2 ：设问题( 2 3 ) 的可行域非空则算法( c z ) 在= 0 时产生的点列 ( z ( 扪，秒( 剐，a ( 南) ) ) 之任何聚点( x + ，y + ，a + ) 都是可行点，如果 p ( 詹) ) 有界则( 矿，y + ，a + ) 必是原问题( 2 3 ) 的解 在本章最后，在m a t l a b7 3 0 环境下完成算例加以佐证 v i i i 、 e h 记号与约定 记号与约定 m i n ：极小化 v ，：函数f 的梯度 a t ：矩阵a 的转置 r ：实数域上的维欧氏空间 1 1 i i ：欧氏范数 ”i i o o ：无穷范数 ：属于 川：a 的绝对值 v ：任意 j ：存在 c ( 一) ( z ) ：表示m i n 0 ，c ( z ) ) q 一：表示m i n 0 ，q ) m a x x ，可) ：表示取x ，y 较大者 以厂：对函数，关于x 求j a c o b b i 函数 v 。厂：对于函数，关于x 求梯度 黔1 黼2 ：r 的礼1 仡2 维欧式空间 ：求和 一：定理或命题证毕，例子求解完毕 i x ： k 、 l h l 尊) 福建师范大学徐凌硕士学位论文 目录 摘要 i a b s t r a c ti i 中文文摘 i i i 记号与约定 i x 绪论 1 0 1 历史文献介绍 1 0 1 1 概述 1 0 1 2 二层规划算法研究成果概述 2 0 1 3 二层规划应用研究 3 0 2 本文主要工作 4 第1 章非线性二层规划的过滤信赖域算法 6 1 1 过滤信赖域算法 7 1 2 基于过滤信赖域方法的非线性二层规划求解算法 9 1 2 1 算法简述 9 1 2 2 数值试验1 3 第2 章 基于乘子法的非线性二层规划的算法1 9 2 1 罚函数方法求解非线性二层规划问题的概述1 9 2 2 非线性二层规划的基于乘子法和非单调罚函数方法的一种算法2 2 2 2 1 算法简述2 2 2 2 2 收敛性证明2 3 2 2 3 数值试验2 7 x 、 i 目录 第3 章结论3 1 参考文献一3 2 攻读学位期间承担的科研任务与主要成果 3 7 致谢 3 8 个人简历 4 0 x 1 ， 一 lli 绪论 绪论 0 1 历史文献介绍 o 1 1 概述 1 9 7 3 年，b r a c k e n 和m c g i l l 首先提出二层规划模型的标准形式，1 9 7 7 年， c a n d l e r 和n o r t o n 第一次在他们的文章中使用了二层规划和多层规划这两个名称， 二层规划作为一种特殊的多目标规划问题和经济中的l e a d e r - f o l l o w e r ( s t a c k e l b e r g ) 博弈是密切相关的，二层规划可以被看作是包含两个独立决策者的l e a d e r - f o l l o w e r ( s t a c k e l b e r g ) 博弈，它是一种典型的非凸不可微优化问题 二层规划的标准数学模型如下： m l n z ， s t f ( x ，y ) g ( z ，) o 、 ( o 1 ) m i n f ( x ，y ) 、。 s t g ( x ，) 0 若f ( x ，秒) ，a ( x ，2 ，) ，f ( x ，) ，g ( x ，y ) 都是关于变量z ，y 的线性函数，则问题( o 1 ) 称 为线性二层规划问题二层规划简称b l p p ，可以从它的标准形式中看出它是由上 层规划和下层规划共同构成的，二层规划是具有递阶结构的优化问题，上层与下层 的关系如下：一方面，根据上层规划取最优解，将这个最优解传到下层，同时影响 下层规划的可行集；另一方面，下层作出的决策将传到上层，影响上层的可行集作 决策；这样的过程往复进行，直到上层目标函数的值不再减小 由于二层规划在经济决策和机械设计等领域的应用，1 9 8 0 年开始，它引起了 广泛的关注，对于二层规划的研究主要包括：二层规划性质，二层规划求解算法， 二层规划实际应用三个方面其中二层规划算法的研究最为广泛 然而，二层规划的难解性从线性二层规划中可见一斑1 9 9 2 年，h a n s e n 等人 福建师范大学徐凌硕士学位论文 【1 】中指出，线性二层规划问题是强n p 难问题；1 9 9 6 年，v i c e n t e 等人在【2 】中指 出，求解线性二层规划的局部最优点也是一个n p 难问题 o 1 2 二层规划算法研究成果概述 关于二层规划问题的算法研究，已经有大量成果，以下对这些研究成果进行简 要的介绍： ( 1 ) 分枝定界法 3 】：分枝定界法是二层规划求解算法中研究最广泛深入的，已被 扩展用于求解线性二次二层规划，又有学者将这种方法扩展用于求解非线性二层规 划，其中包括下层非凸的非线性二层规划实践表明，分枝定界法是很有效的求解 工具，而且分枝定界法可以求变量有界的二层规划问题全局最优解，但同时分枝定 界法存在存储量和计算量大的问题 ( 2 ) 遗传算法和模拟退火算法【4 l ：遗传算法由于具有很强的全局搜索能力，因此 在二层规划研究中备受重视，但是遗传算法同时又具有局部搜索能力不足等缺点， 因此和经典的数学规划方法相比较求解效果差；另一方面，双层规划问题的递阶结 构决定了其诱导域相对狭小，使用遗传算法将产生大量的不可行点，从而降低了算 法的效率一方面，和遗传算法一样，模拟退火算法也具有相似的缺点；另一方面， 模拟退火算法只收敛于局部最优点，这使得这种方法和经典的数学规划相比不具优 势，因此，应用模拟退火算法进行二层规划的研究相对较少 ( 3 ) 割平面算法和极点搜索算法【5 ，6 】：割平面法研究二层规划主要针对的是线性 二层规划割平面法思路简单，首先将线性二层规划通过k k t 条件转化为单层带 互补约束的优化问题；接着，引入割平面法对不满足互补约束的极点进行割除这 种算法的缺点在于割平面法将引入大量的约束以割除极点，这样计算的效率将大大 降低第一个线性二层规划问题的全局收敛算法是c a n d l e r 和t o w n s e l y 提出的， 这种算法通过反复求解两个线性规划得到约束域极点的单减序列来实现；另一种经 典的极点搜索方法就是b i a l a s 和k a r w a n 提出的k - b e s t 算法，这种算法具有全局 收敛性，但是和极点搜索算法一样，它的计算量和储存量也很大 2 ( 4 ) 平衡点算法【7 】：平衡点算法已被应用于求解线性二层规划及线性二次二层 规划，主要思路如下：首先利用k - t 充分条件和罚函数法先将线性二层规划( 或线 性二次二层规划) 转化为单层无约束问题，接着，由无约束问题得到简单的参数线 性规划，通过单纯形法解参数线性规划，得到平衡点，最后，判断平衡点是否为原 二层规划的最优解 ( 5 ) 罚函数方法：这类方法主要被用于求解驻点和局部极小点，a i y o s h i 和 s h i m i z u 8 ，9 】给出这种方法的初始步i s h i z u k a 和a i y o s h i 1 0 】针对这类问题提 出了关于f 和厂的双罚函数方法，c a s e 1 l 】把 1 2 】的线性二层规划的方法推广用 于求解下层系统可被转化为k k t 条件的二层规划问题 ( 6 ) 下降算法p s i ：这种算法假定上层变量x 对应的下层问题的最优解是唯一 的，且可是x 的隐函数，这样，二层规划( 0 1 ) 实际可以被看作是只关于变量x 的 问题 此外，还有的研究成果应用原始对偶算法，互补旋转算法，起作用集算法来求 解二层规划【4 】 o 1 3 二层规划应用研究 以下简述二层规划的应用： ( 1 ) 原厂设备制造【1 4 】：原厂设备制造简称( o e m ) 业务，指品牌拥有者拥有核 心技术，自行设计委托厂商进行加工o e m 业务中，委托方一般是大中型企业，被 委托方一般是中小型企业，被委托方数量远少于委托方数量，因此处于从属地位， 被委托方与委托方的关系可以用二层规划表示 ( 2 ) 不确定市场的最优竞价p 6 j 在不确定电力现货市场条件下，发电商和售电 商关于长期合约交易与现货交易之间的最佳选择策略方法可以用随机二层规划模型 表示 ( 3 ) 无功优化问题【1 6 】：电网的无功优化问题中有许多不确定的因素，若采用常 规的单层优化模型和算法，难以获得满意、实用的无功优化方案，而用计及负荷不 3 福建师范大学徐凌硕士学位论文 确定性因素影响的无功优化双层规划模型可以解决 ( 4 ) 城市公交问题 1 7 - 3 0 ：二层规划在城市公交网络方面的应用涉及到城市高速 公路网络入口流量控制，城市公交网络可靠性，城市公交系统连续平衡网络设计， 城市轨道交通网络布局及设计，大型活动后车道单行优化，多车型高速公路离散平 衡网络设计，高速公路网入口流量控制，公交换乘优惠，公路网络路线布局优化， 公交调度，收费公路合理规模确定方法，交通信号控制，区域公交时刻表及车辆调 度，收费道路均衡配流等 ( 5 ) 物流问题 3 1 - 3 s ：二层规划在物流方面的应用涉及到第三方物流分包商选 择，第三方物流分包合同设计，物流中心选址，区域港口内陆运输网络优化决策， 物流系统集成定位，虚拟物流企业伙伴选择，物流中心扩建规模设计，物流中心布 局规划等方面问题的研究 ( 6 ) 商业决策 3 9 - 4 5 二层规划在商业决策方面的应用涉及到商业信用期限决 策，供应链二级分销网络生产计划，供应链定价决策，供应链多阶响应周期决策， 供应链契约谈判，采购策略，供应链协调机制等 ( 7 ) 机器人系统研究【4 6 ，4 7 】：国内已将二层规划应用于喷涂机器人轨迹研究和足 球机器人系统研究 ( 8 ) 无线传感器网络【4 8 】：二层规划已被应用于解决无线传感器网络中参数设定 问题 ( 9 ) 二层规划的应用还扩展到教育投资问题【4 9 】，车票定价问题【5 0 1 ，及油田开发 【5 1 】，资源优化【5 2 1 ，连锁超市管理【5 3 】等领域 0 2 本文主要工作 非线性二层规划问题在经济决策、工程设计、交通规划等方面有着巨大的应用 价值；另一方面，二层规划问题有着深刻的经济背景一一s t a c k e l b e r g 博弈这一 切都激励着人们对非线性二层规划进行探索，但二层规划的研究从上个世纪七十年 4 绪论 代才逐步开展，因此，对于二层规划问题的研究还不够完善从优化研究的领域来 说，作为优化的一个重要分支，它在优化理论的发展及算法的研究中具有十分重要 的作用，因此，这方面的理论正日益受到人们的重视现在发展起来的二层规划算 法很多，但是这些求解算法相当一部分需要大运算量和大储存量，这是二层规划问 题本身的特殊结构所决定的，方便易行的方法并不多见考虑到这一点，本文研究 了几种易于操作的非线性二层规划算法 考虑到非线性二层规划模型在生产生活中的巨大应用价值，本文主要研究非线 性二层规划问题的若干求解算法本文的研究主要针对下层规划关于可凸的非线性 二层规划展开 本文由两章组成第1 章，在前人的研究基础上，将过滤信赖域算法进行改进， 用于二层规划的求解第2 章，研究第1 章所提问题的另一种求解算法根据第1 章中得到的问题的等价形式，设计出一种有效的基于非单调技术和乘子法的非线性 二层规划问题的求解算法 5 臻， 福建师范大学徐凌硕士学位论文 第1 章非线性二层规划的过滤信赖域算法 本章考虑下列二层规划： m i n f ( x ，y ) s l 斟m 主n 甓) ( 1 1 ) l r i z j s t g ( x ，y ) 0 其中f ( z ，可) ，g ( z ，秒) ，9 ( z ，y ) 是一阶连续可微函数，( 。，y ) 是二阶连续可微函数 1 9 9 8 年，l i u 5 4 】提出了一种用线性二次二层规划近似求解下列二层规划问题 的方法 m i n f ( x ，y ) r a i n ，( z ，y )( 1 2 ) s t g ( x ，y ) 0 在这种方法中l i u 引入信赖域方法，但是【5 4 】的方法被局限于求解没有上层约 束，且下层问题是带线性约束的强凸数学规划在论文【5 4 】的假设下，算法被证明 收敛于一个c l a r k e 驻点 2 0 0 5 年，c o l s o n ，m a r c o t t e ，s a v a r d 5 5 】在 5 4 】的基础上提出了一种算法用于 求解二层规划； m i n f ( x ，y ) 8 q m ? 1 1 2 麓x m ( 1 3 ) ，l， j s t 9 ( z ，y ) 0 并引入了基于f o o 范数的信赖域方法 本章把c o l s o n ，m a r c o t t e ，s a v a r d 5 5 的算法推广，用来求解非线性二层规划 ( 1 1 ) ，同时引入过滤信赖域框架作为评价，给出算例以验证这种算法的实用性和有 效性 6 第1 章非线性二层规划的过滤信赖域算法 1 1 过滤信赖域算法 首先，介绍一下信赖域算法的主要思想：信赖域算法主要用于求解目标函数厂 是二次可微的无约束非线性优化问题，其主要思想是在当前迭代点x k 周围用二次 模型m k 以近似厂，一般的， m 知p ) = + v t p + 去p t b k p 其中 = f ( x k ) ，v = v f ( x k ) ，b k 是某个对称矩阵 一方面，在每步迭代中，求解子问题 船m k ) = f k + v a t l 。p t b k p s t i i p l i 知 其中南 0 是信赖域半径，是欧几里得范数通过这个子问题解出m 另一方面，对极小化子问题所获得的步长p 知，令m = 甓京矧，则p k 是 实际下降量和预估下降量的比如果m 接近0 ，则说明模型m k p ) 不可信，因此， 缩小信赖域半径；相反，若m 接近1 ，则说明在这步迭代中模型m k p ) 和目标函 数厂很一致，因此j 放大信赖域半径接下来的算法描述了这个过程 算法1 1 ( 信赖域算法) 1 给定五 0 ，o ( o ，五) ，7 7 0 ，j ) ；对于k = 0 ，1 ，2 2 通过近似求解子问题获得m ，估计p k ； 3 取 r - a k + l = 气 【 ；1 1 p k l l ， m i n ( 2 a 知，) ， 七， 4 若p k 叼，则x k + 1 = x k + p k ；否则，x k + l = x k ； 7 = i i 七n i ；且 1 4 3 4 胀m 则若若否 福建师范大学徐凌硕士学位论文 其中五是步长的全局边界 接着，介绍一下过滤技术，以及过滤信赖域算法的框架【5 6 1 2 0 0 2 年，过滤技术首先由f l e t c h e r 等人在文 5 7 】中提出，迅速在约束优化领 域取得了长足的发展，过滤技术在算法中的主要作用就是用来放宽迭代步的接受条 件，起到加速迭代收敛的作用，这一点在大中型的规划中体现的尤为明显 在基本信赖域框架中，仅当p k ? 7 时才接受x 七+ ，因此，在信赖域算法框架中 引入过滤技术来加大试验点x k + 被接受的几率，把梯度v ( x ) 记成分量形式 w ( x ) = g ( x ) = ( g l ( z ) ，鲰( z ) ) t 任给两个点z 1 ，z 2 ，当i 吼( z 1 ) i l 仇( z 2 ) i ，( v i = 1 ，佗) 时，我们称z 1 优于 z 2 ，也称z 2 次于x 1 这样，当我们仅关注迭代点列是否收敛于一阶稳定点时，我 们只需要观察点z 1 下面引入针对无约束优化问题的过滤集概念 定义令厂= ( 鲰，1 ，g k ，住) t ) 知z ，其中g k ，t = g i ( x k ) 是函数f ( x ) 在点x k 处 的梯度向量的第i 个分量，z 是一个指标集若对任意不同的k ，f z ，至少存在 一个i 1 ，礼 ，使得i g k ，“ l g l ，“成立，则称厂是由佗维梯度向量组成的过滤 集 过滤法就是当试验点钆+ 不次于相应过滤集氕中的任意点时就接受试验点的 方法，其中兀就是在迭代过程中由各迭代点处的梯度向量按照一定的规则逐步更 新形成的实际计算中，当+ 非常接近于兀中任一点时，我们也不打算接受这 个测试点；当且仅当氕，3 i 1 ，n ) ，使i g t ( x k + ) i i g t ，“一l | 对l i 时， 我们称x k + 可被过滤集兀所接受( 实际意为站= g ( x z ) 可被兀接受) ，其中 ( 0 ，去) 是一个常数当钆+ 被其相应的过滤集氕接受时，我们将g k + 加入 到兀中，从中去除所有满足i g l , j i i g k ，j l ，( v j 1 ，竹) ) 的向量g t ，得新的集合 兀+ 1 显然氕+ 1 满足定义的要求，从而实现了过滤集的更新 8 第1 章非线性二层规划的过滤信赖域算法 下文中，将点x k 加入到过滤集中的含义就是将点z 七处的梯度向量g k 加入到 过滤集中以下是过滤信赖域算法： 算法1 2 ( 过滤信赖域算法) 0 取初始点x o 和初始信赖域半径a o ，常数( o ，击) ，0 ，7 1 现 1 ， 0 饥7 2 7 7 1 ，则+ 1 = z 去，氕+ 1 = 氕；否则，计算站= 9 ( z 吉) 如果z 者被兀所接受，则x k + 1 = z 吉，将z 吉更新到过滤集兀中形成氕+ 1 ； 否则，x k + 1 = x k ，五十1 = 氕 4 更新信赖域半径 若p k 啦，贝0 取后+ 1 ( a k ，6 3 a k ， 5 令尼= k + 1 ，转1 1 2 基于过滤信赖域方法的非线性二层规划求解算法 1 2 1 算法简述 首先建立问题( 1 1 ) 的线性二次二层规划的近似模型在当前迭代点周围分别 计算f ，g ，g 的线性近似函数，以及下层目标函数厂的二次近似函数如果用( 虿，可) 表示当前迭代点，则可以建立以下的模型函数： 其中 ( z ，y ) g m ( z ，y ) ，m ( 。，y ) ( 。，y ) = f ( _ ，功+ c 丁0 一- ) + c j ( 一歹) ， = g ( z ，可) + a 丁( z 一虿) + a - j ( y 一可) ， = 厂( z ，_ ) + d 丁( z 一动+ 四( 可一功+ ；( z 一虿) t q l l ( z 一虿) + ( z 一面) t q l 2 ( y 一可) + ( 秒一可) t q 2 2 ( 一可) ， = 9 ( 虿，功+ 月丁( z z ) + 丑丁( 秒一可) ， c l = v z f ( 虿，可) 砭n - ，c 2 = v 掣f ( 虿，可) 匙n z ， 4 1 = 乃g ( 虿，可) r m l n - ， a 2 = 况g ( 虿，可) 匙m 1 x n 2 ， d l= v 茹f ( x ，动妒1 ，d 2 = v ，( 虿，歹) 跫n z ， 研 = 况夕( 虿，可) r m 2 黼，凰 = 以夕( 虿，可) p z 砒， q n = v ：z f ( x ，功爬n l x m ，q 1 2 一v ： f ( x ，功碾犯z x 砌， q 2 1 = v ；z ，( 虿，可) r n 2 m ，q 2 2 = v 品，( 虿，可) p z m 接下来给出( 1 1 ) 的线性二次二层规划近似模型： r a i n 凡( z ，y ) 茁，掣 s t g m ( z ，y ) 0 m i n ，m ( z ，y ) s t ，y ) 0 这个线性二次二层规划问题可以转为一个混合整型规划问题m i p 求解 为方便表示m i p 问题，引入以下记号： g 夕 r 1 r 2 。拽中- 节 _ 茁 g ( z ，功一a l x a 2 可， 夕( z ，可) 一皿虿一飓可， d 1 一q 五可一q 矗虿p - ， 如一q l 虿一q 乏歹时。 1 0 孙r p p 十州埘 ( 1 4 ) q 第1 章非线性二层规划的过滤信赖域算法 这个m i p 问题则可以表示为； m i n c iz + c 2y z ，童， s t 1 1 z 一虿i i ， 0 可一可i i 七 a l x + a 2 y a 1 - z + a 2 可一g ( 虿，可) h l x + h 2 y 凰虿+ 日2 可一9 ( 虿，功 0 入t m 筋，i = 1 ，m 2 【皿虿+ h 2 y 一9 ( 虿，动一h z 一岛勿m ( 1 一筋) ，i = 1 ，m 2 旎 o ，l ，i = 1 ，r - t 2 1 ( q t 一2 + q 2 1 ) z + q 2 2 y + 可入+ r 2 = 0 ( 1 5 ) 求解问题( 1 5 ) ，得到其解为( z m ，y m ) 将。代入下层问题 m 耖i n m m ，y ) ( 1 6 ) 耖 i1 b l s t 9 ( z m ，y ) 0 求解问题( 1 6 ) ，得到其解为y 。这个下层问题需要求全局最优解，因此，若下 层问题非凸，则需要用全局优化方法求解 以下简单描述这个算法( f t ) ： 1 给出初始信赖域半径o ，参数叩l ，7 7 2 ，7 1 ，讹，满足0 7 1 7 7 2 1 且0 7 1 9 2 r h ，则令( z ( 七+ ，可( 知+ 1 ) = ( z m ，可+ ) ，兀+ 1 = 氕否则，计算 g 吉= g ( z m ，可+ ) 若v g l 氕， 3 i 1 ，礼) ，使得 g i ( z m ，秒+ ) i i g l ，t i - ，y g i l g j i i ， 则令( z ( 凫+