Computing Two Classes Of Quadratic Constraint Quadratic Optimization Problems By SDP Relaxation

Quadratic constraint quadratic optimization problem (QCQP) has widely applications in practice, such as, trust region sub-problem in nonlinear optimization, least square variation problem, signal processing problem and so on. However, it is a NP-hard problem, and there is not good method to deal with it. In this paper, we study efficient rank-one decomposition algorithm for general QCQP on the basic work of Strum and Zhang using SDP relaxation.This thesis mainly consists of the following work:Firstly, we give a QCQP example with a negative eigenvalue, show the general problem is not convex and more complex than convex case.Secondly, we consider a special class of QCQP which has only one quadratic constraint. We present a simple and practical matrix rank-one decomposition algorithm to obtain an optimal solution or approximate optimal solution for the primal problem, furthermore, we realized the algorithm by SEDUMI. Theoretical analysis shows that the method is correct and efficient, the preliminary numerical results also shows the efficiency of our method.Thirdly, we apply the above algorithm to QCQP with two quadratic constraints (usually named as two-ball problem). The preliminary numerical results show that the method is not efficient for two-ball problem, there exists dual gap sometimes, so two-ball problem is still an open issue.Finally, we study a special two-ball problem with one quadratic constraint and one linear constraint. We proposed a simple and practical matrix rank-one decomposition algorithm, and realized the algorithm by SEDUMI. Theoretical analysis shows that the decomposition method is correct and efficient, but the preliminary numerical experiment doesn't coincide with the theory result. Aim this contradiction, we give a reasonable explanation by deeply analysis, the numerical experiment also testify the efficiency of our method.