Study On Efficient Algorithms For Global Optimization Of Quadratic Bilevel Programming Problem

This paper is devoted to efficient algorithms for global optimization of quadratic bilevel programming problem.As a breakthrough,starting with the linear bilevel programming problem, because it is the most simple form of all the bilevel programming problem,and the algorithm is extended to quadratic bilevel programming problems. In quadratic bilevel programming research,firstly, study on the convex quadratic bilevel programming problem,and then research on the more general case, and give the corresponding algorithms.Firstly,this paper introduces the general bilevel programming background, the general bilevel programming model, bilevel programming application and current research status of bilevel programming.For the linear bilevel programming problem(LBPP),this paper introduces the general mathematical model,the definition,the basic theory and some properties of of the bilevel programming problem.Study the complementarity problem and equivalent transformation of linear bilevel programming, According to the basic properties of linear bilevel programming,give an improved branch and bound algorithm for solving linear bilevel programming.For the nonlinear bilevel programming problem(NBLP), at present there are three main methods:branch and bound algorithm,descent method and penalty function method.Based on the model of nonlinear bilevel programming,this paper mainly introduces an improved branch and bound algorithm based on the former,the proposed algorithm is more effective than before. A nonisolated global optimal solution algorithm is proposed for solving quadratic bilevel programming problem in this paper. We first describe how we can recast and solve the follower’s problem of the bilevel formulation as a multiparametric programming problem, with parameters being the variables of the leader’s problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic programming problem. Most existing approximate methods for solving these problems may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a nonisolated global optimal solution algorithm is proposed for solving quadratic bilevel programming problem in this paper. Numerical results are presented to show the effectiveness of this method.