几类带二次约束的非凸二次优化问题的算法研究
|
摘要
二次优化问题在数学规划理论中占据重要地位。同时,随着社会的进步以及科学技术的发展,二次优化问题广泛应用于企业生产管理,金融工程,通信系统,语音识别等重要领域。因此,研究二次优化问题具有重要的意义。
本文主要对三类带二次约束的非凸二次优化问题进行研究,主要工作如下：
(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算法有稳健的定位结果。秩一分解算法是将带二次等式约束的分式二次规划声源定位模型先转化为一个等价的非凸齐次二次优化问题,再进行半正定松弛,之后求解松弛问题的最优解,并对松弛问题的最优解进行秩一分解进而得到声源定位问题的最优解。数值实验显示,该秩一分解算法也具有很好的定位结果。
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.
本文主要对三类带二次约束的非凸二次优化问题进行研究,主要工作如下：
(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算法有稳健的定位结果。秩一分解算法是将带二次等式约束的分式二次规划声源定位模型先转化为一个等价的非凸齐次二次优化问题,再进行半正定松弛,之后求解松弛问题的最优解,并对松弛问题的最优解进行秩一分解进而得到声源定位问题的最优解。数值实验显示,该秩一分解算法也具有很好的定位结果。
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.
引文
[1]Y. Nesterov and A. Nemirovskii. Interior-point Polynomial Algorithms in Convex Programming. Volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematicals(SIAM), Philadelphia, PA, 1994.
[2]A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization. MPS-SIAM Series on Optimization,2001.
[3]M.R. Celis, J.E. Dennis and R.A. Tapia. A Trust Region Algorithm for Nonlinear Equality Constrained Optimization, in R.T. Boggs, R.H. Byrd, and R.B. Schnabel eds., Numerical Optimization, SIAM, Philadelphia,1985:71-82.
[4]C.C.Han, P.M.Pardalos and Y.Ye. Computationla Aspects of an Interior Point Algorithm for Quadratic Programming Problem with Box Constraints, in Large Scale Numerical Optimizatin, T.Coleman Y. Ye, eds, SIAM, Philadephia, PA, 1990.
[5]魏紫銮.边界约束凸二次规划问题的预矫正内点法,数值计算与计算机应用,1998,19(3)：192-202.
[6]张艺.框式约束凸二次规划问题的内点算法,高等学校计算数学学报,2002,24(2)：69-74.
[7]Y.H.Dai and R.Fletcher. Projected Barzilai-Borwein Methods for Large-scale Box-constrained Quadratic Programming, Numer Math,2005,100:21-47.
[8]周斌,高立.求解大规模带边界约束二次规划问题的单挑投影梯度法,中国科学A辑,2006,36(5)：556-570.
[9]L.T.Hoai An and P.D.Tao. Solving a class of linearly constrained indefinite Quadratic Problems by D.C. Algorithms. Journal of Global Optimization, 11,1997:253-285.
[10]O.Barrientos and R. Correa. An Algorithm for Global Minimization of Linearly Constrained Quadratic Functions. Journal of Global Optimization, 16(1),2000:77-93.
[11]A.T.Phillips and J.B.Rosen. Guaranteed ε-approximate Solution for Indefinite Quadratic Global Minimization. Naval Research Logistics,37,1990:499-514.
[12]P.M. Pardalos and S.A. Vavasis. Quadratic Programming with one Negative Eigenvalue is NP-hard. Jounal of Global Optimization,1,1991:843-855.
[13]P.M. Pardalos, W. Hager and Y. Li. Linear Programming Approaches to the Convex Hull Problem. Computers & Mathematics with Applications,29(7), 1995:23-29.
[14]M. Bellare and P. Rogaway. The Complexity of Approximating a Nonlinear Program. Mathematical Programming,69,1995:429-442.
[15]Le Thi Hoai. An Efficient Algorithm for Globally Minimizing a Quadratic Function under Convex Quadratic Constraints. Mathematical Programming Series A,87,2000:401-426.
[16]M.X. Goemans and D.P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM,42,1995:1115-1145.
[17]Y. Nesterov. Semidefinite Relaxation and Nonconvex Quadratic Optimization. Optim. Methods Softw., Special Issue Celebrating the 60th Birthday of Professor Naum Shor,9,1998:141-160.
[18]Y.Ye. Approximating Quadratic Programming with Bound and Quadratic Constraints. Mathematical Programming,84,1999:219-226.
[19]Y. Nesterov. Global Quadratic Optimization via Conic Relaxation, in Handbook of Semidefinite Programming, Theory, Algorithms and Applications. H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, Norwell, MA,2000.363-387.
[20]A. Nemirovskii, C. Roos and T. Terlaky. On Maximization of Quadratic Form over Intersection of Ellipsoids with Common Centers. Mathematical Programming,86,1999:463-473.
[21]M. Fu, Z.-Q. Luo and Y. Ye. Approximation Algorithms for Quadratic Programming. J. Comb. Optim.,2,1998:29-50.
[22]J.F. Sturm and S. Zhang. On Cones of Nonnegative Quadratic Functions. Math. Oper. Res.,28,2003:246-267.
[23]M. Heinkensehlos. On the Solution of a Two Balls Trust Region Subproblem. Mathematical Programming,64,1994:249—276.
[24]J. M. Matiinez and S. A.Santos. A Trust Region Strategy for Minimization on Arbitrary Domains. Mathematical Programming,68,1995:267-301.
[25]R.J.Stern and H. Wolkowicz. Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations. SIAM J. Optim.,5,1995:286-313.
[26]A. Ben Tal and M. Teboulle. Hidden Convexity in Some Nonconvex Quadratically Constrained Quadratic Programming. Mathematical Programming,72,1996:51-63.
[27]M. Peng Ji and Y. Yuan. Optimality Conditions for the Minimization of a Quadratic with Two Quadratic Constraints. SIAM J. Optim.,7,1997:579-594.
[28]Y. Ye and S. Zhang. New Results on Quadratic Minimization. SIAM J. Optim., 14(1),2003:245-267.
[29]Y. Yuan. On a Subproblem of Trust Region Algorithms for Constrained Optimization. Mathematical Programming,47,1990:53-63.
[30]Y. Yuan. A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints. J.Comp. Math.,9,1991:348-359.
[31]Y. Zhang. Computing a Celis-Dennis-Tapia Trust-region Step for Equality Constrained Optimization. Mathematical Programming,55,1992:109-124.
[32]X. Chen and Y. Yuan. On Local Solutions of the Celis-Dennis-Tapia Subproblem. SIAM J. Optim.,10,2000:359-383.
[33]X. Chen and Y. Yuan. On Maxima of Dual Function of the CDT Subproblem, J. Comp. Math.,19,2001:113-124.
[34]J.M. Martinez. Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres. SIAM J.Opt.,4,1994:159-176.
[35]A. Beck and Y. Eldar. Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints, SIAM J. Optimization,17 (3),2006:844-860
[36]Ai Wenbao and Zhang Shuzhong. Strong duality for the CDT subproblem:a necessary and sufficient condition. SIAM Journal on Optimization,19(4),2008: 1735-1756.
[37]U.T.Jonsson. A Lecture on the S-procedure, Lecture notes, Division of Optimization and Systems Theory, Royal Institute of Technology, Stockholm, Sweden,2001.
[38]B.T.Polyak. Convexing of Quadratic Transformations and Its Use in Control and Optimization, J.Optim. Theory Appl.,9,2001:553-583.
[39]Beck A and Teboulle M. A Convex Optimization Approach for Minimizing the Ratio of Indefinite Quadratic Functions Over an Ellipsoid [J]. Mathematical Programming:Series A and B,118(1),2009:13-35.
[40]G.H.Golub and C.F.Van Loan. An Analysis of the Total Least-squares Problem. SIAM J.Numer.Anal.,17(6), Dec.1980:883-893.
[41]S.V. Huffel and J. Vandewalle. The Total Leaat-square Problem:Computational Aspects and Analysis, volume 9 of Frontier in Applied Mathematics. SIAM, Philadelphia, PA,1991.
[42]A.Beck, A.Ben-Tal and M.Teboulle. Finding a Global Optimal Solution for a Quadratically Constrained Fractional Quadratic Problem with Application to the Regularized Total Least Squares. SIAM J.Matrix Anal.Appl.,28(2), 2006:425-445.
[43]G.H.Golub,P.C. Hansen and D.P.O'Leary. Tikhonov Regulazation and Total Least Squares. SIAM J.Matrix Anal.Appl.,21(2),1999:185-194.
[44]H. Guo and R. Renaut. A Regularized Total Least Squares Algorithm. In Total Least Squres and Errors-in-Variables Modeling,57-66. Kulwer,2002.
[45]D. Sima, S.V. Huffel and G.H. Golub. Regularized Total Least Squares based on Quadratic Eigenvalue Problem Solvers. BIT Numerical Mathematics,44(4), 2004:793-812.
[46]D. M. Gay. Computing Optimal Locally Constrained Steps. SIAM J.Sci. Stat. Comput.,2,1981:186-197.
[47]D. C.Sorensen. Newton's Method with a Model Trust Region Modification. SIAM J. Num. Analy.,19(2),1982:409-426.
[48]Sturm J F. Using SeDuMi 1.02, a Matlab Toolbox for Optimization over Symmetric Cones. Optimization Mathods and Softwar,11,1999:625-653.
[49]C.H.Reinsch. Smoothing by Spline Functions,16,1971:451-454.
[50]M.D.Hedben. An Algorithm for Minimization Using Exact Second Derivatives, Technical Reprot TP515, A.E.R.E, Harwell, England,1973.
[51]J. Wang, X. Yang, X.L. Zhang and et.al.. A Novel DFT Based Overlapped Frequency Division Multiplexing System, J.Radio.Sci.Chinese.,23,2008: 17-22.
[52]J.G. Proakis. Digital communication(4th Ed.). Princeton:MCGraw-Hill Companies, Inc,2001:123-135.
[53]D.B. Li. Statistic Examining and Estimating Theory of Signal (2th Ed.) Beijing: Sicence Press,2004:422-425.
[54]Li,Y.,Cimini,L. J. and Sollenberger, N.R. Robust Channel Estimation for OFDM Systems with Rapid Dispersive Fading Channels. IEEE Trans, on Commun,46 (7),1998:902-915.
[55]Hsieh Meng-Han and Wei Che-Ho. Channel Estimation for OFDM Systems Based on Comb-type Pilot Arrangement in Frequency Selective Fading Channel, IEEE Transactions on Consumer Electronics,44 (1),1998:217-225.
[56]Li,G. Pilot-symbol-aided Channel Estimation for OFDM in Wireless Systems. IEEE Transactions on Vehicular Technology,49,2000:1207-1215.
[57]Y Kang,K Kim and H Park. Efficition DFT-based Channel Estimation for OFDM Systems on Multipath Channels. IET Commun,1 (2),2007:197-202.
[58]Huang M,Chen X,Xiao L and et al. Kalman-filter-based Channel Estimation for Orthogonal Frequency Division Multiplexing Systems in Time-varying Channels. IET Commun,1 (4),2007:795-801.
[59]黄瑞, 邹辰.关于编码正交频分复用中同步的研究.光通信研究,5,2007：33-38.
[60]D.B. Li. A Overlap Method and System. International Patent PCT/CN 2006/002012[P],2006.
[61]R.G. Gallager. Information Theory and Reliable Communication. MIT press, 1968.
[62]L. Lov'asz. On the Shannon Capacity of a Graph. IEEE Transactions on Information Theory, IT-25(1),1979:1-7.
[63]Hadlock, F.. Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM J. Comput. 4 (3),1975:221-225.
[64]S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM,23(3), July 1976:555-565.
[65]A.Frieze and M.Jerrum.. Improved Approximation Algorithms for Max k-cut and Max Bisection. Algorithmica,18,1997:67-81.
[66]A. Blum. New Approximation Algorithms for Graph Coloring. Journal of the ACM,41(3), May,1994:470-516.
[67]D. Karger, R. Motwani and M. Sudan. Approximate Graph Coloring by Semidefinite Programming. In 35th Annual Symposium on Foundations of Computer Science, IEEE,1994:2-13.
[68]U. Feige and M.X. Goemans. Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT. In Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995:182-189.
[69]N. Alon and N. Kahale. Approximating the Independence Number via the Function. Technical report, Tel Aviv University, Tel Aviv, Israel,1995.
[70]Ye Y. A 0.699-approximation Algorithm for Max-bisection. Mathematical Programming,90,2001:101-111.
[71]Halperin E and Zwick U. A Unifed Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems. Random Structures and Algorithms,20,2002:382-402
[72]Feige U and Langberg M. The RPR2 Rounding Technique for Semidefinite Programs. Proceedings of the 28th Int. Coll. on Automata, Languages and Programming, Crete, Greece,2001:213-224.
[73]Han Q, Ye Y and Zhang J. An Improved Rounding Method and Semidefinite Programming Relaxation for Graph Partition. Mathematical Programming,92, 2002:509—535
[74]Ye Y, Zhang J. Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection. Journal of Global Optimization,25,2003:55—73
[75]徐大川,韩继业,杜东雷.关于图划分问题的改进的近似算法.应用数学学报,28(4),2005.
[76]Feige U, Goemans M X. Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT. In:Proceedings of the 3nd Israel Symposium On Theory and Computing Systems. Tel Aviv, Israel,1995:182-189.
[77]E.de Klerk and D.V. Pasechnik. On the Performance Guarantee of MAX 3-CUT Approximation Algorithms. Manuscript,2001.
[78]M.X. Goemans and D.P. Williamson. Approximation Algorithms for MAX-3-CUT and Other Problems via Complex Semidefinite Programming. Journal of Computer and System Sciences.Mar.68(2),2004:442-470.
[79]M.C. So, J.W. Zhang and Y.Y. Ye. On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations. Mathematical Programming:Series A and B,110(l),2007:93-110.
[80]Huang Y, Benesty J, Elko G W and et.al.. An Efficient Linear-correction Least-square Approach to Source Localization. IEEE Workshop on Applications of Signal Processing to Audio and Acoustics(WASPAA). New Paltz, NY, USA.2001:21-24.
[81]杨祥清,汪增福.基于麦克风阵列的三维声源定位算法及其实现.声学技术,27(2),2008：260-265.
[82]张奕,殷福亮,陈喆.基于线性校正总体最小二乘准则的三维说话人定位算法.通信学报,30(12),2009：106-122.
[83]Amir B, Aharon B T and Marc T. Finding a Global Optimal Solution for a Quadratically Constrained Fractional Quadratic Problem with Applications to the Regularized Total Least Squares. SIAM J. Matrix Anal. Appl.,28(2),2006: 425-445.
[84]J L Flanagan, J D Johnston, R Zahn and et.al.. Computer-steered Microphone Arrays for Sound Transduction in Large Rooms. Journal of the Acoustical Society of America,11,1985:1508-1518.
[85]M S Brandstein and HF.Silverman. A Practical Methodology for Speech Source Localization with Microphone Arrays. Computer, Speech, and Language,11(2):91-126.
[86]Brandstein, M., Adcock, J. and Silverman, H. A Practical Time-Delay Estimator for Localizing Speech Sources with a Microphone Array. Computer, Speech, and Language,9, April 1995:153-169。
[87]Rudzyn B, Kadous W and Sammut C. Real Time Robot Audition System Incorporating both 3D Sound Source Localization and Voice Characterization. IEEE Int Conf on Roboticd and Automation. Roma, Italy,2007:4733-4738.
[88]Xu Yong, Lu Yinghua, He Pengfei and et.al. TDOA algorithm for UWB localization in mobile environments. IEEE Int Conf on Wireless Communications, Networking and Mobile Computing. Wuhan, China,2006: 1-5
[89]Wu W, Hsieh C, Huang H. Hearing aid system with 3D sound localization. IEEE Region 10 Conference, Tencon. Taipei,2007:1-4.
[90]叶一枝,黄建民.声源定位技术在工业领域中研究与应用.上海电气技术,2(2),2009：55-58.
[91]Schau H C and Robinson A Z. Passive Source Localization Employing Intersection Spherical Surfaces from Time-of-arrival Differences. IEEE Trans on Acoustics, Speech and Signal Processing,35(8),1987:1223-1225.
[92]Smith J O and Abel J S. Closed-form Least-squares Source Location Estimation from Range-difference Measurements. IEEE Trans on Acoustics, Speech and Signal Processing,35(12),1987:1661-1669.
[93]Brandstein M S, Adcock J E and Silverman H F. A Closed-form Localization Estimation for Use with Room Environment Microphone Arrays. IEEE Trans on Speech and Audio Processing,5(1),1997:45-50.
[94]J. Lofberg. YALMIP:A Toolbox for Modeling and Optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan,2004.
[95]Y. W. Huang and S. Zhang. Complex Matrix Decomposition and Quadratic Programming. Mathematics of Operations Research,32,2007:758-768.
[96]W. Ai, Y.W. Huang and S. Zhang. New Results on Hermitian Matrix Rank-one Decomposition. Mathematical Programming, Ser. A,2009.
[97]W. Ai, Y.W. Huang and S. Zhang. On the Low Rank Solutions for Linear Matrix Inequalities. Mathematics of Operations Research,33(4),2008:965-975.
[2]A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization. MPS-SIAM Series on Optimization,2001.
[3]M.R. Celis, J.E. Dennis and R.A. Tapia. A Trust Region Algorithm for Nonlinear Equality Constrained Optimization, in R.T. Boggs, R.H. Byrd, and R.B. Schnabel eds., Numerical Optimization, SIAM, Philadelphia,1985:71-82.
[4]C.C.Han, P.M.Pardalos and Y.Ye. Computationla Aspects of an Interior Point Algorithm for Quadratic Programming Problem with Box Constraints, in Large Scale Numerical Optimizatin, T.Coleman Y. Ye, eds, SIAM, Philadephia, PA, 1990.
[5]魏紫銮.边界约束凸二次规划问题的预矫正内点法,数值计算与计算机应用,1998,19(3)：192-202.
[6]张艺.框式约束凸二次规划问题的内点算法,高等学校计算数学学报,2002,24(2)：69-74.
[7]Y.H.Dai and R.Fletcher. Projected Barzilai-Borwein Methods for Large-scale Box-constrained Quadratic Programming, Numer Math,2005,100:21-47.
[8]周斌,高立.求解大规模带边界约束二次规划问题的单挑投影梯度法,中国科学A辑,2006,36(5)：556-570.
[9]L.T.Hoai An and P.D.Tao. Solving a class of linearly constrained indefinite Quadratic Problems by D.C. Algorithms. Journal of Global Optimization, 11,1997:253-285.
[10]O.Barrientos and R. Correa. An Algorithm for Global Minimization of Linearly Constrained Quadratic Functions. Journal of Global Optimization, 16(1),2000:77-93.
[11]A.T.Phillips and J.B.Rosen. Guaranteed ε-approximate Solution for Indefinite Quadratic Global Minimization. Naval Research Logistics,37,1990:499-514.
[12]P.M. Pardalos and S.A. Vavasis. Quadratic Programming with one Negative Eigenvalue is NP-hard. Jounal of Global Optimization,1,1991:843-855.
[13]P.M. Pardalos, W. Hager and Y. Li. Linear Programming Approaches to the Convex Hull Problem. Computers & Mathematics with Applications,29(7), 1995:23-29.
[14]M. Bellare and P. Rogaway. The Complexity of Approximating a Nonlinear Program. Mathematical Programming,69,1995:429-442.
[15]Le Thi Hoai. An Efficient Algorithm for Globally Minimizing a Quadratic Function under Convex Quadratic Constraints. Mathematical Programming Series A,87,2000:401-426.
[16]M.X. Goemans and D.P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM,42,1995:1115-1145.
[17]Y. Nesterov. Semidefinite Relaxation and Nonconvex Quadratic Optimization. Optim. Methods Softw., Special Issue Celebrating the 60th Birthday of Professor Naum Shor,9,1998:141-160.
[18]Y.Ye. Approximating Quadratic Programming with Bound and Quadratic Constraints. Mathematical Programming,84,1999:219-226.
[19]Y. Nesterov. Global Quadratic Optimization via Conic Relaxation, in Handbook of Semidefinite Programming, Theory, Algorithms and Applications. H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, Norwell, MA,2000.363-387.
[20]A. Nemirovskii, C. Roos and T. Terlaky. On Maximization of Quadratic Form over Intersection of Ellipsoids with Common Centers. Mathematical Programming,86,1999:463-473.
[21]M. Fu, Z.-Q. Luo and Y. Ye. Approximation Algorithms for Quadratic Programming. J. Comb. Optim.,2,1998:29-50.
[22]J.F. Sturm and S. Zhang. On Cones of Nonnegative Quadratic Functions. Math. Oper. Res.,28,2003:246-267.
[23]M. Heinkensehlos. On the Solution of a Two Balls Trust Region Subproblem. Mathematical Programming,64,1994:249—276.
[24]J. M. Matiinez and S. A.Santos. A Trust Region Strategy for Minimization on Arbitrary Domains. Mathematical Programming,68,1995:267-301.
[25]R.J.Stern and H. Wolkowicz. Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations. SIAM J. Optim.,5,1995:286-313.
[26]A. Ben Tal and M. Teboulle. Hidden Convexity in Some Nonconvex Quadratically Constrained Quadratic Programming. Mathematical Programming,72,1996:51-63.
[27]M. Peng Ji and Y. Yuan. Optimality Conditions for the Minimization of a Quadratic with Two Quadratic Constraints. SIAM J. Optim.,7,1997:579-594.
[28]Y. Ye and S. Zhang. New Results on Quadratic Minimization. SIAM J. Optim., 14(1),2003:245-267.
[29]Y. Yuan. On a Subproblem of Trust Region Algorithms for Constrained Optimization. Mathematical Programming,47,1990:53-63.
[30]Y. Yuan. A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints. J.Comp. Math.,9,1991:348-359.
[31]Y. Zhang. Computing a Celis-Dennis-Tapia Trust-region Step for Equality Constrained Optimization. Mathematical Programming,55,1992:109-124.
[32]X. Chen and Y. Yuan. On Local Solutions of the Celis-Dennis-Tapia Subproblem. SIAM J. Optim.,10,2000:359-383.
[33]X. Chen and Y. Yuan. On Maxima of Dual Function of the CDT Subproblem, J. Comp. Math.,19,2001:113-124.
[34]J.M. Martinez. Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres. SIAM J.Opt.,4,1994:159-176.
[35]A. Beck and Y. Eldar. Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints, SIAM J. Optimization,17 (3),2006:844-860
[36]Ai Wenbao and Zhang Shuzhong. Strong duality for the CDT subproblem:a necessary and sufficient condition. SIAM Journal on Optimization,19(4),2008: 1735-1756.
[37]U.T.Jonsson. A Lecture on the S-procedure, Lecture notes, Division of Optimization and Systems Theory, Royal Institute of Technology, Stockholm, Sweden,2001.
[38]B.T.Polyak. Convexing of Quadratic Transformations and Its Use in Control and Optimization, J.Optim. Theory Appl.,9,2001:553-583.
[39]Beck A and Teboulle M. A Convex Optimization Approach for Minimizing the Ratio of Indefinite Quadratic Functions Over an Ellipsoid [J]. Mathematical Programming:Series A and B,118(1),2009:13-35.
[40]G.H.Golub and C.F.Van Loan. An Analysis of the Total Least-squares Problem. SIAM J.Numer.Anal.,17(6), Dec.1980:883-893.
[41]S.V. Huffel and J. Vandewalle. The Total Leaat-square Problem:Computational Aspects and Analysis, volume 9 of Frontier in Applied Mathematics. SIAM, Philadelphia, PA,1991.
[42]A.Beck, A.Ben-Tal and M.Teboulle. Finding a Global Optimal Solution for a Quadratically Constrained Fractional Quadratic Problem with Application to the Regularized Total Least Squares. SIAM J.Matrix Anal.Appl.,28(2), 2006:425-445.
[43]G.H.Golub,P.C. Hansen and D.P.O'Leary. Tikhonov Regulazation and Total Least Squares. SIAM J.Matrix Anal.Appl.,21(2),1999:185-194.
[44]H. Guo and R. Renaut. A Regularized Total Least Squares Algorithm. In Total Least Squres and Errors-in-Variables Modeling,57-66. Kulwer,2002.
[45]D. Sima, S.V. Huffel and G.H. Golub. Regularized Total Least Squares based on Quadratic Eigenvalue Problem Solvers. BIT Numerical Mathematics,44(4), 2004:793-812.
[46]D. M. Gay. Computing Optimal Locally Constrained Steps. SIAM J.Sci. Stat. Comput.,2,1981:186-197.
[47]D. C.Sorensen. Newton's Method with a Model Trust Region Modification. SIAM J. Num. Analy.,19(2),1982:409-426.
[48]Sturm J F. Using SeDuMi 1.02, a Matlab Toolbox for Optimization over Symmetric Cones. Optimization Mathods and Softwar,11,1999:625-653.
[49]C.H.Reinsch. Smoothing by Spline Functions,16,1971:451-454.
[50]M.D.Hedben. An Algorithm for Minimization Using Exact Second Derivatives, Technical Reprot TP515, A.E.R.E, Harwell, England,1973.
[51]J. Wang, X. Yang, X.L. Zhang and et.al.. A Novel DFT Based Overlapped Frequency Division Multiplexing System, J.Radio.Sci.Chinese.,23,2008: 17-22.
[52]J.G. Proakis. Digital communication(4th Ed.). Princeton:MCGraw-Hill Companies, Inc,2001:123-135.
[53]D.B. Li. Statistic Examining and Estimating Theory of Signal (2th Ed.) Beijing: Sicence Press,2004:422-425.
[54]Li,Y.,Cimini,L. J. and Sollenberger, N.R. Robust Channel Estimation for OFDM Systems with Rapid Dispersive Fading Channels. IEEE Trans, on Commun,46 (7),1998:902-915.
[55]Hsieh Meng-Han and Wei Che-Ho. Channel Estimation for OFDM Systems Based on Comb-type Pilot Arrangement in Frequency Selective Fading Channel, IEEE Transactions on Consumer Electronics,44 (1),1998:217-225.
[56]Li,G. Pilot-symbol-aided Channel Estimation for OFDM in Wireless Systems. IEEE Transactions on Vehicular Technology,49,2000:1207-1215.
[57]Y Kang,K Kim and H Park. Efficition DFT-based Channel Estimation for OFDM Systems on Multipath Channels. IET Commun,1 (2),2007:197-202.
[58]Huang M,Chen X,Xiao L and et al. Kalman-filter-based Channel Estimation for Orthogonal Frequency Division Multiplexing Systems in Time-varying Channels. IET Commun,1 (4),2007:795-801.
[59]黄瑞, 邹辰.关于编码正交频分复用中同步的研究.光通信研究,5,2007：33-38.
[60]D.B. Li. A Overlap Method and System. International Patent PCT/CN 2006/002012[P],2006.
[61]R.G. Gallager. Information Theory and Reliable Communication. MIT press, 1968.
[62]L. Lov'asz. On the Shannon Capacity of a Graph. IEEE Transactions on Information Theory, IT-25(1),1979:1-7.
[63]Hadlock, F.. Finding a Maximum Cut of a Planar Graph in Polynomial Time. SIAM J. Comput. 4 (3),1975:221-225.
[64]S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM,23(3), July 1976:555-565.
[65]A.Frieze and M.Jerrum.. Improved Approximation Algorithms for Max k-cut and Max Bisection. Algorithmica,18,1997:67-81.
[66]A. Blum. New Approximation Algorithms for Graph Coloring. Journal of the ACM,41(3), May,1994:470-516.
[67]D. Karger, R. Motwani and M. Sudan. Approximate Graph Coloring by Semidefinite Programming. In 35th Annual Symposium on Foundations of Computer Science, IEEE,1994:2-13.
[68]U. Feige and M.X. Goemans. Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT. In Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995:182-189.
[69]N. Alon and N. Kahale. Approximating the Independence Number via the Function. Technical report, Tel Aviv University, Tel Aviv, Israel,1995.
[70]Ye Y. A 0.699-approximation Algorithm for Max-bisection. Mathematical Programming,90,2001:101-111.
[71]Halperin E and Zwick U. A Unifed Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems. Random Structures and Algorithms,20,2002:382-402
[72]Feige U and Langberg M. The RPR2 Rounding Technique for Semidefinite Programs. Proceedings of the 28th Int. Coll. on Automata, Languages and Programming, Crete, Greece,2001:213-224.
[73]Han Q, Ye Y and Zhang J. An Improved Rounding Method and Semidefinite Programming Relaxation for Graph Partition. Mathematical Programming,92, 2002:509—535
[74]Ye Y, Zhang J. Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection. Journal of Global Optimization,25,2003:55—73
[75]徐大川,韩继业,杜东雷.关于图划分问题的改进的近似算法.应用数学学报,28(4),2005.
[76]Feige U, Goemans M X. Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT. In:Proceedings of the 3nd Israel Symposium On Theory and Computing Systems. Tel Aviv, Israel,1995:182-189.
[77]E.de Klerk and D.V. Pasechnik. On the Performance Guarantee of MAX 3-CUT Approximation Algorithms. Manuscript,2001.
[78]M.X. Goemans and D.P. Williamson. Approximation Algorithms for MAX-3-CUT and Other Problems via Complex Semidefinite Programming. Journal of Computer and System Sciences.Mar.68(2),2004:442-470.
[79]M.C. So, J.W. Zhang and Y.Y. Ye. On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations. Mathematical Programming:Series A and B,110(l),2007:93-110.
[80]Huang Y, Benesty J, Elko G W and et.al.. An Efficient Linear-correction Least-square Approach to Source Localization. IEEE Workshop on Applications of Signal Processing to Audio and Acoustics(WASPAA). New Paltz, NY, USA.2001:21-24.
[81]杨祥清,汪增福.基于麦克风阵列的三维声源定位算法及其实现.声学技术,27(2),2008：260-265.
[82]张奕,殷福亮,陈喆.基于线性校正总体最小二乘准则的三维说话人定位算法.通信学报,30(12),2009：106-122.
[83]Amir B, Aharon B T and Marc T. Finding a Global Optimal Solution for a Quadratically Constrained Fractional Quadratic Problem with Applications to the Regularized Total Least Squares. SIAM J. Matrix Anal. Appl.,28(2),2006: 425-445.
[84]J L Flanagan, J D Johnston, R Zahn and et.al.. Computer-steered Microphone Arrays for Sound Transduction in Large Rooms. Journal of the Acoustical Society of America,11,1985:1508-1518.
[85]M S Brandstein and HF.Silverman. A Practical Methodology for Speech Source Localization with Microphone Arrays. Computer, Speech, and Language,11(2):91-126.
[86]Brandstein, M., Adcock, J. and Silverman, H. A Practical Time-Delay Estimator for Localizing Speech Sources with a Microphone Array. Computer, Speech, and Language,9, April 1995:153-169。
[87]Rudzyn B, Kadous W and Sammut C. Real Time Robot Audition System Incorporating both 3D Sound Source Localization and Voice Characterization. IEEE Int Conf on Roboticd and Automation. Roma, Italy,2007:4733-4738.
[88]Xu Yong, Lu Yinghua, He Pengfei and et.al. TDOA algorithm for UWB localization in mobile environments. IEEE Int Conf on Wireless Communications, Networking and Mobile Computing. Wuhan, China,2006: 1-5
[89]Wu W, Hsieh C, Huang H. Hearing aid system with 3D sound localization. IEEE Region 10 Conference, Tencon. Taipei,2007:1-4.
[90]叶一枝,黄建民.声源定位技术在工业领域中研究与应用.上海电气技术,2(2),2009：55-58.
[91]Schau H C and Robinson A Z. Passive Source Localization Employing Intersection Spherical Surfaces from Time-of-arrival Differences. IEEE Trans on Acoustics, Speech and Signal Processing,35(8),1987:1223-1225.
[92]Smith J O and Abel J S. Closed-form Least-squares Source Location Estimation from Range-difference Measurements. IEEE Trans on Acoustics, Speech and Signal Processing,35(12),1987:1661-1669.
[93]Brandstein M S, Adcock J E and Silverman H F. A Closed-form Localization Estimation for Use with Room Environment Microphone Arrays. IEEE Trans on Speech and Audio Processing,5(1),1997:45-50.
[94]J. Lofberg. YALMIP:A Toolbox for Modeling and Optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan,2004.
[95]Y. W. Huang and S. Zhang. Complex Matrix Decomposition and Quadratic Programming. Mathematics of Operations Research,32,2007:758-768.
[96]W. Ai, Y.W. Huang and S. Zhang. New Results on Hermitian Matrix Rank-one Decomposition. Mathematical Programming, Ser. A,2009.
[97]W. Ai, Y.W. Huang and S. Zhang. On the Low Rank Solutions for Linear Matrix Inequalities. Mathematics of Operations Research,33(4),2008:965-975.