Study On Hybrid Algorithm For Bilevel Quadratic Programming Problem

Along with the development of human society and the aggravation of economic globalization,many practical decision problems are completed by many decision-makers,and these decision-makers not only have the relationship of independence,but also interrelationship,so the hierarchy of decision problem becomes more and more obvious.For this sake,multilevel programming has caught people's attentions.For the research of the multilevel programming,up to now,there are many significative results.Bilevel programming is the simplest one of multilevel programming. At present time,there are many research methods for bilevel linear programming, and they take good outcome,but the current situation of bilevel nonlinear programming research isn't perfect. The essence of the bilevel programming problem ,which is nonconvexity and nondifferentiability,already makes it difficult to solute the bilevel linear programming problem,so it will be more difficult to solute the bilevel nonlinear programming problem.On the other hand,many difficult nonlinear programming usually can be solved by Sequential Quadratic Programming Method.Bilevel Quadratic Programming(BQP) is the simplest one of the bilevel nonliear programming.For the past few years,people have gotten many good acheievements in the Interior Point Algorithm(IPA) research,which be used in quadratic programming,and especially, when variable has large demension, the IPA will show its advantage.At the same time,Genetic Algorithm(GA) has been used in many subjects and fields,the property of the GA,which is simple,universal, parallelism and robustness,make it show large advantage when solving difficult and complicated practical problem.Hence,the IPA and the GA will be combinated perfectly and be used to solve BQP in this thesis.This theisi has four charpers to be discussed.Charper 1 is exordium,in this charper,generating background and current research situation of bilevel programming,quad ratic programming,the GA and the IPA are introduced,and then the research subject of this thesis—BQP is introduced into.In charper 2,the basic knowledge,theories and properties of the BQP,the GA and the IPA are introduced.In charper 3,we improve the GA and the IPA,then combinate them to be a new hybrid algorithm to solve the BQP,at the same time, we proof the global convergence of the new hybrid algorithm, then we give some examples to illustrate the validity and the advantage of this new hybrid algorithm.The last charper is the summary and the outlook of this thesis.