Branch-and-Bound Algorithms Of Nonconvex Programming Problems

For several types of nonconvex programming problems, several global optimization algorithms based on branch-and-bound are proposed, and conducted convergence analysis, and numerical results are given. This thesis is divided into four parts, the main contents are as follows:At first, for a class of non-negative integer quadratic programming problems, a new branch-and-bound reduced method is proposed. In this method, a new rectangular two-partitioned technique and a new linear programming relaxation bounded technique are used. At the same time, to improve the degree of approximation and the convergence rate of acceleration, a rectangular reduction strategy is used.Next, nonconvex quadratic programming problem is researched, a new linear progra- mming relaxation branch and bound algorithm with a reduction is proposed and converge- nce is proved. In this algorithm, a new hyper-rectangle partition technique and a new linear programming relaxation are used, at the same time in order to improve the extent approach and speed the convergence, the hyper-rectangular reduction is used.Furthermore, a class of quadratic programming with quadratic constraints of the bran- ch-and-bound algorithm for the problem to be studied and the reduction course of the branch above, a new linear relaxation method has been constructed.Finally, a class of multi-product programming problems is equivalently converted into a concave minimum problem by using the properties of logarithmic function. For the concave-sum special structures and with that property that the convex envelope of concave function is linear on simplex, a linear programming relaxation problem is given to determi- ne the lower bound of the global optimal value of the original problem. Thus we propose a simplex branch and bound method for solving a class of multi-product problems and gives the convergence proof of the proposed method. Numerical examples show that the propos- ed method is feasible and effective.