New Algorithm For Solving Bilevel Programming Problem

The structure with upper and follower relationship is called hierarchy. All of the management systems have the character of hierarchy. For this sake, multilevel programming has caught people's attentions. There have been many important results for studying multilevel programming. As the basic model in multilevel programming—linear bilevel programming and quadratic bilevel programming problem, they have been become the hot point. Because the constraints of the LBP and BQP are linear functions, and the simple method is the most efficient method to solve linear programming. How to transform the LBP and BQP and solve them using the simple method is the aim of the thesis. Following this idea, the author proposes a Frank-Wolf method for solving the LBP and BQP and hope to get a new method for solving the two kinds of bilevel programming problem..The thesis is divided into five chapters: In chapter 1, we summarize the development, usage of the multilevel programming, difficult points and two different kinds of formulations of the bilevel programming problem; In chapter 2, we introduce the Frank-Wolf method and the convergence of this algorithm. In chapter 3, we discuss the linear bilevel programming, and put forward a revised Frank-Wolf method for solving the linear bilevel programming, In chapter 4, we introduce the quadratic bilevel programming problem, and give the Frank-Wolf method for solving the BQP. In chapter 5, the paper is concluded.