logo资料库

利用GRG解一类非线性二层规划 .pdf

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：0.30M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    中国科技论文在线 http://www.paper.edu.cn 利用 GRG 解一类非线性二层规划 黄银珠 张圣贵 福建师范大学数学与计算机科学学院 福建福州 (35007) E-mail:yinzhu326@126.com 摘要摘要摘要摘要:本文主要研究了一类下层是凸的二层规划的一种求解算法.在下层是凸的情况下,我们 可以将下层用其 KKT 条件代替,从而把原二层规划转化为单层非线性规划,进而借用广义既 约梯度(GRG),提出一种简单有效的下降算法来解该规划,并通过数值算例的计算结果说明 了该算法的可行性和有效性. 关键词关键词关键词关键词: 二层规划 KKT 条件下 GRG; 下降方法 1.引言 随着人类社会的发展,人们发现有的实际问题用单层规划模型去描述已是十分困难并且 是不合适的.应用的需求使得人们不得不将视线更多地集中于多层规划.对于多层规划的研究 也有了悠久的历史.在对多层规划的研究中,二层规划是一个重要的研究对象.二层规划研究 的是具有两个层次系统的规划与管理问题, 上层决策者只是通过自己的决策去指导下层决 策者,并不直接干涉下层的决策;而下层决策者只需要把上层的决策作为参数,它可以在自己 的可能范围内自由决策.二层规划的基本形式为 )F x y min ( , . .st G x y ≤ ( , ) 0 (1) min f x y ) ( , . .st g x y ≤ ( , ) 0 其中 mx R∈ , ny R∈ 分别称为上,下层变量, F R R R , × → : m n f R R R × → : m n 分别称为 上,下层目标函数, G R R R l × → : m n , g R R R k × → : m n 分别称为上,下层约束函数. 在实际生活中广泛存在着可以描述为二层规划模型的问题,人们对二层规划的理论,算法 都进行了较深入的研究.二层规划问题的一般决策过程为:上层先约定一个决策,下层子系统 则以这个决策为参量,根据自己的目标在可能的范围内选定一个最优决策,并将自己的最佳反 馈给上层,上层再在下层最佳反应的基础上,在可能的范围内做出整体最优决策.二层规划可 划会为线性二层规划和非线性二层规划.若 F G f g , , , 全为线性函数, 则称(1)为线性二层规 划;若 F G f g , , , 至少有一个为非线性函数,则称(1)为非线性二层规划. 一般来说,求解二层规划问题是非常困难的, 文献 指出线性二层规划是一个 Np-hard [1] 问题. 文献 对此结论给出了简短的证明, 文献 对线性二层 规划是强 Np-hard 问题给出 [2][3] [4] 1
    中国科技论文在线 http://www.paper.edu.cn 了严格的证明. 文献 指出寻找二层规划的局部最优解也是 Np-hard 问题,不存在多项式时 [5] 间算法.相对于线性二层规划来说,非线性二层规划的求解更加困难而且绝大多数关于求解非 线性二层规划问题的数值方法研究,或者局限于具有某种特殊结构,或者局限于求局部最优解. 由于对于非线性二层规划问题的求解算法都是借助于问题本身的特殊结构而设计的,所以,很 难将其算法推广到求解一般的非线性二层规划问题中.对于一般的非线性二层规划问题, 文 [6][7] 献 提出了基于下层问题的某种最优性条件或者是利用下层问题的最优解关于上层决策 变量的梯度信息的求解方法; 文献 提出了一种网格搜索法,它是建立在非线性二层规划问 [8] 题的两种最优性的基础上,需要求解一系列非凸的非线性规划问题; 文献 在下层问题解唯 [9] 一的情况下,提出了一种基于模拟退火算法求解非线性二层规划问题的方法,在算法中引入了 一个辅助优化问题,通过求解该辅助优化问题产生满足上层约束的试探点,从而避免了使用罚 函数的弊端. 本文主要研究下这样一类非线性二层规划: F G f g , 连续可微且 , , if g , 关于变量 是 y 凸函数.下层用 KKT 条件代替,将原二层规划化为单层非线性规划,进而利用广义既约梯度给 出此类二层规划的一种下降方法.文章安排如下:在第二节中,我们把要求解的二层规划(1)转 化为单层非线性规划问题;第三节中,我们利用广义既约梯度提出针对模型(1)的一种新的算 法;最后通过数值算例,说明了该算法的可行性,并给出了结论. 2.二层规划的转化 对于固定的 ,假设 x g x y ≤ ( , ) 0 满足 Slater 条件,由凸规划的最优性理论,下层问题等价 于如下 KKT 稳定点问题 (2) .用式 g x y y k ( , ))T ∇ y f x y ) ( , + ∇ T ξ g x y ( , y ) 0 = g x y ( , ) 0, ξ≤ ≥ 0 Tg x y ξ ( , ) 0 = 其中 1( ξ ξ = ⋯ , , ξ k )T 是 Lagrangian 乘子, ∇ g x y ) ( , y = ∇ ( g x y ), y 1 ( , ∇⋯ , (2)代替(1)的下层得: min )F x y ( , . .st G x y ≤ ( , ) 0 ∇ y f x y ( , ) + ∇ T ξ g x y ( , y ) 0 = g x y ( , ) 0, ξ≤ ≥ 0 ig x y T ξ i ( , ) 0 = , i = ⋯ 1,2, k . 2
    中国科技论文在线 http://www.paper.edu.cn 在上式的约束中加入松弛变量 λ 1 λ∈ 2 R ,l ∈ R k 得 min )F x y ( , . .st G x y λ+ 1 ( , ) = 0 ∇ y f x y ( , ) + ∇ T ξ g x y ( , y ) 0 = g x y λ+ ( , 2 ) = 0 ig x y T ξ i ( , ) 0 = , i = ⋯ 1,2, k . ξ 0, λ≥ i ≥ 0, i = 1,2. 这样就把(1)转化为非线性单层规划(3). 3.算法 现在考虑非线性规划问题: min )F X ( . .st H X = ) 0 ( (3) (4) u X l ≥ ≥ H R R→ p : q 其中 qX R∈ , l R∈ q , qu R∈ , : qF R R→ , 续可微函数. )H X ( 的 Jacobi 矩阵为: , p q≤ , iF H i ( , = ⋯ 1,2, , p ) 是连 H ∂ X ∂ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ = ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ H ∂ 1 X ∂ 1 ⋮ H ∂ i X ∂ 1 ⋮ H ∂ p X ∂ 1 ⋯ ⋯ ⋯ H ∂ 1 X ∂ q H ∂ i X ∂ q H ∂ p X ∂ q ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 的秩为 s p≤ ,这里假设经过重新标号,使得 H ∂ X ∂ 的前 行 列构成 s s 的最大主子式,设 的前 个分量为基变量 ,剩余的 s BX q s− NX 个分量为非基变量 , 对于当前可行解 , X H ∂ X ∂ X H ∂ X ∂ 3
    中国科技论文在线 http://www.paper.edu.cn h ∂ X ∂ = H ∂ 1 X ∂ 1 ⋮ H ∂ s X ∂ 1 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⋯ ⋯ H ∂ 1 X ∂ q H ∂ s X ∂ q ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ( 则 非奇异. h ∂ X ∂ h h ∂ ∂ X X ∂ ∂ N B , ) 由 H X = ) 0 ( 的前 个方程 s h X = ( ) 0 BX , 可用 表示,从而把目标函数 NX F X X N , B ( ) 化为只关于 NX 的函数 F X X X N ( B ), ( N ) ,我们用文献 中的方法来求 的既约梯度 [10] F r X ( N ) 其中 = ∇ F X X X N ( B ), ( N ) .主要采用微分法求广义的既约梯度.目标函数的微分 dF = ∇ ( F dX B ) T + ∇ ( F dX N ) T X N X B ∇ X B F = ( F ∂ X ∂ 1 , ⋯ , F ∂ X ∂ s ) T , ∇ F = ( X N F ∂ X ∂ s 1 + , ⋯ , F ∂ X ∂ q ) T dX dX 1 = ( B , ⋯ , dX )T s , dX dX S 1 + = ( N , ⋯ , dX )T q 为了用 NdX 表示 BdX ,使用恒等式两端取微分的方法,从 hx = ( ) 0 得到 dh 1 ⎧ ⎪ ⎪⎪ ⎨ ⎪ dh ⎪ s ⎪⎩ = h ∂ 1 X ∂ 1 = h ∂ s X ∂ 1 dX 1 + ⋯ + ⋮ dX 1 + ⋯ + h ∂ 1 X ∂ q h ∂ s X ∂ q dX q = 0 dX q = 0 h ∂ X ∂ B dX B + ⋯ + h ∂ X ∂ N dX N = 0 即 由于 可逆,因此有 h ∂ X ∂ dX B = − ( h ∂ X ∂ B 1 − ) h ∂ X ∂ N dX N 将(9)代入(5)得 从而得到既约梯度 dF = ∇ [ F − (( X N h ∂ X ∂ B − 1 ) h ∂ X ∂ N ) T ∇ F dX N ] T X B 4 (5) (6) (7) (8) (9)
    中国科技论文在线 http://www.paper.edu.cn r X ( N ) = dF dX N = ∇ X N F − [( h ∂ X ∂ B 1 − ) h ∂ X ∂ N ] T ∇ F X B 现在研究怎样确定搜索方向.一般情况下,定义 ,使它的分量满足: Nd d jN ⎧⎪= ⎨ −⎪⎩ 0, r X ( j N ), 当X =l 且r(X )>0或当X =u 且r(X )<0 N j N j j N j N j N j j N j 其他情形 (10) (11) 其中 是 的第 个分量, 是 的第 个分量, jNX NX j jNd Nd j jNl jNu 分别是非基变量 jNX 的下 界和上界.为从 出发求使得目标函数下降的可行点,定义 之后,取适当的步长 ,令 λ X Nd 使得 再求解非线性方程组 得到 .若满足 ˆy 并且 则得到新的可行点 ˆ( , )Ny X ˆ X X N = N + dλ N l X u N N ≤ ≤ N ˆ h y X = ( , ) 0 N ˆ F y X F X X N ˆ( , , B < ) ( N l y u B B ≤ ≤ ˆ (12) (13) (14) (15) ) ;若 不满足(14),(15)式,则减小步长 ,重复以上过程.若 充 λ λ ˆy 分小时,仍不能同时满足(12)(14)(15)式,则需改变 的某个或某几个分量的符号. Nd 算法: I. 给定初始点 ,允许误差 1X ε 1 20, ε> > 0 .置 1k= . II. 求 的最大主子式,将与其列相应的 的分量设为基变量 ,其余为非基变量 H ∂ X k ∂ NX k kX BX k ,由(10)式计算既约梯度,由(11)式求得方向 NdX k . III. 若 k NdX ε< 1 或 X k 1 + − X k ≤ 1(1 ε + X k ) 或 则停止计算,得到 ,否则进行步骤 IV. kX F X k 1 + − ( ) F X k ( ) ≤ ε 1 1 + F X k ( ) IV. 取 0λ> ,令 ˆ NX X k N = + dλ k N ,若 l X u N N ≤ ≤ N ˆ λ 则进行步骤 V,否则以 代替 , λ 1 2 5
    中国科技论文在线 http://www.paper.edu.cn 再求 ,直到满足 ˆ NX l X u N N ≤ ≤ N ˆ ,进行步骤 V.当 充分小,即 λ 2λ ε< 时,仍不能满 l X u N N ≤ ≤ N ˆ 足 ,则需改变 NdX k 的某几个分量符号. V. 求解非线性方程组(13) 令 y X j 1 = , k B = 1, y j 1 + = y j − [ ) h X ( k ∂ X ∂ B ] 1 − ˆ h y X ( N , j ) ,若 ˆ f y X ( N j 1 + , ) < f X ( k ), l y u+ , j 1 B B ≤ ≤ ˆ h y X ( N j 1 + , ) < ε 2 (*) 则转步骤 VI,否则以以 代替 ,令 1 2 λ λ ˆ NX X k N = + dλ k N ,重复以上过程.当当 充分 λ 小,即 2λ ε< 时,仍不能满足(*),则需改变 NdX k 的某几个分量符号.返回步骤 IV. VI. 令 X k 1 + = ( ˆ y X k 1 + N , ) ,置 k k= + : 1 ,返回步骤 II. 4.数值实验 例 [11] min x 2 y+ − ( 10) 2 . .st x y − + ≤ 0 0x≥ min ( x y+ − 2 2 30) . .st x y+ − 20 0 ≤ 0y≥ 经过 5 轮迭代算法停止,得 x = 10.0003, y = 9.9997 ,目标函数值为 100.006.事实上,由 [11] 文献 知本题最优解为(10,10). 6.总结 本文主要研究了一层是凸的二层规划的一种求解算法,先是将下层用 KKT 条件代替,将 其化为单层非线性规划,进而借用议既约梯度,提出一种简单有效的下降算法来解该规划,并 能过算例说明了该算法的可行性和有效性. [1]Jeroslow R. The polynomial hierarchy and a simple model for competitive analysis[J]. Mathematical programming,1985,32:146-164. [2] Ben-Ayed O and Blair C E. Computational difficulties of bilevel linear programming[J]. 参考文献参考文献 参考文献 参考文献 6
    中国科技论文在线 http://www.paper.edu.cn Operations Research, 1990,38: 556-560. [3] Bard J. Some properties of the bilevel programming proble[J]. Journal of Optimization Theory and Applications.1991,68:371-378 [4] Hansen P,Jaumard B,Savard G. New branch-and-bound rules for linear bilevel program- ming[J]. SIAM Journal scientific and statistical computing,1992,13:1194-1217. [5] Vicente L,Savard G,Judice J. Descent approaches for quadratic bilevel programming[J]. Journal of Optimization Theory and Applications.1994,81:379-399. [6] Aiyoshi E,Shimizu K. Hierachical Decentralized Systems and Its New Solution by A Barrier Method[J]. IEEE Transaction on Systems,Man,and Cybernetics,1981,11:444-449. [7] Aiyoshi E,Shimizu K. A Solution Method for The Static Constrained Stackilberg Problem via Penalty-method[J]. IEEE transaction on Automatic Control,1984,29:1111-1114. [8] Bard J. An Efficient Algorithm for Solving General Bilevel Programming Problem[J]. Mathematical Operations Research,1983,8:260-272. [9]杨若黎,顾基发.一类非线性两级规划问题的模拟退火求解[J].系统工程理论与实践,1997,7:52-58. [10]陈宝林.最优化理论与算法[M].清华大学出版社,2005:360-364. [11] KIYOTA SHIMIZU AND EITARO AIYOSHI. A New Computational Method for Stackel- berg and Min-Max Problems by Use of a Penalty Method[J]. IEEE transaction on Auto-matic Control,VOL.AC-26.1981,2:460-466. method Computational AAAA newnewnewnew Computational method forforforfor Computational method Computational method Programs Bilevel Nonlinear aaaa ClassClassClassClass ofofofof Nonlinear Programs bybybyby useuseuseuse ofofofof GRGGRGGRGGRG Nonlinear Bilevel Programs Bilevel Programs Nonlinear Bilevel HUANG Yin-zhu , ZHANG Sheng-gui 1 1 1 School of Mathmatics and Computer Science, Fujian Normal University,Fuzhou (350007) Abstract Abstract Abstract Abstract In this paper,we disscuss a class of nonlinear bilevel programming in which the second level is convex .The bilevel programming is tranformed into a single nonlinear programming by replacing the second level with its KKT condition.And with the help of General Reduced Gradient(GRG),a simple descent algorithm is given for it.The computational results of the examples show the feasibility and efficiency of the algorithm. words KeyKeyKeyKey words words words: Bilevel programming;KKT condition; GRG; Descent Direction. 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料