解多项式双层规划最优解的参数化方法

徐俊彦，苗 壮，刘庆怀

（长春工业大学基础科学学院，吉林长春130012）

解多项式双层规划最优解的参数化方法

徐俊彦，苗 壮，刘庆怀

（长春工业大学基础科学学院，吉林长春130012）

给出解多项式双层规划最优解的参数化算法.以上层变量为参数，对双层规划下层利用参数化方法求解；得到合理反应集代入上层，使双层问题转化为多项式规划求解.证明了算法的收敛性，数值例子表明算法是可行的.

全局优化；多项式双层规划；非孤立最优解

1 预备知识

最早双层规划是H.V.Stackelberg在研究经济问题时提出的，20世纪70年代作为优化问题进行研究.如文献［1-4］给出了求最优解的一些结论.文献［5-8］提出了基于参数规划理论和转化技术的算法.本文给出上层目标及约束函数都是非凸多项式的双层规划算法，该算法融入了非孤立最优解的思想，克服了现有一些算法有时得到的解为不可行解，甚至远离全局最优解的问题.

本文考虑如下多项式双层规划问题（Polynomial Bileverl Programming Problems）：

其中：α＝（α1，…，αn1），β＝（β1，…，βn2）为非负整数向量j＝1，…，m1，M6∈R；［M1］n1×n1，［M2］n2×n1，［M3］n2×n2，［M4］1×n1，［M5］1×n2，［N1］m2×n1，［N2］m2×n2，［N3］m2×1为实矩阵，且［M3］n2×n2是对称正定阵.

2 等价问题

考虑下层问题，x为参数作变换

下层问题转化为参数二次规划问题：

其中：

由文献［9］的结论，下层问题为可解的.对问题（2.2）采用参数规划算法求解［10］，得到合理反应集

将（2.3）式与（2.1）式代入（1.1）式的上层得：

其中α＝（α1，…，αn1）为非负整数向量，~c0α，~cjα∈R，j＝1，…，m1.

多项式双层规划问题（1.1）被转化为r个多项式规划问题（2.4）.根据文献［9］的结论，问题（1.1）有全局最优解.问题（2.4）最优解中最小的为（1.1）的全局最优解.多项式可分解为两个正系数多项式之差，即

由x1≤x≤x2，x1，x2∈，有

都是增函数.问题（2.4）与问题（2.5）等价.

记

则问题（2.5）表示为问题（FP）

显然，p（θ）为多项式增函数，且所有系数都是正数；而qj（θ）可分解为两个多项式增函数uj（θ）与vj（θ）的差，即

3 算法及其收敛性

设θ＊是问题（FP）的非孤立可行解，对问题（FP）的任意非孤立可行解θ，如果p（θ＊）＝min｛p（θ）：θ∈S＊｝，则称θ＊是问题（FP）的非孤立最优解（其中S＊为问题（FP）的所有非孤立可行解集）.为求解问题，文中作如下假设：

（H1）D＝｛（x，y）∈Rn1＋×Rn2，x1，x2∈Rn1＋：pj（x，y）≥0，j＝1，2，…，m1，x1≤x≤x2，N1x＋N2y＋N3≥0｝是非空闭集.

（H2）集合｛θ∈［θ1，θ2］：q（θ）＞0｝≠∅.

（H3）p（θ1）＜ρ－ε，q（θ1）≤0.

对ε≥0，若θ∈［θ1，θ2］满足q（θ）≥ε，则称θ为（FP）的ε-非孤立可行解.若¯θ是（FP）的ε-非孤立可行解，且满足p（¯θ）－ε≤inf｛p（θ）：q（θ）≥ε，θ∈［θ1，θ2］｝，则称¯θ为（FP）的ε-非孤立最优解.

为解问题（FP），考虑辅助问题（EP）

max｛q（θ）：p（θ）≤ρ－ε，θ∈［θ1，θ2］｝.

min（FP）和max（EP）分别表示（FP）和（EP）的最优值.下列定理给出（FP）和（EP）的关系.

定理1 假设（H1），（H2），（H3）成立，那么有下列结论：

（1）若θ0为（EP）任一可行解，且q（θ0）＞0，则θ0满足p（θ0）≤ρ－ε，且θ0是（FP）的非孤立可行解.特别的，若max（EP）＞0，则（EP）的最优点θ′满足p（θ′）≤ρ－ε，且θ′是（FP）的非孤立可行解.

（2）设＾θ为（FP）的非孤立可行解，若max（EP）＜ε，p（＾θ）＝ρ，则＾θ是（FP）的ε-非孤立最优解；若max（EP）＜ε，ρ＝p（θ2）＋ε，则（FP）不存在非孤立可行解.

证明 （1）根据q（θ1）≤0＜q（θ0），有θ0≠θ1，并且任一θ＝（1－μ）θ1－μθ0（0≤μ≤1），满足θ1≤θ≤θ0.当μ→1－，知θ→θ0，有q（θ）＞0，所以θ为（FP）的可行解.由于θ0是（EP）的任一可行解，有p（θ0）≤ρ－ε.所以θ0满足p（θ0）≤ρ－ε，同时θ0是（FP）的非孤立可行解.

（2）如果max（EP）＜ε，那么sup｛q（θ）：p（θ）≤ρ－ε，θ∈［θ1，θ2］｝＜ε，故任一θ∈［θ1，θ2］，且q（θ）≥ε，有p（θ）＞ρ－ε＝p（＾θ）－ε，这表明＾θ为（FP）的ε-非孤立最优解.若ρ＝p（θ2）＋ε，那么｛θ∈［θ1，θ2］：q（θ）≥ε｝＝∅，则（FP）非孤立可行解不存在.

3.1 基本操作

（1）将可行集进行矩形拆分，采用最长边二分法.

（2）不失当前可行解情况下，对拆分集有效缩减.令Θ＝［θ1，θ2］为感兴趣拆分集.求θ∈［θ1，θ2］，满足p（θ）≤ρ－ε的（FP）非孤立可行解.在集合Dρ∩［θ1，θ2］中求Dρ＝｛θ：p（θ）≤ρ－ε，q（θ）≥0｝.用较小矩形［θ′1，θ′2］⊂［θ1，θ2］代替［θ1，θ2］，且Dρ∩［θ′1，θ′2］＝Dρ∩［θ1，θ2］，满足该条件的矩形［θ′1，θ′2］记为red［θ1，θ2］.利用文献［4］中的引理可以实现上述目的.

3.2 算法描述

步0 给定收敛精度ε＞0.若可行解未知，则令ρ＝p（θ2）＋ε；否则，令ρ＝p（¯θ），¯θ是当前最好的非孤立可行解.令Q1＝｛Θ1｝，Θ1＝［θ1，θ2］，T1＝∅，k＝1.

步1 对Θ∈Qk，计算redΘ.若redΘ＝∅，则删除Θ；若redΘ≠∅，则用redΘ代Θ.若redΘ＝［θ′1，θ′2］，则计算上界V［EP（Θ）］，且使V［EP（Θ）］若V［EP（Θ）］＜0，则删除Θ.

步2 令Q′k为步1从Qk计算得到结果的集合；令T′k＝Tk∪Q′k.

步3 若Q′k＝∅，则迭代终止：若ρ＝p（¯θ），则¯θ为问题（FP）的ε-最优解；若ρ＝p（θ2）＋ε，则问题（FP）是不可行的.

步4 若Q′k≠∅，令［θ1k，θ2k］：＝Θk∈argmax｛V［EP（Θ）］：Θ⊂Q′k｝，V（EP）k＝V［EP（Θk）］.

步5 若V（EP）k＜ε，则迭代终止：若ρ＝p（¯θ），则¯θ为问题（FP）的ε-非孤立最优解；若ρ＝p（θ2）＋ε，则问题（FP）是不可行的.

步6 若V（EP）k≥ε，计算τk＝max｛λ：H（θ1k＋λ（θ2k－θ1k））≤ρ－ε｝，令θk＝θ1k＋τk（θ2k－θ1k）.

（1）若q（θk）＞0，则θk为问题（FP）的满足p（θk）≤ρ－ε的一个新非孤立可行解：若q（θ1k）＜0，计算θ1k和θk连线与q（w）＝0的交点¯θk，重赋值¯θ←¯θk；否则，重赋值¯θ←θ1k，转步7.

（2）若q（θk）≤0，¯θ不变，转步7.

步7 将Θk分为两个矩形.令Qk＋1为Θk的矩形集合，Tk＋1＝T′k＼｛Θk｝，赋值k：＝k＋1，回步1.

3.3 算法收敛性

定理2 上述算法在有限步迭代后终止，或得到问题（FP）的ε-非孤立最优解，或证明问题（FP）是不可行的.

证明 若步3出现，即由Q′k＝∅知，不存在可行解θ使得p（θ）≤ρ－ε＝p（¯θ）－ε成立，故结论正确.若步5出现，即V（EP）k＜ε，则max（EP）＜ε，由定理1知结论成立.在步6中，由p（θ1k）≤ρ－ε，存在点θk满足p（θk）≤ρ－ε；若q（θk）＞0，则由定理1，θk是满足p（θk）≤p（¯θ）－ε的一个非孤立可行解，证明步（1）结论成立.故下列情形之一出现，结论成立：Q′k＝φ，V（EP）k＜ε，q（θk）＞0.其余步骤显示，对充分大的k，或步3或步5的情形发生，假设算法迭代是无限的.由于步6（1）每出现一次，当前最好的目标函数值至少下降ε（ε＞0），而p（θ）有下界，步6（1）不能无限发生.对充分大k，¯θ不变，且V（EP）k≥ε时，v

数值例子

全局最小值点x1＝0，x2＝0.332，y1＝0，y2＝－0.000 1.全局最小值为p0＝0.220 5，f＝0.

［1］ CHINCHULUUN A，PARDALOS P M，HUANG H X.Multilevel（hierarchical）optimization：complexity issues，optimality conditions，algorithms.in：advances in applied mathematics and global optimization in honor of gilbert strang［J］.Advances in Mechanics and Mathematics Series，2009，17：197-222.

［2］ CAO D，CHEN M.Capacitated plant selection in a decentralized manufacturing environment：a bilevel optimization approach［J］.Eur J Oper Res，2006，169（1）：97-110.

［3］ TUY H，MIGDALAS A，HOAI-PHUONG N T.A novel appraoach to Bilevel nonlinear programming［J］.J Glob Optim，2007，38（4）：527-554.

［4］ TUY H，HOAI-PHUONG N T.A robust algorithm for quadratic optimization under quadratic constraints［J］.J Glob Optim，2007，37（4）：557-569.

［5］ NUNO P F，KONSTANTINOS I K，EFSTRATIOS N P.A multi-parametric programming approach for constrained dynamic programming problems［J］.Optimization Letters，2008，2（2）：267-280.

［6］ NUNO P F，PEDRO M S，EFSTRATIOS N P.A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems［J］.CMS，2009，6（4）：377-397.

［7］ KÖPPE M，QUEYRANNE M，RYANPARAMETRIC C T.Integer programming algorithm for bilevel mixed integer programs［J］.J Optim Theory Appl，2010，146（1）：137-150.

［8］ DEMPE S，MORDUKHOVICH B S，ZEMKOHO A B.Necessary optimality conditions in pessimistic bilevel programming［J］.Optimization，2014，63（4）：505-533.

［9］ VICENTE L.Bilevel programming［D］.Coimbra：Department of Mathematics，University of Coimbra，1992.

［10］ DUA V，BOZINIS A，PISTIKOPOULOS E N.A multiparametric programming approach for mixed-integer quadratic engineering problems［J］.Comput Chem Eng，2002，26：715-733.

Parametric global optimization for polynomial bilevel programming

XU Jun-yan，MIAO Zhuang，LIU Qing-huai
（School of Basic Science，Changchun University of Technology，Changchun 130012，China）

A parametric global optimization algorithm is proposed for solving polynomial bilevel programming problem in this paper.We first describe how we can recast and solve the follower's problem of the bileve fomulation as a multi-parametric programming problem，with parameters being the variables of the leader's problem.By inserting the obtained reasonable response sets in the leader' problem the overall problem is transformed into a set of independent polynomial programming problem.Convergence of the algorithm is established and numerical results are given to show the feasibility.

global optimization；polynomial bilevel programming；nonisolated optimal solution

O 224 ［学科代码］ 110·7480

A

（责任编辑：陶 理）

1000-1832（2015）03-0005-04

10.16163／j.cnki.22-1123／n.2015.03.002

2013-12-29

国家自然科学基金资助项目（10771020）；吉林省自然科学基金资助项目（20101597）.

徐俊彦（1964—），女，硕士，副教授，主要从事最优化理论与算法研究；通讯作者：刘庆怀（1961—），男，博士，教授，主要从事最优化理论与算法研究.