Solving The Quadratic Programming Problem With Box Constraints

This paper consists of two parts. In the first part, a new branch and bound algorithm for minimizing the nonconvex quadratic programming with box constraints is proposed. The convergent property of the algorithm is also proved. The bound is decided by using rectangular partition and ellipsoidal technique. The d.c. (diffence of convex functions) optimization algorithm, called DCA is applied to minimize a quadratic form over a ball which is the subproblem of the original problem. The numerical results show that this algorithm is efficient. In the second part, a decomposition method for solving semidefmite quadratic programming with box constraints is proposed. A regular splitting of the Hessian matrix of the problem is used in the algorithm. The convergence of the algorithm is proved under certain assumptions, the numerical results are also given.