Branch-and-Bound Algorithm Of Fractional Programming And Nonconvex Quadratic Programming

In our life, many important issues are related to the selection of the best goal, or select some parameters and determine certain values in order to achieve the goal, these problems can be attributed to optimization problems. This thesis mainly studies the algorithms of solving fractional programming and non-convex quadratic programming problems. The thesis is divided into three parts, the basic contents as follows:Firstly, a new branch and bound algorithm is studied for sum of linear fractional programming problem. In this algorithm, equivalent transformation is used on the original problem, then utilize a new linear relaxation lower-bounding method, make the non-convex programming problem can be converted to a sequence of linear programming problems, i.e. obtain the lower bound of the optimal value of the original problem.Secondly, a branch and bound reduced method is studied for globally solving a class of non-convex quadratic programming problem with linear constraints. The equivalent problem can be obtained from the characteristics of a quadratic function, a linear relaxation programming of the equivalent problem can be constructed by using the concave envelopes and convex envelopes technique, i.e. obtain the lower bound of the optimal value of the original problem, the optimal solutions and the optimal value can be obtained by solving a sequence of linear relaxation programming problems, at the same time in order to improve the approximation of the algorithm and accelerate the convergence rate of the algorithm, the hyper-rectangular reduction technique is used.Finally, a branch and bound algorithm is studied for globally solving a class of non-convex quadratic programming problem with quadratic constraints. According to the characteristics of a quadratic function, the initial problem is equivalently transformed, then the linearizations of the objective function and constraint functions is given by using a new linear relaxation technique, i.e. obtain the lower bound of the optimal value of the original problem, the degree of approximation and the convergence rate are improved through a two deeper subdivision and hyper-rectangular reduction technique. Numerical experiments are reported to show that the proposed algorithm is feasible and effective.