Convex Relaxation Of Quadratically Constrained Quadratic Programming Without Dimension Lifting

Quadratically constrained quadratic programming problem can represent a series of discrete and continuous optimization problems, such as the max-cut problem, maximum clique problem, 0-1quadratic knapsack problem which belong to combinational optimization. The classic linear programming problem is also a kind of QCQP problems, so is the Markowitz mean-variance model in the field of financial investment. Therefore, QCQP problems have important theoretical and application value. When the objective function and constraint functions of QCQP problem are all convex, it can be solved in polynomial time with the interior-point algorithm. However, in general, the QCQP problem is proved to bean NP-hard problem. Currently, there are several popular research areas on QCQP problem. However, these areas mainly focus on the relaxation and evaluating the bounds, judgment of the optimal solution and finding some kind of the QCQP problem which can be solved in polynomial time and designing the global optimal searching algorithms. The main work of this thesis is to solve the nonconvex QCQP problem using a branch-and-bound algorithm without dimension lifting, and then obtains an approximate optimal solution of the original problem.In general,the theories of semidefinite programming and Lagrangian duality are two of the most important tools used to solve the QCQP problem. In addition, reformulation linearization technical(RLT) is applied to improve the SDP relaxation. In general, the effect of combination of the two is better than singly using SDP relaxation or RLT inequality. Firstly, this thesis presents a basic introduction of the research background, significance and traditional methods on solving QCQP problems. Secondly, we study nonconvex QCQP problems with convex constraints, and provide a branch-and-bound algorithm for solving such QCQP problems without dimension lifting. Then, theoretical convergence property and worst-case complexity of the proposed algorithm are provided. We also compare the numerical performances of the proposed algorithm with the branch-and-bound algorithm based on the SDP relaxations on random examples. Numerical results show that the proposed algorithm is very efficient on certain types of quadratic programming problems. Thirdly, this thesis studies the general QCQP problems with box constraints. Besides, the branch-and-bound algorithm is designed and theoretical convergence property and worst-case complexity of the proposed algorithm are also provided. Finally numerical experiments are presented to compare the performance of the proposed algorithm with SDP relaxation algorithm.The contributions and novelties of the dissertation are summarized as follows.(1) We provide a method to relax the original problem without dimension lifting by using straight lines instead of nonconvex quadratic functions. Next, we designthe corresponding branch-and-bound algorithm to search the global optimal solution of the original problem.(2) Theoretical convergence property and worst-case complexity of the proposed algorithmare provided. Numerical results of the proposed algorithm and the branch-and-bound algorithm based on the SDP relaxations and Baron are show-ed and compared.