Global Optimality Conditions And Optimization Methods For Quadratic Integer Programming Problems

Global optimization problems abound in economic modeling, finance, network and transportation, database, chip design, image processing, chemical engineering design and central, molecular biology and enviromental engineering. Quadratic optimization problems cover a large spectrum of situations. Many quadratic programming problems are NP-hard or NP-complete. They constitute an important part both in the field of local optimization and of global optimization. There are close connections between nonconvex quadratic optimization problems and combinatorial optimization. It is important to study these problems because such problems have many diverse applications. In this thesis, some special nonconvex quadratic programming problems are discussed, and some global optimality conditions for bivalent nonconvex quadratic programs with inequality constraints, quadratic integer problems and mixed quadratic integer programs are presented. At the same time, some new global optimization methods for quadratic integer programs or mixed quadratic integer programming problems are introduced.In the first chapter of this thesis, we introduce the recent developments in global optimization. The sufficient global optimality conditions of bivalent non-convex quadratic programming problems are discussed in chapter 2. In chapter 3, some global optimality conditions for quadratic integer programs are established including global sufficient conditions and global necessary conditions. And then we present a new local minimization method for quadratic integer program according to its necessary global optimality conditions. A new filled function with well properties is designed by using specialty of quadratic integer programs. Moreover, we introduce a global optimization method to find a global minimizer of quadratic integer problems by combining the local optimization method, filled function and the sufficient global optimality condition. Some numerical examples are also given to show that the proposed optimization methods are very efficient and stable. In chapter 4, we pay more attention to the global optimality conditions for mixed quadratic integer programming problems. We introduce a new definition of K-K-T point, and present some new local minimization methods and global optimization method for mixed quadratic integer programming problems. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.