Global Algorithm For 0-1 Quadratic Program Based On SDP Relaxation

The 0-1 quadratic program is an important class of optimization problems in integer pro-gramming, which has a wide range of applications in many important fields, including engineer-ing, economics, finance, military and management science. It is an important and challenging re-search topic in international optimization fields. In recent years, the development of semidefinite programming (for short, SDP) methods motivates the investigation of 0-1 quadratic programs.This thesis investigates the SDP relaxation and global algorithm for 0-1 quadratic programs. We present a tight SDP relaxation based on the matrix decomposition scheme, and propose a branch-and-bound algorithm based on the SDP relaxation. The main contributions of the thesis are as follows:(1) We develop a tight SDP relaxation for 0-1 quadratic programs with linear constraints based on the matrix decomposition approach. We first obtain a convex relaxation of the original problem by employing matrix decomposition of the objective function and piecewise linear ap-proximation techniques of quadratic term. We then show that the problem of finding the optimal parameters in the convex relaxation can be reduced to an SDP problem. Numerical results show that the SDP relaxation can provide a tighter lower bound of the original problem.(2) We propose a new branch-and-bound algorithm based on the SDP relaxation for 0-1 quadratic programs with linear constraints and its convergence. First, We next present the relation between the optimal values to the original problem and the SDP relaxation problem. we then present a branch-and-bound algorithm based on the SDP relaxation and show that the algorithm converges in a finite number of iterations to a global optimal solution of the original problem. The preliminary numerical results shows that our proposed algorithm can find effectively the global optimal solution.