Algorithmic Studies On Continuous And Discrete Monotone Optimization And Indefinite Quadratic Programming

Global optimization aims to find the global optimal solution of a nonconvex optimization problem. With the progress of the modern society and the development of science and technology, global optimization plays an important role in many fields, such as production planning and management, financial engineering, engineering design and control, traffic transportation, agricultural forecast, national defence and so on. The significance of the algorithmic studies on global optimization is therefore evident.In this thesis, two classes of global optimization problems with special structures are studied: monotone optimization problem and indefinite quadratic programming problem. Monotone optimization deals with the problems of optimizing a monotone function subject to monotone constraints. Discrete monotone optimization problem is a monotone optimization problem with all variables restricted to integers. Such problems are also referred to as multi-dimensional nonseparable knapsack problems. The objective function and the constraint functions of a monotone optimization problem are not necessarily convex or separable. Indefinite quadratic programming deals with the problems of optimizing an indefinite quadratic function subject to linear constraints or quadratic constraints. Indefinite quadratic integer (discrete) programming is an indefinite quadratic programming with all variables restricted to integers. In this thesis, we focus on continuous and discrete indefinite quadratic programming with linear constraints.This thesis consists of seven chapters. In Chapter 1, monotone optimization problem, indefinite quadratic programming problem and their discrete versions are formally described. Several examples of applications of continuous and discrete monotone optimization and indefinite quadratic programming are presented. Finally, the main contributions of the thesis are briefly introduced in this chapter. In Chapter 2, some basic solution algorithms for general global optimization problems are first introduced. We then give literature survey of algorithms for continuous and discrete monotone optimization problems and indefinite quadratic programming problems.In Chapter 3, a new exact method for monotone optimization problems is proposed. The method is of branch-and-bound framework that combines three basic strategies: partition, convexification and local search. The partition scheme is used to construct a union of subboxes that covers the boundary of the feasible region. The convexification outer approximation is then applied to each subbox to obtain an upper bound of the objective function on the subbox. The performance of the method can be further improved by incorporating the method with local search procedure. The numerical results show the feasibility and effectiveness of the proposed algorithm, and the algorithm can solve medium size monotone optimization problems in reasonable time.In Chapter 4, we study discrete monotone optimization. A discrete polyblock algorithm is first proposed. The polyblock algorithm is then incorporated with convexification method to improve the efficiency of the algorithm. Numerical results show that the two algorithms are effective for discrete monotone optimization problems and the comparison results indicate that the improved algorithm outperforms the discrete polyblock algorithm for the problems with large domain region.In Chapter 5, we present a new algorithm for finding global solution of indefinite quadratic programming problems. Three lower bounding techniques, linear approximation, Lagrangian dual relaxation and convex relaxation, are derived. A branch-and-bound algorithm based on these lower bounding techniques and rectangular bisection is established. We also show that the convex relaxation of transformed separable indefinite quadratic problem by orthogonal transformation is equivalent to the Lagrangian dual relaxation. Preliminary computational results indicate the effectiveness of the proposed algorithm. In Chapter 6, several new lower bounds are derived for indefinite quadratic integer programming problems and their relations are established. We first construct convex relaxations by D. C. decomposition and linear underestimation. Cholesky factorization is used to reduce the original problem into the separable problems. Two Lagrangian bounds are then derived by applying dual decomposition schemes to the separable reformulations. Relationships between the convex relaxation bounds and Lagrangian bounds are also established. These underestimation methods are applicable to the algorithms for (continuous) indefinite quadratic programming problems.Finally, we conclude the thesis in Chapter 7 by summarizing the main results and discussing some possible future research directions.