| During the last decade, global optimization has attracted a lot of attention due to the increased practical need for obtaining global solutions and the success in solving many global optimization problems that were previously considered intractable. In general, the central question of global optimization is to find an optimal solution to a given problem such that no other better solution exists, or show that no feasible point exists to the given formulation. Unlike local optimization methods, global optimization methods must investigate the global optimality of a solution point, which unfortunately is difficult and beyond the reach of classic nonlinear programming methods. Therefore, global optimization is much more computationally expensive than standard nonlinear programming. One often successful response to this challenge is the branch-and-bound technique, which obtains information on global quality of the feasible solutions by computing lower and upper bounds for the possible global optimum on successively refined partitions of the search space. For a minimization problem, since the upper bounds can usually be obtained by effective heuristic methods, the key of many branch-and-bound based algorithms is to rely on tight relaxations for the problem so as to achieve tight lower bounds. A large number of nonlinear relaxation techniques have been developed for various classes of problems. However, nonlinear relaxations may not be solved as robustly and efficiently as their linear counterparts, given the mature linear programming technology. On the other hand, the common polyhedral relaxations used in the literature often lead to poor lower bounds.;This dissertation aims to improve polyhedral relaxations for efficient solution of difficult global optimization problems that are not easily solvable by current global optimization algorithms. To this end, the dissertation addresses the development of novel relaxations and cutting planes, their implementation in branch-and-bound algorithms, and the development of model preprocessing techniques that can facilitate the construction of polyhedral relaxations.;We start by considering the nonconvex, quadratically constrained quadratic program, which is important both practically and theoretically. Utilizing the convex envelopes of multilinear functions, we develop a polyhedral relaxation for this problem, along with a cutting plane algorithm for implementing this relaxation. In contrast to the classic termwise relaxation of bilinear functions, the proposed relaxations are multiterm, i.e. they are derived from the convex envelope of the sum of multiple bilinear terms of quadratic constraints, thereby providing tighter bounds. Even when embedded only at the root node of the branch-and-bound algorithm, the proposed cutting planes result in a dramatic improvement to the performance of a branch-and-bound algorithm due to their tightness.;We then extend our approach to multilinear functions for more general global optimization problems. Our implementation is the first practical global optimization system for general problems utilizing relaxations for multiple multilinear terms. The cutting plane generation algorithm is embedded at every node of the branch-and-bound search tree, supplemented with a customized simplex method for solving the separation problem, and a proper decomposition to manage the computational expense on the generation of cuts. The implementation with multiterm relaxations exhibits a 33% reduction in CPU time and a 70% reduction in the number of nodes for quadratically constrained quadratic programming problems in comparison to using only termwise relaxations.;Furthermore, we consider semidefinite relaxations for quadratically constrained quadratic programs. We perform a systematic investigation of the equivalence and dominance of different semidefinite relaxations, two of which are shown to be stronger than six other SDP relaxations but require three orders of magnitude more computational time than the weaker relaxations using state-of-art SDP solvers. In addition, we present a novel approach that solves an SDP in matrix space to provide cutting planes in the space of the original problem variables.;Finally, in a complementary line of work, we address model preprocessing to facilitate the construction of polyhedral relaxations for global optimization. We design and implement an automatic convexity detection algorithm to exploit the convexity properties of general nonlinear programming problems. |
