Global Optimality Conditions And Global Optimization Algorithms For Quadratic 0-1 Problems

During the past several decades, many new theoretical, algorithmic and computational contributions have helped to solve globally multiextreme problems arising from important practical applications. In this thesis, we emphasize nonconvex optimization problems presenting some specific structures like quadratic 0-1 programming problems first. We obtain global optimality conditions of these problems and discuss the algorithms for solving these problems. Then, we consider a new filled function method with parameter free for solving general global optimization problems.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. But tackling them from the global optimality and duality viewpoints is not as yet at hand.In the first chapter of this thesis, we introduce the recent developments in global optimization. The global optimality conditions of quadratic 0-1 programming problems are discussed in chapter two. First we obtain a necessary and sufficient condition for a feasible point to be a global maximizer of a convex quadratic function under linear constraints. Through this work, we find explicit global optimality conditions of quadratic 0-1 programming problems, including sufficient and necessary conditions and some necessary conditions. These works are presented in section three and four. In section five of chapter two, we focus on the necessary conditions of quadratic 0-1 problems. All the necessary conditions we got are expressed only with the primal problems' data in a simple way and without dual variables. That makes the necessary conditions can be checked in practical applications. Furthermore, we reduce the dimensions in our global optimality conditions. Some necessary conditions expressed here are given with lower dimensions than the primal problem and can be used easily.In chapter three, we consider quadratic 0-1 problems with linear constraints. In section one, we establish global optimality conditions for quadratic 0-1 problems with inequality constrains, including sufficient conditions and a necessary condition. The necessary condition is expressed without dual variables. We also study the relations between the global optimal solutions of nonconvex 0-1 quadratic problems versus the associated relaxed and convex problems. Section two gives the relations between the global optimal solutions of quadratic 0-1 problems with linear equality constraints and the global solutions of quadratic 0-1 problems. The set of the global optimal solutions of these two class of problems are the same. Some applications of quadratic 0-1 problems are discussed in section three of chapter three. We discuss...