【作者】 向文；

【导师】 艾文宝；

【作者基本信息】 北京邮电大学 ， 管理科学与工程， 2010， 博士

【摘要】 二次优化问题在数学规划理论中占据重要地位。同时,随着社会的进步以及科学技术的发展,二次优化问题广泛应用于企业生产管理,金融工程,通信系统,语音识别等重要领域。因此,研究二次优化问题具有重要的意义。本文主要对三类带二次约束的非凸二次优化问题进行研究,主要工作如下：(1)本文给出了带两个二次约束的非凸二次优化问题在最优解处拉格朗日函数Hessian矩阵是否半正定的充要条件的一个新的证明方法。该证明方法主要利用分析的思想,以及利用对偶理论来证明,不需要了解半正定相关的知识。之后,利用这一充要条件以及之前的证明方法,我们给出了当Q0是一般的对称矩阵,Q2是半正定矩阵时的一个ζ近似算法,ζ为设定的计算精度。如果在全局解处,H半正定,则我们的算法可以准确地找到这个解,计算误差仅为0(ζ)；反之,算法可以找到一个近似最优解,其误差至多为其中μn-1为矩阵H的次大特征值。我们通过数值例子说明了算法的有效性。最后,当Q2是一般的对称矩阵时,我们设计了一个近似算法。首先将第二个约束作为罚项添加到目标函数中,之后通过求解带参数的一球问题并利用二分法的思想来求解。大量的数值结果显示,该算法是高效的。(2)针对非正交频分复用系统纠错过程中的距离计算模型,设计了一个基于SDP的近似算法。该系统可以纠错的条件是当两个不同发射序列之间的距离大于使用QAW调制时的距离。因而我们需要计算两个不同发射序列之间的距离。于是我们首先给出了该系统中的距离计算模型,该模型是带一个二次约束的非凸二次整数优化问题,且决策变量的取值只能是-2,0,2。然后,针对该模型设计了一种近似算法。利用半正定方法,将原问题进行松弛并求解,再对求得的松弛问题的最优解利用rounding技术进而得到距离计算模型的近似最优解。为了测试这一算法的性能,我们分别对取随机数和取OVFDM系统中具体数值的情况进行了数值试验,并和之前的求解方法进行了数值对比。实验结果表明：不论是哪种情况,该算法求得的近似最优解要么就是最优解,要么十分靠近最优解。同时我们的算法还可以求维数比较大的问题,是求解非正交频分复用系统中距离计算模型的一种较好的方法。(3)本文提出了两个求解三维声源定位问题的算法。考虑到达时间差(TDOA)度量误差且声源具有鲁棒性的三维声源定位问题,是一个带有二次约束的二次分式优化问题。我们先将该模型转化为带二次约束的非凸齐次二次优化问题,之后提出了两个不同的求解算法：(ⅰ)用半正定规划方法求解的全局性算法LCTLS-SDP;(ⅱ)秩一分解算法LCTLS-ROD。LCTLS-SDP算法是将声源定位模型转化为两个带二次不等式约束的非凸齐次二次优化问题,再利用对偶理论设计算法,求出该模型的最优解。在声源可以定位时,我们从理论上证明LCTLS-SDP算法能够找到问题的最优解。数值实验显示,LCTLS-SDP算法有稳健的定位结果。秩一分解算法是将带二次等式约束的分式二次规划声源定位模型先转化为一个等价的非凸齐次二次优化问题,再进行半正定松弛,之后求解松弛问题的最优解,并对松弛问题的最优解进行秩一分解进而得到声源定位问题的最优解。数值实验显示,该秩一分解算法也具有很好的定位结果。更多还原

【Abstract】 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.更多还原