The Algorithms Reaearch Of Some Non-Convex Quadratic Optimization Problems With Quadratic Constraints

Quadratic optimization problems play a significant role in theory of mathematical programming. With the progress of the modern society and the development of science and technology, quadratic optimization are used in many fileds, such as production planning and management, financial engineering, telecommunications system, speech recognition and so on. So the research on quadratic optimization is evident.In this dissertation, we mainly discuss non-convex quadratic optimization problems with quadratic constraints. The main contents are list as follows:(l)Give a different proof for the sufficient and necessary condition that is used determining whether non-convex quadratic problem with two quadratic constraints have the optimal solution letting the Hessian matrix of lagrangian function is positive definite proposed by Ai and Zhang. This new proof based on only traditional mathematical analysis. Moreover, it is simpler and more understandable. Then by this condition and primal proof, we present an epsilon algorithm, which can solve the extended CDT subproblem for general symmetric matrix Qo and semi-positive definite matrix Q2·If H is semi-positive definite at the global solution, our algorithm can find the solution and the error is no more thanO(ξ).Otherwise, it will obtain a approximation solution and the error is no more than ((?))·We also show its effectiveness by numerical experiments. Finally, we propose an algorithm for general symmetric matrixes Q0 and Q2·Take the second constraints as a part of objective function, then we obtain the optimal solution by solving the one ball problem with variable and using bisection method. Numerical results show that this algorithm is also indeed efficient.(2)We design an algorithm based on SDP to solve distance calculation prolem in overlapped frequency division multiplexing communication system. If the distance between two different signals is bigger than the distance when quadrature amplitude modulation is used, then this system has ability of correcting error. Therefore, calculating the distance between two different signals is necessary. First, we construct the distance calculation model, which is non-convex combinatorial optimization problem with a quadratic constraint and its decision variable value is{-2,0,2}. Second, we design a randomized rounding algorithm for this problem. This algorithm can produce an optimal solution of semi-deinite relaxation model and then get the integral solution by the rounding technique. In order to test the performance of the algorithm, numerical tests have done when S is random semi-positive definite matrix and S is matrix generated by OVFDM system. All the results show that the algorithm is indeed efficient. The solution achieved by the algorithm is equal or close to the optimum solution.(3)We also design two different algorithms to solve 3D acoustic source localization problem based on time difference of arrival (TDOA). This problem is a quadratic fraction optimition problem with quadratic constraints. We design two algorithms to solve it. The first one is LCTLS-SDP algorithm, which is base on SDP method, and the other is LCTLS-ROD algorithm, which is base on the matrix rank-one decomposition method. LCTLS-SDP algorithm is to transform the quadratic fraction model into two non-convex homogeneous quadratic problems with quadratic constaints, and then by the dual theory and SDP method we get the optimal solution of problem. When the problem can be solved, we establish the convergent theorem for the algorithm and show its effectiveness by numerical experiments. LCTLS-ROD algorithm is to transform the quadratic fraction model into a non-convex homogeneous quadratic problem with quadratic constaints. Then it solves the semi-deinite relaxation model and obtains an optimal solution of our problem by rank-one decomposition of semi-deinite relaxation model's solution. Numerical results show that the algorithm is indeed efficient.