Research On The Algorithm Of Solving Two Kinds Of Half Vector Bilevel Programming Problems

With the development of human society and the intensification of economic globalization,many decision-making problems in actual problems have multiple levels,and decision-makers are also in different levels.This type of decision problem is called a hierarchical optimization problem,and multi-level programming is a powerful tool for describing hierarchical optimization problems.In multi-level programming,the bilevel(or two-level)programming problem is a type of structure that is relatively simple,but also a problem that is more widely studied.Bilevel programming,as the name implies,is a type of constraint that contains another sub-optimization problem,the hierarchical optimization problem.In bilevel programming problem,the upper-level decision-makers first give their own decisions;for a given upper-level decision variable,the lower-level decision-makers choose the most favorable decision for themselves,and then feedback to the upper-level.In this process of constant interaction,both parties finally get the "optimal solution".It is worth noting that the feasible region of the bilevel programming is non-convex,and it may be an unconnected region.Therefore,the bilevel programming is essentially a non-convex,non-differentiable optimization problem.Even for the simplest bilevel programming problem—the linear bilevel programming problem,the structure of the feasible region is more complicated.In fact,bilevel programming is an NP-difficult problem,and it is also NP-difficult to solve the local optimal solution of the bilevel programming problem in time.Although the structure of the two-level programming is more complicated,the solution is more difficult.However,because of its ability to describe the hierarchical relationship in actual problems more perfectly,the bilevel programming shows a broad application prospect.In fact,bilevel programming has been successfully applied to resource optimization,transportation network design,reservoir scheduling,water resource pricing,etc.At the same time,various bilevel programming models with practical background have spawned various solving algorithms.This paper will focus on a special class of bilevel programming problems,namelysemivectorial bilevel programming problems,that is,the lower-levleis a multi-objective optimization problem,the upper-lever is a scalar optimization problem.This type of problem can be seen as an extension of the general bileve programming problem.In this paper,we will focus on two kinds of semivectorial bilevel programming problem solving algorithms,and give relevant numerical experiments to verify the feasibility and effectiveness of the designed algorithm.The structure of the paper is as follows:The first chapter briefly introduces the relevant basic knowledge of the bilevel programming problem,including the mathematical model of the bilevel programming,the basic decision-making mechanism,etc.and summarizes the research background of the bilevel programming problem from the two aspects of solving algorithms and practical applications.And development status.In the overview of the solving algorithm,it briefly introduces several commonly used solving methods for bilevel programming problems.It mainly includes penalty function method,pole search method,intelligent solution algorithm,branch and bound method,etc.At the same time,the solution ideas,advantages and disadvantages of the above algorithm are briefly summarized.In terms of practical application,the application of the bilevel programming problem in resource optimization allocation,transportation network design,reservoir dispatch management,etc.is introduced.Finally,the specific arrangements of the subsequent chapters of this article are introduced.The second chapter gives the relevant preliminary knowledge closely related to this article.The specific contents include: closed sets,convex sets,continuous functions,differentiable functions,local minimum(maximum)value points and other mathematical concepts;The mathematical model of linear and nonlinear bilevel programming problem and the basic properties of its solutions;the mathematical model of multi-objective optimization problems,optimality conditions and related solving algorithms.Provide the theoretical and algorithmic basis for solving the two types of semivectorial bilevel programming problems in the third and fourth chapters.Chapter 3 designs the pole search algorithm.The first section gives the mathematical model of the linear semivectorial bilevel programming problem,the concept of related optimal solutions,and gives a brief description of the relevant variables in the model.In the second section,based on the assumption that the constraint region is not empty,using the Karush-Kuhn-Tucker(KKT)optimality condition to replace the lower-lever problem,and the considered linear bilevel programming problem is converted into a single-level programming problem.Then,using the structural characteristics of the feasible region of the single-level optimization problem,a pole search algorithm that can obtain the optimal solution of the original linear two-level programming problem is designed.At the same time,the related numerical experiments verify the feasibility and effectiveness of the algorithm.Section 4 briefly analyzes the advantages and disadvantages of the designed pole search algorithm.Chapter 4 studies a class of nonlinear semivectorial bilevel programming problems,that is,the upper level is quadratic programming and the lower level is a linear multi-objective optimization algorithm.Firstly,the linear weighted scalar quantization method is used to transform this type of nonlinear semivectorial bilevel programming problem into a general bilevel single-objective optimization problem.Then using the K-K-T optimality condition replaces the lower lever problem,and a class of single-lever programming problems with complementary constraints is obtained.In order to easily deal with the complementary constraint,it is added as a penalty term to the upper-lever objective function,and then the Frank-Wolf method is used to solve the penalty problem.At the same time,the relevant numerical results verify the feasibility and effectiveness of the algorithm.Finally,a summary of the content of this section.Chapter 5 summarizes the full text,especially looking forward to the possible future research contents of this paper.