Global Optimization Methods For Solving Several Classes Of Nonconvex Programming Problems

Global optimization method is an important branch of the larger difficulty in the optimization field, whose theory and algorithm are not perfect. It is well known that nonconvex program-ming problems possess generally multiple local optima that are not globally optima, so that the classes of problems are very difficult to be solved. Nonconvex programming problems have a broad applications in engineering optimization design, economic and trade balance, investment and combination optimization, and so on. In the past decades, many domestic and foreign scholars proposed some algorithms for globally solving some special nonconvex programming problems. For example:in allusion to quadratic programming, linear fractional programming etc. problems, some algorithms have been given in the literatures. Based on these known algorithms, this paper will construct the tighter relaxation problem, and by combining the branch and bound algorithm framework and the range reduction technique, some more efficient global optimization algorithms are established for solving several classes of nonconvex programming problems. The main contents are given as follows.1. In allusion to the nonconvex quadratic programming problem, a parametric linear relaxation method is presented. By utilizing the characteristics of quadratic function, a new parametric linear relaxation technique is constructed, based on this technique the nonconvex quadratic programming problem are converted into a parametric linear relaxation programming problem. To improve the convergent speed of the algorithm, a range reduction technique is integrated into the branch and bound framework for developing the proposed algorithm. The convergence of the algorithm is proved, and numerical experimental results show that the proposed algorithm has the higher computational efficiency.2. Consider the generalized linear multiplicative programming problem, by using e-quivalent transformation, linear relaxation bounding technique, successive partition of the outer space region, and solutions of a series of linear relaxation programming problems, we present an outer space branch and bound algorithm. The proposed outer space branch and bound algorithm is convergent to the global optimal solution of the original problems, the numerical experimental results shows the efficiency of the proposed algorithm.3. In allusion to the sum of linear ratios problem, an outcome space branch and bound algorithm with accelerating technique is proposed. By converting the original problem into an equivalent bilinear programming problem, then use the convex envelope approximation and concave envelope approximation of bilinear function, thus the equivalent problem be converted into a series of linear relaxation programming problems. To improve the efficiency of the algorithm, an outcome space regional deleting rules are obtained by utilizing the special structure of the equivalent problem and algorithm characteristic. Global convergence of the proposed algorithm is proved and the numerical results indicate the effectiveness and robustness of the proposed algorithm.4. In allusion to the quadratically constrained sum of quadratic ratios problem, we propose a branch-reduction-bound algorithm. By utilizing the special structure of quadratic function, the linear lower bounding function of the numerator and the linear upper bounding function of the denominator for each ratio can be constructed, then the quadratically constrained sum of quadratic ratios problem can be converted into a sum of linear ratios problem, at the same time, a linear relaxation programming of the sum of linear ratios problem is constructed, by combining the branch and bound framework and the regional reduction technique, an effective and convergent algorithm is established, and the numerical experimental results are given to demonstrate the feasibility of the proposed algorithm.5. For the two different forms of the generalized polynomial problem, first of all, by introducing new variables and constraints, an equivalent generalized geometric programming problem is established, by utilizing the new linearizing technique, a linear lower bound relaxation problem is constructed for the equivalent problem, then we present a branch and bound algorithm for generalized polynomial problem with polynomial constraints; secondly, using the equivalent transformation and linear approximation of exponential function and logarithm function, a new two-level linear relaxation technique is proposed. Combining branch and bound method and range reduction technique, we propose a global optimization algorithm for the general form of the generalized polynomial problem.