Global Optimization Algorithms For Fractional Programming Problems

Global optimization is concerned with the characterization and computation of global minima or maxima of nonlinear functions. Global optimization problems are widespread in mathematical modeling of real world systems for a very broad range of applications. Such applications include economies of scale, fixed charges, allocation and location problems, quadratic assignment and a number of other combinatorial optimization problems. Fur-thermore, the more comprehensive the considered class of global optimization problems, the smaller the tractable scale of problems. Active research during the past two decades has produced a variety of methods for finding constrained global solutions to nonlinear optimization problems.This paper respectively proposes the branch-and-bound algorithm for solving a linear sum-of-ratios fractional programming problem and a quadratic sum-of-ratios fractional programming problem and gives the convergence of this algorithm.The main contents of this paper are as follows:In Chapter1, several main global optimization approaches and the latest research de-velopment of problems studied in this paper are simply presented, and a brief introduction is given to related concepts of complexity and our work.In Chapter2, a global optimal algorithm is presented for globally solving a linear sum-of-ratios fractional programming problem. By introducing new variables, we trans-form the primal problem into a equivalent monotonic optimal problem whose objective function is only a single variable and constraint functions are the difference of two increas-ing functions. According to the characteristics of the equivalent problem, the algorithm starts from a feasible solution to find the global optimal solution of this initial problem. The convergence of the algorithm is proved theoretically, and the numerical examples show that the algorithm is feasible and valid.In Chapter3, firstly, the general form of quadratic sum-of-ratios fractional program-ming problem is transformed into a equivalent monotonic optimal problem. Then according to the equivalent problem presents a global optimal algorithm for solving this initial prob-lem. At last, the convergence of the algorithm is proved, and the numerical examples show the feasibility and validity of the proposed algorithm.