【作者】 李和成；

【导师】 王宇平；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2009， 博士

【摘要】 双层规划问题是一类具有递阶结构的非凸优化问题。目前,对于这类问题的讨论往往局限于线性情形、上下层函数均凸可微等,对于含不可微非凸函数的双层规划问题,存在的有效算法极少。本文针对几类非线性双层规划问题,利用问题的特点设计了相应的遗传算法,并证明了算法的收敛性。提出的大部分算法突破了基于梯度的传统优化方法对函数可微性和凸性的限制;另外,为了提高遗传算法的效率,利用单纯形法、指数分布等设计了一些新的遗传算子。主要工作包括如下几个方面:1.对于下层问题为线性规划的情形,本文讨论了上层问题为凸可微规划和上层函数非凸不可微两种情况。首先,对于上层凸可微的问题,利用下层基进行个体编码,并运用最优性条件,将问题转化为一个单层规划,以该单层规划的最优值作为相应个体的适应度值。该算法的优点是适合求解大规模问题。其次,针对上层函数非凸不可微的问题,基于下层规划的对偶问题及对偶定理,将上层变量的取值域进行剖分,使得每一个剖分区域内的所有点对应同一个下层最优解表达式。而对上层采用遗传算法求解,并基于单纯形法设计了新的杂交算子。算法的优势是对每一个上层变量值,无需求解下层问题即可得到下层最优解,因而提高了算法的效率。2.讨论了下层为凸二次规划和一般凸规划,而上层含非凸不可微函数的两个问题,分别提出了求解这两类问题的遗传算法。首先利用下层凸规划的K-K-T条件,将问题转化为一个等价的单层规划;其次为了提高种群个体的可行性,对下层为凸二次规划的情形,利用Lemke算法获得下层最优解;对于下层为一般凸规划的情形,给出了新的约束处理方法,它能将种群中的不可行点转化为约束域内的点,且给出了一个判断个体是否满足下层最优性的方法。3.研究了三类下层含非凸函数的双层规划问题,包括下层函数可分、下层目标为一类非凸复合函数和下层函数为广义凹函数三种情形。首先针对下层问题特点,分别给出了下层求解方法。对下层可分的情形,将问题分为单变量函数的极值问题求解;对于第二类问题,利用下层目标函数,将问题分解为多个凸规划,通过求解其中两个而获得最优解;对于第三类问题,利用凹规划的最优解能在极点上达到的性质求解。其次利用种群最好个体设计了新的杂交算子,并用遗传算法求解上层问题。4.针对下层问题可解的非线性双层规划问题,提出了一个基于插值的遗传算法。该算法的特点是利用插值函数估计下层最优解函数,以插值函数的值近似下层最优解。这省去了大量求解下层问题的过程,能有效节约计算量。5.研究了下层函数关于整数变量可分、下层松弛问题为凸规划和下层函数关于整数变量为多项式的混合整数双层规划问题。首先给出了各类下层问题的解法,对于下层可分的问题,利用目标函数的凸凹性分解求解;对于下层松弛问题为凸规划的问题,利用凸函数的性质,给出了一种简化的分支定界法;对于第三类问题,利用连续化技术给出了同解的线性规划问题。其次利用遗传算法求解上层问题,并设计了一个基于指数分布的杂交算子。6.对提出的算法,进行了收敛性分析。更多还原

【Abstract】 Bilevel programming problems (BLPPs) are nonconvex optimization problems with hierarchial structure. The vast majority of the existing research works on BLPPs is concentrated on linear BLPPs and some special nonlinear BLPPs in which all of the functions involved are convex and twice differentiable. Few works are concentrated on the BLPPs involving nondifferential and nonconvex functions. In this dissertation, based on the characteristics of problems involved, GAs are proposed for solving several classes of nonlinear BLPPs, and the convergence of these algorithms is verified. Unlike the optimization technologies based on gradients, most of these proposed GAs do not require the convexity and differentiability on the leader’s function. Furthermore, based on the simplex method and the exponential distribution, new crossover operators are designed to improve the efficiency of GAs. The main contributions of this thesis are as follows:1. For BLPPs in which the follower’s problems are linear, two classes of problems are studied. One is that the leader’s problem is convex and differentiable, whereas the other is that the leader’s problem is nonconvex and nondifferentiable. For the first class of problems, the different bases of the follower’s problems are applied to encode individuals in the population, and the optimality conditions are applied to transform the BLPP into a single level programming where the optimal value is taken as the fitness. The advantage of designing GA in this way is that the large scale BLPPs can be solved efficiently. For BLPPs with nonconvex and nondifferentiable functions, based on the dual programming of the follower’s problem and the dual theorem, the region of the leader’s variables is divided into several subregions, such that for all values of leader’s variables in each subregion, the follower’s problem has the same solution expression. Furthermore, GA is used to solve the leader’s problems, in which a new crossover operator is designed based on the simplex method. An advantage of the proposed GA is the optimal solutions to the follower’s problem can be obtained very easily without solving the follower’s problem. As a result, the efficiency of GA is greatly improved.2. Two classes of BLPPs are studied, one is that the follower’s problem is convex quadratic, while the other is that the follower’s functions are convex. Also, in the two classes of BLPPs the leader’s problems involve nonconvex and nondifferentiable functions. GAs are proposed for solving the two classes of problems, respectively, and the K-K-T conditions are applied to transform the original BLPPs into single level programming. Furthermore, in order to improve the feasibility of individuals in populations, some special techniques are adopted. For the first class of BLPPs, Lemke algorithm is used to obtain the follower’ solutions; for the second one, a new constraint-handling scheme is given which can make infeasible points satisfy all equality and inequality constraints. Also, a method which can judge whether an individual is a solution of follower’s problem is presented.3. Three classes of BLPPs with nonconvex follower’s functions are studied. In the first one the follower’s functions are separable with respect to follower’s variables. In the second one the follower’s objective is a special compound function. In the last one the follower’s problem is generalized concave. First, for these three classes of BLPPs, the solution methods to the follower’s programming are presented. For the first class, the follower’s solutions are obtained by decomposing the follower’s programming into univariate optimization problem. For the second one, based on the characteristics of the follower’s objective, the follower’s programming is decomposed into several convex programming, and the optimal solutions can be obtained by solving at most two of these convex programming problems. Note that the solutions to a concave programming can be obtained at one of extreme points of the feasible region, the follower’s problem of the last class can be solved by comparing the objective values at all extreme points. To solve the leader’s problem, GAs are adopted and the best individuals are used to design new crossover operators.4. For the nonlinear BLPPs in which the follower’s problems can be solved, an interpolation-based GA is proposed. The solution function of the follower’s programming is approximated by its interpolating function, that is, the solutions to follower’s programming can be approximately obtained by the interpolation. It avoids solving a large number of the follower’s programming, as a result, the amount of computation is greatly decreased.5. Three classes of mixed-integer nonlinear bilevel programming problems are studied. In the first one, the follower’s function is separable with respect to the follower’s integral variables. In the second one, the follower’s function is convex if the follower’s variables are not restricted to integers. In the last one, the follower’s function is polynomial with respect to integer variables. First, the solution methods are given for each follower’s programming mentioned above, respectively. For the first one, the follower’s problem is solved by making use of the convexity or concavity of the objective function. According to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower’s programming for the second class of problems. For the last one, a continuity technique is used to transform the follower’s mixed-integer problem into a linear programming(LP). Then, based on the exponential distribution, a new crossover operator is designed, and GAs are proposed for solving these three classes of BLPPs, respectively.6. For all of the proposed algorithms, the convergence is analyzed.更多还原