Constraint Shifting Combined Homotopy Method For Bilevel Programming Problems

In 1984, Karmarkar presented a new method called interior-point method for solvinglinear programming, which was proved a polynomial algorithm, and its efficiency is higherthan simplex method in practical application. Since the publication of Karmarkar's paper,interior-point method becomes a hot topic for research. But boundedness of solution anduniform convexity are needed for interior-point method, therefor, Feng Guochen, Yu Boand Lin Zhenghua proposed the combined homotopy interior-point method using Newtonhomotopy and fixed point homotopy, and proved the existence and convergence of thehomotopy path under the certain condition. And this method needs a feasible interior-point as the initial point. Recently, Yu Bo and Shang Yufeng proposed the ConstraintShifting Combined Homotopy Method, which didn't have the constraint that the initialpoint must be in the feasible region and can solve more general nonconvex programmingproblems also. Generaly speaking, it is difficult to solve bilevel programming problems.The main reasons are as follows Firstly, it is a kind of NP-hard poblem; Secondly, thenonconvexity makes the computation of solution more difficult. In this thesis, we proposedthe Constraint Shifting Combined Homotopy Method, which didn't have the constraintthat the initial point must in the feasible region and can solve more general nonconvexprogramming problems also. Existence and convergence of the homotopy path are proved.