几类锥规划问题算法与应用的研究
|
摘要
二阶锥规划(second-order cone programming)、协正锥规划(eopositive cone pro-gramming)以及双非负锥规划(doubly nonnegativp cone programming)是三类重要的最优化问题,其中，二阶锥规划属于对称锥规划，协正锥规划和双非负锥规划属于非对称锥规划.这些锥规划的特殊结构特点,决定了它们在实际中的应用非常广泛,在人工智能、物联网、数据挖掘、投资组合以及动力系统与控制等领域中都有所应用.此外,协正锥规划还包含了组合优化中许多重要的具有挑战性的NP-难问题.如图的稳定数、二次选址、最大团等问题.因此,研究这三类特殊锥规划的算法理论和实际应用具有重要的理论意义和实际应用价值.
本学位论文旨在较全面了解二阶锥规划、协正锥规划以及双非负锥规划的研究背景及其研究进展的基础上,对这三类锥规划问题的算法理论和应用进行相关研究.取得主要研究成果如下：
(?)第二章研究了一类带有二阶锥约束的非凸二次规划问题.首先,基于二阶锥约束的结构特点,原问题被等价转化为一个二次约束二次规划问题.借助于向量的提升技术和线性锥规划的对偶理论,该二次约束二次规划问题被转化为一个线性锥规划问题,其中约束锥可以被一个半定锥和一个特殊锥的和有效的近似.其次.根据该线性锥规划问题的最优解和二次约束二次规划问题的KKT解的关系,我们给出了一个关于原问题的全局最优性条件.依据此条件,设计了一个求解原问题的算法.该算法在理论上能够保证所得到的最优解是原问题的全局最优解,或者得到的是原问题的一个下界.最后,我们对算法进行了初步的数值实验,数值结果表明该算法能够有效求得原问题的全局最优解,或得到一个较紧的下界.
(?)第三章考虑了一类协正锥规划问题,即在一个特殊协正锥约束空间上求一个连续函数的极小值.首先,根据协正矩阵的定义,给出了协正矩阵另外一种等价的表达形式.基于该新的表达形式,原问题可以被等价转化为一个半无限规划问题.其次,根据离散化方法求解半无限规划问题的思想,给出了一个新的离散化算法来求解原问题.最后,在适当的假设条件下,证明了本章所给出的算法能够有限步收敛到原问题的可行近似最优解.
(?)第四章讨论了一类带有线性与非负约束的多目标二次规划问题.该问题通常不存在使得所有目标函数同时达到最优的最优解.因此寻求Pareto有效解就成为求解原问题的关键.首先,利用线性加权和法,原问题被转化为一个单目标二次规划问题,其在通常情况下是非凸且NP-难的.借助于双非负锥松弛技术,这一单目标二次规划问题被松弛为一可计算的凸规划问题.在一定的假设条件下,该凸规划问题的最优解是原问题的Pareto有效(弱有效)解.最后,对一些随机的例子和实际投资组合例子进行了数值实验,实验结果表明我们所给出的方法是有效的.
(?)第五章研究了一类0-1二次规划问题,其在通常情况下是非凸且NP-难的.为了求解该问题,给出了两种凸松弛方法：一种是半定锥松弛,一种是双非负锥松弛.而且,在一定的假设条件下,证明了这两种松弛方法所得到的问题是等价的.当原问题退化为Max-Cut问题时,双非负锥松弛问题等价于标准的半定锥松弛问题.当原问题退化为Densest k-Subgraph问题时,双非负锥松弛问题等价于一个新的半定锥松弛问题.同时,对于不同问题得到的不同松弛问题,测试了一些随机例子来比较这些松弛问题各自的计算效果.
Second-order cone programming, copositive cone programming and doubly nonneg-ative cone programming are three important classes of optimization problems, among which second-order cone programming belongs to symmetric conic programming, eopos-itive cone programming and doubly nonnegative cone programming are both asymmetric conic programming. Since the special characteristics of these conic programming, they have widely applications in the real world. For example, artificial intelligence, inter-net of things, data mining, portfolio selection, dynamical systems and control, and so on. Moreover, copositive cone programming includes many important and challenging NP-hard problems in the areas of combinatorial optimization, such as stability number of a graph, quadratic-assignment, maximum clique, etc. Therefore, the studies on al-gorithms and practical applications for these three kinds of special conic programming have important theoretical significance and practical value.
Based on the comprehensive understanding of the research progress for second-order cone programming and copositive cone programming as well as doubly nonnegative cone programming, this thesis aims to investigate the algorithms and applications for these three types of conic programming. The main contributions of the thesis are as follows:
◣In Chapter2, we study a class of nonconvex quadratic programming problems with second-order cone constraint. First, according to the characteristics of the second-order cone constraint, the original problem is equivalently reformulated as a quadratically constrained quadratic programming problem. By using the lifting technique and the linear conic duality theory, the latter problem is converted into an equivalent linear conic programming problem, where the constraint cone can be inner approximated by a summation of positive seniideh'nite cone and the cone of special one. Then, a suf-ficient global optimization condition is developed for the original problem in terms of the relationship between the optima] solution of linear conic programming problem and the KKT solution of quadratically constrained quadratic; programming problem. Based on this condition, an algorithm for solving the original problem is presented. Theo-retically, the proposed algorithm which provides either a global optimal solution or a lower bound for the original problem. Finally, we test some elementary examples. The numerical results show that the proposed algorithm can effectively obtain the global optimal solutions or the tighter bounds for the test examples.
? Chapter3is devoted to studying a type of copositive cone programming prob-lems. Based on the definition of copositive matrices, another equivalent expression for copositive matrices is presented. Using this new expression for copositive matrices, the original problem is equivalently transformed into a semi-infinite programming problem. Employing the idea of discretization method for solving semi-infinite programming, a new discretization algorithm for solving the latter semi-infinite programming problem is proposed. Moreover, under some mild assumptions, this new algorithm posses the finite-step convergence.
? In Chapter4, we discuss a kind of multiple objective quadratic programming prob-lems with linear and nonnegative constraints, which does not have a single solution that simultaneously minimizes each objective function in general. So seeking Pareto efficient solutions is the key to solve the original problem. Exploiting the technique of the linear weighted sum method, the original multiple objective quadratic programming problem is transformed into a single objective one. Such a problem is nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative cone relaxation, respectively, this single objective quadratic programming problem is relaxed to a com-putable convex doubly nonnegative cone programming problem. The optimal solutions of this computable convex problem are Pareto (weekly) efficient solutions for the origi-nal problem under some mild conditions. Moreover, the proposed method is tested with some random examples and practical portfolio selection example. The numerical results show that the proposed method is effective and promising.
? Chapter5focuses on the relationship between the semidifinite cone relaxation and the doubly nonnegative cone relaxation for binary quadratic programming problem. Under some suitable assumptions, we prove that the doubly nonnegative relaxation for the original problem is equivalent to a new semidifinite cone relaxation with tighter bound. If the original problem reduces to the Max-Cut problem, the doubly nonnegative cone relaxation for it is equivalent to the standard semidifinite cone relaxation. If the original problem reduces to the Densest k-Subgraph problem, the doubly nonnegative cone relaxation is equivalent to a tighter semidifinite cone relaxation. Furthermore, some comparative numerical results are reported to show the efficiency of these relaxation problems, respectively.
本学位论文旨在较全面了解二阶锥规划、协正锥规划以及双非负锥规划的研究背景及其研究进展的基础上,对这三类锥规划问题的算法理论和应用进行相关研究.取得主要研究成果如下：
(?)第二章研究了一类带有二阶锥约束的非凸二次规划问题.首先,基于二阶锥约束的结构特点,原问题被等价转化为一个二次约束二次规划问题.借助于向量的提升技术和线性锥规划的对偶理论,该二次约束二次规划问题被转化为一个线性锥规划问题,其中约束锥可以被一个半定锥和一个特殊锥的和有效的近似.其次.根据该线性锥规划问题的最优解和二次约束二次规划问题的KKT解的关系,我们给出了一个关于原问题的全局最优性条件.依据此条件,设计了一个求解原问题的算法.该算法在理论上能够保证所得到的最优解是原问题的全局最优解,或者得到的是原问题的一个下界.最后,我们对算法进行了初步的数值实验,数值结果表明该算法能够有效求得原问题的全局最优解,或得到一个较紧的下界.
(?)第三章考虑了一类协正锥规划问题,即在一个特殊协正锥约束空间上求一个连续函数的极小值.首先,根据协正矩阵的定义,给出了协正矩阵另外一种等价的表达形式.基于该新的表达形式,原问题可以被等价转化为一个半无限规划问题.其次,根据离散化方法求解半无限规划问题的思想,给出了一个新的离散化算法来求解原问题.最后,在适当的假设条件下,证明了本章所给出的算法能够有限步收敛到原问题的可行近似最优解.
(?)第四章讨论了一类带有线性与非负约束的多目标二次规划问题.该问题通常不存在使得所有目标函数同时达到最优的最优解.因此寻求Pareto有效解就成为求解原问题的关键.首先,利用线性加权和法,原问题被转化为一个单目标二次规划问题,其在通常情况下是非凸且NP-难的.借助于双非负锥松弛技术,这一单目标二次规划问题被松弛为一可计算的凸规划问题.在一定的假设条件下,该凸规划问题的最优解是原问题的Pareto有效(弱有效)解.最后,对一些随机的例子和实际投资组合例子进行了数值实验,实验结果表明我们所给出的方法是有效的.
(?)第五章研究了一类0-1二次规划问题,其在通常情况下是非凸且NP-难的.为了求解该问题,给出了两种凸松弛方法：一种是半定锥松弛,一种是双非负锥松弛.而且,在一定的假设条件下,证明了这两种松弛方法所得到的问题是等价的.当原问题退化为Max-Cut问题时,双非负锥松弛问题等价于标准的半定锥松弛问题.当原问题退化为Densest k-Subgraph问题时,双非负锥松弛问题等价于一个新的半定锥松弛问题.同时,对于不同问题得到的不同松弛问题,测试了一些随机例子来比较这些松弛问题各自的计算效果.
Second-order cone programming, copositive cone programming and doubly nonneg-ative cone programming are three important classes of optimization problems, among which second-order cone programming belongs to symmetric conic programming, eopos-itive cone programming and doubly nonnegative cone programming are both asymmetric conic programming. Since the special characteristics of these conic programming, they have widely applications in the real world. For example, artificial intelligence, inter-net of things, data mining, portfolio selection, dynamical systems and control, and so on. Moreover, copositive cone programming includes many important and challenging NP-hard problems in the areas of combinatorial optimization, such as stability number of a graph, quadratic-assignment, maximum clique, etc. Therefore, the studies on al-gorithms and practical applications for these three kinds of special conic programming have important theoretical significance and practical value.
Based on the comprehensive understanding of the research progress for second-order cone programming and copositive cone programming as well as doubly nonnegative cone programming, this thesis aims to investigate the algorithms and applications for these three types of conic programming. The main contributions of the thesis are as follows:
◣In Chapter2, we study a class of nonconvex quadratic programming problems with second-order cone constraint. First, according to the characteristics of the second-order cone constraint, the original problem is equivalently reformulated as a quadratically constrained quadratic programming problem. By using the lifting technique and the linear conic duality theory, the latter problem is converted into an equivalent linear conic programming problem, where the constraint cone can be inner approximated by a summation of positive seniideh'nite cone and the cone of special one. Then, a suf-ficient global optimization condition is developed for the original problem in terms of the relationship between the optima] solution of linear conic programming problem and the KKT solution of quadratically constrained quadratic; programming problem. Based on this condition, an algorithm for solving the original problem is presented. Theo-retically, the proposed algorithm which provides either a global optimal solution or a lower bound for the original problem. Finally, we test some elementary examples. The numerical results show that the proposed algorithm can effectively obtain the global optimal solutions or the tighter bounds for the test examples.
? Chapter3is devoted to studying a type of copositive cone programming prob-lems. Based on the definition of copositive matrices, another equivalent expression for copositive matrices is presented. Using this new expression for copositive matrices, the original problem is equivalently transformed into a semi-infinite programming problem. Employing the idea of discretization method for solving semi-infinite programming, a new discretization algorithm for solving the latter semi-infinite programming problem is proposed. Moreover, under some mild assumptions, this new algorithm posses the finite-step convergence.
? In Chapter4, we discuss a kind of multiple objective quadratic programming prob-lems with linear and nonnegative constraints, which does not have a single solution that simultaneously minimizes each objective function in general. So seeking Pareto efficient solutions is the key to solve the original problem. Exploiting the technique of the linear weighted sum method, the original multiple objective quadratic programming problem is transformed into a single objective one. Such a problem is nonconvex and NP-hard in general. By using the techniques of lifting and doubly nonnegative cone relaxation, respectively, this single objective quadratic programming problem is relaxed to a com-putable convex doubly nonnegative cone programming problem. The optimal solutions of this computable convex problem are Pareto (weekly) efficient solutions for the origi-nal problem under some mild conditions. Moreover, the proposed method is tested with some random examples and practical portfolio selection example. The numerical results show that the proposed method is effective and promising.
? Chapter5focuses on the relationship between the semidifinite cone relaxation and the doubly nonnegative cone relaxation for binary quadratic programming problem. Under some suitable assumptions, we prove that the doubly nonnegative relaxation for the original problem is equivalent to a new semidifinite cone relaxation with tighter bound. If the original problem reduces to the Max-Cut problem, the doubly nonnegative cone relaxation for it is equivalent to the standard semidifinite cone relaxation. If the original problem reduces to the Densest k-Subgraph problem, the doubly nonnegative cone relaxation is equivalent to a tighter semidifinite cone relaxation. Furthermore, some comparative numerical results are reported to show the efficiency of these relaxation problems, respectively.
引文
[1]徐玖平和李军.多目标决策的理论与方法.清华大学出版社,2005.
[2]胡毓达.实用多目标最优化.上海科学技术出版社,1990.
[3]胡毓达.多目标规划有效性理论.上海科学技术出版社,1994.
[4]越民义.最小网络：斯坦纳树问题.上海科学技术出版社,2006.
[5]迟晓妮.二次锥规划的算法研究.博士学位论文,西安电子科技大学,2008.
[6]顾剑.非凸二阶锥规划问题的非线性重新尺度化方法.博士学位论文,大连理工大学,2009.
[7]曾友芳.二阶锥规划的理论与算法研究.博士学位论文,上海大学,2011.
[8]F. Ahmed. Relations between semidefinite, copositive, semi-infinite and integer programming. Master's Thesis, University of Twente,2010.
[9]F. Alizadeh and D. Goldfarb. Second-order cone programming. Mathematical programming,95(1):3-51,2003.
[10]F. Alizadeh, J.P.A. Haeberly, and M.L. Overton. Primal-dual interior-point meth-ods for semidefinite programming:convergence rates, stability and numerical re-sults. SIAM Journal on Optimization,8(3):746-768,1998.
[11]F. Alvarez, J. Lopez, and C.H. Ramirez. Interior proximal algorithm with variable metric for second-order cone programming:applications to structural optimization and support vector machines. Optimization Methods & Software,25(6):859-881, 2010.
[12]P. Amaral, I.M. Bomze, and J.J. Judice. Copositivity and constrained fractional quadratic problems. Technical report, TR.-ISDS 2010-05, University of Vienna, 2010.
[13]M. Anitescu, J.F. Cremer. and F.A. Potra. On the existence of solutions to com-plementarity formulations of contact, problems with friction. In Complementarity and Variational Problems:State of the Art, pages 12-21. SIAM,1997.
[14]M. Anitescu and F.A. Potra. Formulating dynamic multi-rigid-body contact prob-lems with friction as solvable linear complementarity problems. Nonlinear Dynam-ics,14(3):231-247,1997.
[15]M. Anitescu and F.A. Potra. A time-stepping method for stiff multibody dynam-ics with contact and friction. International Journal for Numerical Methods in Engineering,55(7):753-784,2002.
[16]C. Audet, P. Hansen, B. Jaumard, and G. Savard. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Mathematical Programming,87(1):131-152,2000.
[17]A. Auslender, M.A. Goberna, and M.A. Lopez. Penalty and smoothing meth-ods for convex semi-infinite programming. Mathematics of Operations Research, 34(2):303-319,2009.
[18]Y.Q. Bai and C.H. Guo. Doubly nonnegative relaxation method for solving mul-tiple objective quadratic programming problems. Journal of Industrial and Man-agement Optimization,2013.
[19]Y.Q. Bai, C.H. Guo, and L.M. Sun. A new algorithm for solving nonconvex quadratic programming over an ice cream cone. Pacific Journal of Optimization, 8(4):651-665,2012.
[20]Y.Q. Bai, G. Lesaja, C. Roos, G.Q. Wang, and M. El Ghami. A class of large-update and small-update primal-dual interior-point algorithms for linear optimiza-tion. Journal of Optimization Theory and Applications,138(3):341-359,2008.
[21]Y.Q. Bai and G.Q. Wang. Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function. Acta Mathematica Sinica, English Series,23(11):2027-2042,2007.
[22]Y.Q. Bai, G.Q. Wang, and C. Roos. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Analysis: Theory, Methods& Applications,70(10):3584-3602,2009.
[23]R.C. Baliban, D. Sakellari, Z.K. Li, Y.A. Guzman, B.A. Garcia, and C.A. Floudas. Discovery of biomarker combinations that predict periodontal health or disease with high accuracy from GCF samples based on high-throughput proteomic anal-ysis and mixed-integer linear optimization. Journal of Clinical Periodontology, 40(2):131 139,2013.
[24]X. Bao, N.V. Sahinidis, and M. Tawarmalani. Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optimization Methods & Software,24(4-5):485-504,2009.
[25]G.P. Barker and J. Foran. Self-dual cones in euclidean spaces. Linear Algebra and its Applications,13(1):147-155,1976.
[26]M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali. Linear Programming and Network Flows. John Wiley & Sons Inc., Fourth Edition,2010.
[27]M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. Nonlinear Programming:Theory and Algorithms. Wiley-Interscience,2006.
[28]A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization:Anal-ysis, Algorithms, and Engineering Applications, volume 2. Society for Industrial and Applied Mathematics,1987.
[29]A. Ben-Tal and A. Nemirovski. Robust solutions of uncertain linear programs. Operations Research Letters,25(1):1-13,1999.
[30]A. Berman. Cones, Matrices and Mathematical Programming. Springer-Verlag, Berlin,1973.
[31]A. Berman and N. Shaked-Monderer. Completely Positive Matrices. World Scien-tific,2003.
[32]C. Bhattacharyya. K.S. Pannagadatta, and A.J. Smola. A second-order cone programming formulation for classifying missing data. Advances in Neural Infor-mation Processing Systems,17:153-160,2004.
[33]CD. Bisbos and P.M. Pardalos. Second-order cone and semidefinite representa-tions of material failure criteria. Journal of Optimization Theory and Applications, 134(2):275-301,2007.
[34]J.W. Blankenship and J.E. Falk. Infinitely constrained optimization problems. Journal of Optimization Theory and Applications,19(2):261-281,1976.
[35]I.M. Bomze. Copositive optimization-recent developments and applications. Eu-ropean Journal of Operational Research,216(3):509-520,2012.
[36]I.M. Bomze and E. De Klerk. Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimiza-tion,24(2):163-185,2002.
[37]I.M. Bomze, M. Dur, E. De Klerk, C. Roos, A.J. Quist, and T. Terlaky. On copositive programming and standard quadratic optimization problems. Journal of Global Optimization,18(4):301-320,2000.
[38]I.M. Bomze, F. Jarre, and F. Rendl. Quadratic factorization heuristics for copos-itive programming. Mathematical Programming Computation,3(1):37-57,2011.
[39]I.M. Bomze, W. Schachinger, and G. Uchida. Think co(mpletely) positive! ma-trix properties, examples and a clustered bibliography on copositive optimization. Journal of Global Optimization,52(3):423-445,2012.
[40]J.F. Bonnans and H. Ramirez C. Perturbation analysis of second-order cone pro-gramming problems. Mathematical Programming,104(2):205-227,2005.
[41]S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[42]B. Brogliato, A.A. Ten Dam. L. Paoli, F. Genot, and M. Abadie. Numerical sim-ulation of finite dimensional multibody nonsmooth mechanical systems. Applied Mechanics Reviews,55(2):107.2002.
[43]S. Bundfuss. Copositive Matrices, Copositive Programming, and Applications. Der Andere Verlag,2009.
[44]S. Bundfuss and M. Diir. Copositivo lyapunov functions for switched systems over cones. Systems& Control Letters,58(5):342345,2009.
[45]S. Burer. On the copositivo representation of binary and continuous nonconvex quadratic programs. Mathematical Programming,120(2):479-495,2009.
[46]S. Burer. Optimizing a polyhedral-semidefmite relaxation of completely positive programs. Mathematical Programming Computation,2(1):119,2010.
[47]S. Burer, K..VL Anstreicher, and M. Diir. The difference between 5×5 doubly nonnegative and completely positive matrices. Linear Algebra and its Applications, 431(9):1539-1552,2009.
[48]S. Burer and H.B. Dong. Representing quadratieally constrained quadratic pro-grams as generalized copositivc programs. Operations Research Letters,40(3):203-206,2012.
[49]M.K. Camlibel and J.M. Schumacher. Copositive lyapunov functions. Unsolved Problems in Mathematical Systems and Control Theory, pages 189-193,2004.
[50]S.C. Chan, H.H. Chen, and C.K.S. Pun. The design of digital all-pass filters using second-order cone programming. IEEE Transactions on Circuits and Systems II: Express Briefs,52(2):66-70,2005.
[51]X.N. Chi and S.Y. Liu. An infeasible interior-point predictor-corrector algorithm for the second-order cone program. Acta. Mathematica Scientia,28(3):551-559, 2008.
[52]J.O. Coleman and D.P. Scholnik. Design of nonlinear-phase FIR filters with second-order cone programming. In 42nd Midwest Symposium on Circuits and Systems, volume 1, pages 409-412. IEEE,1999
[53]X.T. Cui, X.J. Zheng, S.S. Zhu, and X.L. Sun. Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems. Journal of Global Optimization, pages 1-15,2012.
[54]O. Dandekar, W. Plishker, S.S. Bhattacharyya, and R. Shekhar. Multiobjective optimization for reconfigurable implementation of medical image registration. In-ternational Journal of Reconfigurable Computing,2008:1-17,2009.
[55]T. Davi and F. Jarre. Solving large scale problems over the doubly nonnegative cone. Technical report, Institut fur Informatik, Universitat Dusseldorf,2011.
[56]E. de Klerk and D.V. Pasechnik. Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization,12(4):875-892,2002.
[57]R. Debnath, M. Muramatsu, and H. Takahashi. The support vector machine learning using the second-order cone programming. In IEEE International Joint Conference on Neural Networks, volume 4, pages 2991-2996. IEEE,2004.
[58]R. Debnath, M. Muramatsu, and H. Takahashi. An efficient support vector ma-chine learning method with second-order cone programming for large-scale prob-lems. Applied Intelligence,23(3):219-239,2005.
[59]R. Debnath and H. Takahashi. SVM training:Second-order cone programming versus quadratic programming. In International Joint Conference on Neural Net-works, pages 1162-1168. IEEE,2006.
[60]Z.B. Deng, S.C. Fang, Q.W. Jin, and W.X. Xing. Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme. European Journal of Operational Research,2013.
[61]P.H. Diananda. On non-negative forms in real variables some or all of which are non-negative. In Proceedings of the Cambridge Philosophical Society, volume 58, pages 17-25. Cambridge University Press,1962.
[62]P.J.C. Dickinson and L. Gijben. On the computational complexity of member-ship problems for the completely positive cone and its dual. Technical report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands,2011.
[63]E.D. Dolan and J.J. More. Benchmarking optimization software with performance profiles. Mathematical Programming,91(2):201-213,2002.
[64]H.B. Dong. Symmetric tensor approximation hierarchies for the completely positive cone. Technical report:, Department of Management Sciences, Univer-sity of Iowa, Iowa City, IA. Available from:http://www.optimization-online. org/DB_HTML/2010/11/2791. html,2010.
[65]H.B. Dong. Copositive Programming:Separation and Relaxations. PhD Thesis, The University of Iowa,2011.
[66]H.B. Dong and K. Anstreicher. Separating doubly nonnegative and completely positive matrices. Mathematical Programming:Series A,137:131-153,2013.
[67]S. Drewes and S. Ulbrich. Subgradient based outer approximation for mixed integer second-order cone programming. In Mixed Integer Nonlinear Programming, pages 41-59. Springer,2012.
[68]H.Q. Du, T. Ratnarajah, M. Pesavento, and C.B. Papadias. Joint, transceiver beamforming in MIMO cognitive radio network via second-order cone program-ming. IEEE Transactions on Signal Processing.,60(2):781-792,2012.
[69]I. Dukanovic and F. Rendl. Copositive programming motivated bounds on the stability and the chromatic numbers. Mathematical Programming,121(2):249-268,2010.
[70]M. Diir. Copositive programming-a survey. In Recent Advances in Optimization and Its Applications in Engineering, pages 3-20. Springer,2010.
[71]G. Eichfelder and J. Jahn. Set-semidefinite optimization. Journal of Convex Analysis,15(4):767-801.2008.
[72]E. Erdougan and G. Iyengar. An active set method for single-cone second-order cone programs. SIAM Journal on Optimization,17(2):459-484,2006.
[73]L. Fang. A smoothing-typc newton method for second-order cone programming problems based on a new smooth function. Journal of Applied Mathematics and Computing,34(1):147-161,2010.
[74]L. Fang, G.P. He, Z.Z. Feng, and Y.L. Wang. A large-update primal-dual interior-point method for second-order cone programming. In Advances in Neural Networks-ISNN 2010, pages 102-109. Springer,2010.
[75]L. Fang, G.P. He, and Y.H. Hu. A new smoothing newton-type method for second-order cone programming problems. Applied Mathematics and Computa-tion,215(3):1020-1029,2009.
[76]S.C. Fang and S. Puthenpura. Linear Optimization and Extensions:Theory and Algorithms. Prentice-Hall,1993.
[77]L. Faybusovich and T. Mouktonglang. Multi-target linear-quadratic control prob-lem and second-order cone programming. Systems & Control Letters,52(1):17-23, 2004.
[78]U. Feige, G. Kortsarz, and D. Peleg. The dense k-subgraph problem. Algorith-mica,29(3):410-421,2001.
[79]D.D. Ge and Y.Y. Ye. On doubly positive semidefinite programming relaxations. Availabe at http://www.optimizationonline.org/DB HTML/2010/08/2709.html, 2010.
[80]M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM,42(6):1115-1145,1995.
[81]D. Goldfarb and W.T. Yin. Second-order cone programming methods for to-tal variation-based image restoration. SIAM Journal on Scientific Computing, 27(2):622-645,2005.
[82]D. Goldstein and M. Langberg. The dense k-subgraph problem. arXiv preprint arXiv:0912.5327,2009.
[83]M. Grant, S. Boyd, and Y.Y. Ye. CVX:Matlab software for disciplined convex programming. Online accessiable:http://Stanford. edu/-boyd/cvx,2008.
[84]E. Guslitser. Uncertainty-Immunized Solutions in Linear Programming. PhD Thesis, Technion-Israel Institute of Technology,2002.
[85]N. Gvozdenovic and M. Laurent. The operator ψ for the chromatic number of a graph. SIAM Journal on Optimization,19(2):572 591,2008.
[86]C.M. Harvey. Operations Research:An Introduction to Linear Optimization and Decision Analysis. North Holland,1979.
[87]C. Helmberg and F. Rendl. A spectral bundle method for semidefinite program-ming. SIAM Journal on Optimization,10(3):673-696,2000.
[88]C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz. An interior-point method for semidefinite programming. SIAM Journal on Optimization,6(2):342-361,1996.
[89]J.B. Hiriart-Urruty and A. Seeger. A variational approach to copositive matrices. SIAM Review,52(4):593 629,2010.
[90]C. Humes, J. Ou, and P.R. Kumar. The delay of open markovian queueing net-works:uniform functional bounds, heavy traffic pole multiplicities, and stability. Mathematics of Operations Research,22(4):921-954,1997.
[91]K.D. Ikramov and N.V. Savel'eva. Conditionally definite matrices. Journal of Mathematical Sciences,98(1):1-50,2000.
[92]F. Jarre. Burer's key assumption for semidefinite and doubly nonnegative relax-ations. Optimization Letters,6(3):593599,2012.
[93]J.J. Judice, M. Raydan, S.S. Rosa, and S.A. Santos. On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numerical Algorithms,47(4):391-407,2008.
[94]J..J Judice, H.D. Sherali, and I.M. Ribeiro. The eigenvalue complementarity prob-lem. Computational Optimization and Applications,37(2):139-156,2007.
[95]Y. Kanno and M. Ohsaki. Minimum principle of complementary energy of cable networks by using second-order cone programming. International Journal of Solids and Structures,40(17):4437-4460,2003.
[96]Y. Kanno and M. Ohsaki. Contact analysis of cable networks by using second-order cone programming. SI AM Journal on Scientific Computing,27(6):2032-2052,2006.
[97]C. Kanzow and M. Fukushima. Semismooth Methods for Linear and Nonlinear Second-Order Cone Programs. The Institute of Mathematics,2006.
[98]N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 302-311. ACM,1984.
[99]R.M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008, pages 219-241. Springer,2010.
[100]H. Kato and M. Fukushima. An SQP-type algorithm for nonlinear second-order cone programs. Optimization Letters,1(2):129-144,2007.
[101]J.H. Kim, R. Hartley, J.M. Frahm, and M. Pollefeys. Visual odometry for non-overlapping views using second-order cone programming. In Computer Vision-ACCV 2007, pages 353-362. Springer,2007.
[102]S. Kim and M. Kojima. Second-order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods & Software,15(3-4):201-224,2001.
[103]C.H. Ko, J.S. Chen, and C.Y. Yang. Recurrent neural networks for solving second-order cone programs. Neurocomputing,74(17).3646-3653,2011.
[104]M. Kojima and L. Tungel. Cones of matrices and successive convex relaxations of nonconvex sets. SIAM Journal on Optimization,10(3):750-778,2000.
[105]M.P. Kumar, P.H.S. Torr, and A. Zisserman. Solving markov random fields using second-order cone programming relaxations. In IEEE Computer Society Confer-ence on Computer Vision and Pattern Recognition, volume 1, pagos 1045-1052. IEEE,2006.
[106]P.R. Kumar and S.P. Meyn. Duality and linear programs for stability and perfor-mance analysis of queuing networks and scheduling policies. IEEE Transactions on Automatic Control,41(1):4-17,1996.
[107]Y.J. Kuo and H.D. Mittelmann. Interior-point methods for second-order cone programming and or applications. Computational Optimization and Applications, 28(3):255-285,2004.
[108]C. Lacoursiere. Splitting methods for dry frictional contact problems in rigid multibody systems:preliminary performance results. In Conference Proceedings from SIGRAD2003, pages 11-16. Citeseer,2003.
[109]E. Leonardi, M. Mellia, M.A. Marsan, and F. Neri. On the throughput achievable by isolated and interconnected input-queueing switches under multiclass traffic. In Twenty-First Annual Joint Conference of the IEEE Computer and Communi-cations Societies, volume 3, pages 1605-1614. IEEE,2002.
[110]Y.J. Liu and L.W. Zhang. Convergence analysis of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Nonlinear Analy-sis:Theory, Methods & Applications,67(5):1359-1373,2007.
[111]M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret. Second-order cone pro-gramming. Manuscript, Information Systems Laboratory, Electrical Engineering Department, Stanford University, Stanford, CA, USA,1997.
[112]M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret. Applications of second-order cone programming. Linear Algebra and its Applications,284(1):193-228, 1998.
[113]R. Loewy and H. Schneider. Positive operators on the n-dimensional ice cream cone. Journal of Mathematical Analysis and Applications,49(2):375-392,1975.
[114]M. Lopez and G. Still. Semi-infinite programming. European Journal of Opera-tional Research,180(2):491-518,2007.
[115]C. Lu, S.C. Fang, Q.W..Jin, Z. Wang, and W.X. Xing. KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems. SI AM Journal on Optimization,21-(4):1475-1490,2011.
[116]C. Lu, Z. Wang, W. Xing, and S.C. Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Indus-trial and Management Optimization,6(4):779-793,2010.
[117]W.S. Lu, T. Saramaki, and R. Bregovic. Design of practically perfect-reconstruction cosine-modulated filter banks:A second-order cone program-ming approach. IEEE Transactions on Circuits and Systems Ⅰ:Regular Papers, 51(3):552-563,2004.
[118]W.K. Ma, T.N. Davidson, K.M. Wong, Z.Q. Luo, and P.C. Ching. Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with ap-plication to synchronous CDMA. IEEE Transactions on Signal Processing, 50(4):912-922,2002.
[119]W.K. Ma, C.C. Su, J. Jalden, T.H. Chang, and C.Y. Chi. The equivalence of semidefinite relaxation MIMO detectors for higher-order QAM. IEEE Journal of Selected Topics in Signal Processing,3(6):1038-1052,2009.
[120]A. Makrodimopoulos and C.M. Martin. Lower bound limit analysis of cohesive-frictional materials using second-order cone programming. International Journal for Numerical Methods in Engineering,66(4):604-634,2006.
[121]N. Masuda, T. Fujie, and K. Murota. Application of semidefinite programming to maximize the spectral gap produced by node removal. In Complex Networks IV, pages 155-163. Springer,2013.
[122]R.D.C. Monteiro. Primal-dual path-following algorithms for semidefinite program-ming. SI AM Journal on Optimization,7(3):663-678,1997.
[123]R.D.C. Monteiro and T. Tsuchiya. Polynomial convergence of primal-dual algo-rithms for the second-order cone program based on the MZ-family of directions. Mathematical Programming,88(1):61-83,2000.
[124]J.R. Morrison and P.R. Kumar. New linear program performance bounds for closed queueing networks. Discrete Event Dynamic Systems,11(4):291-317,2001.
[125]T.S. Motzkin. National bureau of standards report 1818. Projects and Publications of the National Applied Mathematics Laboratories. Quarterly Report, April-June, 1952.
[126]T.S. Motzkin and E.G. Straus. Maxima for graphs and a new proof of a theorem ofturan. Canadian Journal of Mathematics,17(4):533540,1965.
[127]M. Muramatsu and T. Suzuki. A new second-order cone programming relaxation for max-cut problems. Journal of Operations Research of Japan,46(2):164-177, 2003.
[128]K.G. Murty and S.N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming,39(2):117-129,1987.
[129]A. Nemirovski. Advances in convex optimization:conic programming. In Pro-ceedings oh the International Congress of Mathematicians:Madrid, August 22-30, invited lectures, pages 413-444.2006.
[130]S.H. Pan and J.S. Chen. Proximal-like algorithm using the quasi D-function for convex second-order cone programming. Journal of Optimization Theory and Applications,138(1):95-113,2008.
[131]P.M. Pardalos and S.A. Vavasis. Quadratic programming with one negative eigen-value is NP-hard. Journal of Global Optimization, 1(1):15-22,1991.
[132]J.M. Peng. C. Roos. and T. Terlaky. Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities. SIAM Jour-nal on Optimization,13(1):179-203,2002.
[133]J.M. Peng, C. Roos, and T. Terlaky. Self-Regularity:A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press,2002.
[134]X. Peng and I. King. Robust BMPM training based on second-order cone program-ming and its application in medical diagnosis. Neural Networks,21(2):450-457, 2008.
[135]M. Pesavento, A.D. Gershman, and Z.Q. Luo. Robust, array interpolation using second-order cone programming. IEEE Signal Processing Letters,9(1):8-11,2002.
[136]S.H. Piao, Y.Q. Liu, W. Zhao, and Q.B. Zhong. Application and research of humanoid robot based on second-order cone programming. International Journal of Advanced Robotic Systems,8(2):22-28,2011.
[137]S. Poljak, F. Rendl, and H. Wolkowicz. A recipe for semidefinite relaxation for (0, 1)-quadratic programming. Journal of Global Optimization,7(1):51-73,1995.
[138]J. Povh. Application of Semidefinite and Copositive Programming in Combinato-rial Optimization. PhD Thesis, University of Ljubljana, Ljubljana,2006.
[139]J. Povh and F. Rendl. A copositive programming approach to graph partitioning. SI AM Journal on Optimization,18(1):223-241,2007.
[140]J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization,6(3):231-241,2009.
[141]J.C. Preisig. Copositivity and the minimization of quadratic functions with non-negativity and quadratic equality constraints. SI AM Journal on Control and Op-timization,34(4):1135-1150,1996.
[142]A.J. Quist, E. De klerk, C. Roos, and T. Terlaky. Copositive realxation for genera quadratic programming. Optimization methods & software,9(1-3):185-208,1998.
[143]F. Roupin and A. Billionnet. A deterministic approximation algorithm for the densest k-subgraph problem. International Journal of Operational Research, 3(3):301-314,2008.
[144]T. Sasakawa and T. Tsuchiya. Optimal magnetic shield design with second-order cone programming. SIAM Journal on Scientific Computing,24(6):1930-1950, 2003.
[145]S.H. Schmieta. Application of Jordan Algebras to the Design and Analysis of Interior-Point Algorithms for Linear, Quadratically Constrained Quadratic, and Semidefinite Programming. Rutgers University,1999.
[146]P.K. Shivaswamy, C. Bhattacharyya, and A.J. Smola. Second-order cone program-ming approaches for handling missing and uncertain data. Journal of Machine Learning Research.7:1283-1314,2006.
[147]C.K. Sim and G.Y. Zhao. A note on treating a second-order cone program as a special case of a semidefinite program. Mathematical Programming,102(3):609-613,2005.
[148]K.C. Toh, MJ. Todd, and R.H. Tiituncu. SDPT3-a Matlab software package for semidefinite programming, version 1.3. Optimization Methods & Software,11(1-4):545 581,1999.
[149]P. Tseng. Second-order cone programming relaxation of sensor network localiza-tion. SIAM Journal on Optimization,18(1):156-185,2007.
[150]T. Tsuchiya. A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optimization Methods & Software,11 (1-4):141-182,1999.
[151]R.H. Tutuncii, K.C. Toh, and M.J. Todd. SDPT3-a Matlab software package for semidefinite-quadratic-linear programming, version 3.0. http://www.math.nus. edu.sg/~mattohkc/sdptS.html 2001.
[152]L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(l):49-95,1996.
[153]S.A. Vorobyov, A.B. Gershman, and Z.Q. Luo. An application of second-order cone programming to robust adaptive beamforming. In Proceedings on the 5th International Conference on Optimization:Techniques and Applications, volume 1, pages 308-315, Hong Kong,2001.
[154]G.Q. Wang and Y.Q. Bai. A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Applied Mathematics and Computation,215(3):1047 1061,2009.
[155]Z.W. Wen, D. Goldfarb, and W.T. Yin. Alternating direction augmented La-grangian methods for semidefinite programming. Mathematical Programming Computation,2(3):203-230,2010.
[156]H. Wolkowicz, R. Saigal, and L. Vandenberghe. Handbook of Semidefinite Pro-gramming:Theory, Algorithms, and Applications, volume 27. Springer,2000.
[157]Y. Xia and F. Alizadeh. The Q method for second-order cone programming. Computers & Operations Research,35(5):1510-1538,2008.
[158]Y. Xia, R.L. Sheu, X.L. Sun, and D. Li. Tightening a copositive relaxation for standard quadratic optimization problems. Computational Optimization and Ap-plications, pages 1-20,2012.
[159]J.P. Xu and J. Li. A class of stochastie optimization problems with one quadratic & several linear objective functions and extended portfolio selection model. Journal of Computational and Applied Mathematics,146(1):99-113,2002.
[160]G.L. Xue and Y.Y. Ye. An efficient algorithm for minimizing a sum of euclidean norms with applications. SIAM Journal on Optimization,7(4):1017-1036,1997.
[161]H. Yamashita and H. Yabe. A primal-dual interior-point method for nonlinear op-timization over second-order cones. Optimization Methods & Software,24(3):407-426,2009.
[162]Y. Ye and S. Zhang. New results on quadratic minimization. SIAM Journal on Optimization,14(1):245-267,2004.
[163]E.A. Yildrim. On the accuracy of uniform polyhedral approximations of the copositive cone. Optimization Methods & Software,27(1):155-173,2012.
[164]A. Yoshise and Y. Matsukawa. On optimization over the doubly nonnegative cone. In IEEE International Symposium on Computer-Aided Control System Design, pages 13-18. IEEE,2010.
[165]L.W. Zhang, J. Gu, and X.T. Xiao. A class of nonlinear lagrangians for nonconvex second-order cone programming. Computational Optimization and Applications, 49(1):61-99,2011.
[166]X.S. Zhang, Z.H. Liu, and S.Y. Liu. A trust region SQP-filter method for nonlinear second-order cone programming. Computers & Mathematics with Applications, 63(12):1569-1576,2012.
[167]P. Zhong and M. Fukushima. Second-order cone programming formulations for robust multiclass classification. Neural Computation,19(1):258-282,2007.
[2]胡毓达.实用多目标最优化.上海科学技术出版社,1990.
[3]胡毓达.多目标规划有效性理论.上海科学技术出版社,1994.
[4]越民义.最小网络：斯坦纳树问题.上海科学技术出版社,2006.
[5]迟晓妮.二次锥规划的算法研究.博士学位论文,西安电子科技大学,2008.
[6]顾剑.非凸二阶锥规划问题的非线性重新尺度化方法.博士学位论文,大连理工大学,2009.
[7]曾友芳.二阶锥规划的理论与算法研究.博士学位论文,上海大学,2011.
[8]F. Ahmed. Relations between semidefinite, copositive, semi-infinite and integer programming. Master's Thesis, University of Twente,2010.
[9]F. Alizadeh and D. Goldfarb. Second-order cone programming. Mathematical programming,95(1):3-51,2003.
[10]F. Alizadeh, J.P.A. Haeberly, and M.L. Overton. Primal-dual interior-point meth-ods for semidefinite programming:convergence rates, stability and numerical re-sults. SIAM Journal on Optimization,8(3):746-768,1998.
[11]F. Alvarez, J. Lopez, and C.H. Ramirez. Interior proximal algorithm with variable metric for second-order cone programming:applications to structural optimization and support vector machines. Optimization Methods & Software,25(6):859-881, 2010.
[12]P. Amaral, I.M. Bomze, and J.J. Judice. Copositivity and constrained fractional quadratic problems. Technical report, TR.-ISDS 2010-05, University of Vienna, 2010.
[13]M. Anitescu, J.F. Cremer. and F.A. Potra. On the existence of solutions to com-plementarity formulations of contact, problems with friction. In Complementarity and Variational Problems:State of the Art, pages 12-21. SIAM,1997.
[14]M. Anitescu and F.A. Potra. Formulating dynamic multi-rigid-body contact prob-lems with friction as solvable linear complementarity problems. Nonlinear Dynam-ics,14(3):231-247,1997.
[15]M. Anitescu and F.A. Potra. A time-stepping method for stiff multibody dynam-ics with contact and friction. International Journal for Numerical Methods in Engineering,55(7):753-784,2002.
[16]C. Audet, P. Hansen, B. Jaumard, and G. Savard. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Mathematical Programming,87(1):131-152,2000.
[17]A. Auslender, M.A. Goberna, and M.A. Lopez. Penalty and smoothing meth-ods for convex semi-infinite programming. Mathematics of Operations Research, 34(2):303-319,2009.
[18]Y.Q. Bai and C.H. Guo. Doubly nonnegative relaxation method for solving mul-tiple objective quadratic programming problems. Journal of Industrial and Man-agement Optimization,2013.
[19]Y.Q. Bai, C.H. Guo, and L.M. Sun. A new algorithm for solving nonconvex quadratic programming over an ice cream cone. Pacific Journal of Optimization, 8(4):651-665,2012.
[20]Y.Q. Bai, G. Lesaja, C. Roos, G.Q. Wang, and M. El Ghami. A class of large-update and small-update primal-dual interior-point algorithms for linear optimiza-tion. Journal of Optimization Theory and Applications,138(3):341-359,2008.
[21]Y.Q. Bai and G.Q. Wang. Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function. Acta Mathematica Sinica, English Series,23(11):2027-2042,2007.
[22]Y.Q. Bai, G.Q. Wang, and C. Roos. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Analysis: Theory, Methods& Applications,70(10):3584-3602,2009.
[23]R.C. Baliban, D. Sakellari, Z.K. Li, Y.A. Guzman, B.A. Garcia, and C.A. Floudas. Discovery of biomarker combinations that predict periodontal health or disease with high accuracy from GCF samples based on high-throughput proteomic anal-ysis and mixed-integer linear optimization. Journal of Clinical Periodontology, 40(2):131 139,2013.
[24]X. Bao, N.V. Sahinidis, and M. Tawarmalani. Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optimization Methods & Software,24(4-5):485-504,2009.
[25]G.P. Barker and J. Foran. Self-dual cones in euclidean spaces. Linear Algebra and its Applications,13(1):147-155,1976.
[26]M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali. Linear Programming and Network Flows. John Wiley & Sons Inc., Fourth Edition,2010.
[27]M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. Nonlinear Programming:Theory and Algorithms. Wiley-Interscience,2006.
[28]A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization:Anal-ysis, Algorithms, and Engineering Applications, volume 2. Society for Industrial and Applied Mathematics,1987.
[29]A. Ben-Tal and A. Nemirovski. Robust solutions of uncertain linear programs. Operations Research Letters,25(1):1-13,1999.
[30]A. Berman. Cones, Matrices and Mathematical Programming. Springer-Verlag, Berlin,1973.
[31]A. Berman and N. Shaked-Monderer. Completely Positive Matrices. World Scien-tific,2003.
[32]C. Bhattacharyya. K.S. Pannagadatta, and A.J. Smola. A second-order cone programming formulation for classifying missing data. Advances in Neural Infor-mation Processing Systems,17:153-160,2004.
[33]CD. Bisbos and P.M. Pardalos. Second-order cone and semidefinite representa-tions of material failure criteria. Journal of Optimization Theory and Applications, 134(2):275-301,2007.
[34]J.W. Blankenship and J.E. Falk. Infinitely constrained optimization problems. Journal of Optimization Theory and Applications,19(2):261-281,1976.
[35]I.M. Bomze. Copositive optimization-recent developments and applications. Eu-ropean Journal of Operational Research,216(3):509-520,2012.
[36]I.M. Bomze and E. De Klerk. Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Journal of Global Optimiza-tion,24(2):163-185,2002.
[37]I.M. Bomze, M. Dur, E. De Klerk, C. Roos, A.J. Quist, and T. Terlaky. On copositive programming and standard quadratic optimization problems. Journal of Global Optimization,18(4):301-320,2000.
[38]I.M. Bomze, F. Jarre, and F. Rendl. Quadratic factorization heuristics for copos-itive programming. Mathematical Programming Computation,3(1):37-57,2011.
[39]I.M. Bomze, W. Schachinger, and G. Uchida. Think co(mpletely) positive! ma-trix properties, examples and a clustered bibliography on copositive optimization. Journal of Global Optimization,52(3):423-445,2012.
[40]J.F. Bonnans and H. Ramirez C. Perturbation analysis of second-order cone pro-gramming problems. Mathematical Programming,104(2):205-227,2005.
[41]S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[42]B. Brogliato, A.A. Ten Dam. L. Paoli, F. Genot, and M. Abadie. Numerical sim-ulation of finite dimensional multibody nonsmooth mechanical systems. Applied Mechanics Reviews,55(2):107.2002.
[43]S. Bundfuss. Copositive Matrices, Copositive Programming, and Applications. Der Andere Verlag,2009.
[44]S. Bundfuss and M. Diir. Copositivo lyapunov functions for switched systems over cones. Systems& Control Letters,58(5):342345,2009.
[45]S. Burer. On the copositivo representation of binary and continuous nonconvex quadratic programs. Mathematical Programming,120(2):479-495,2009.
[46]S. Burer. Optimizing a polyhedral-semidefmite relaxation of completely positive programs. Mathematical Programming Computation,2(1):119,2010.
[47]S. Burer, K..VL Anstreicher, and M. Diir. The difference between 5×5 doubly nonnegative and completely positive matrices. Linear Algebra and its Applications, 431(9):1539-1552,2009.
[48]S. Burer and H.B. Dong. Representing quadratieally constrained quadratic pro-grams as generalized copositivc programs. Operations Research Letters,40(3):203-206,2012.
[49]M.K. Camlibel and J.M. Schumacher. Copositive lyapunov functions. Unsolved Problems in Mathematical Systems and Control Theory, pages 189-193,2004.
[50]S.C. Chan, H.H. Chen, and C.K.S. Pun. The design of digital all-pass filters using second-order cone programming. IEEE Transactions on Circuits and Systems II: Express Briefs,52(2):66-70,2005.
[51]X.N. Chi and S.Y. Liu. An infeasible interior-point predictor-corrector algorithm for the second-order cone program. Acta. Mathematica Scientia,28(3):551-559, 2008.
[52]J.O. Coleman and D.P. Scholnik. Design of nonlinear-phase FIR filters with second-order cone programming. In 42nd Midwest Symposium on Circuits and Systems, volume 1, pages 409-412. IEEE,1999
[53]X.T. Cui, X.J. Zheng, S.S. Zhu, and X.L. Sun. Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems. Journal of Global Optimization, pages 1-15,2012.
[54]O. Dandekar, W. Plishker, S.S. Bhattacharyya, and R. Shekhar. Multiobjective optimization for reconfigurable implementation of medical image registration. In-ternational Journal of Reconfigurable Computing,2008:1-17,2009.
[55]T. Davi and F. Jarre. Solving large scale problems over the doubly nonnegative cone. Technical report, Institut fur Informatik, Universitat Dusseldorf,2011.
[56]E. de Klerk and D.V. Pasechnik. Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization,12(4):875-892,2002.
[57]R. Debnath, M. Muramatsu, and H. Takahashi. The support vector machine learning using the second-order cone programming. In IEEE International Joint Conference on Neural Networks, volume 4, pages 2991-2996. IEEE,2004.
[58]R. Debnath, M. Muramatsu, and H. Takahashi. An efficient support vector ma-chine learning method with second-order cone programming for large-scale prob-lems. Applied Intelligence,23(3):219-239,2005.
[59]R. Debnath and H. Takahashi. SVM training:Second-order cone programming versus quadratic programming. In International Joint Conference on Neural Net-works, pages 1162-1168. IEEE,2006.
[60]Z.B. Deng, S.C. Fang, Q.W. Jin, and W.X. Xing. Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme. European Journal of Operational Research,2013.
[61]P.H. Diananda. On non-negative forms in real variables some or all of which are non-negative. In Proceedings of the Cambridge Philosophical Society, volume 58, pages 17-25. Cambridge University Press,1962.
[62]P.J.C. Dickinson and L. Gijben. On the computational complexity of member-ship problems for the completely positive cone and its dual. Technical report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands,2011.
[63]E.D. Dolan and J.J. More. Benchmarking optimization software with performance profiles. Mathematical Programming,91(2):201-213,2002.
[64]H.B. Dong. Symmetric tensor approximation hierarchies for the completely positive cone. Technical report:, Department of Management Sciences, Univer-sity of Iowa, Iowa City, IA. Available from:http://www.optimization-online. org/DB_HTML/2010/11/2791. html,2010.
[65]H.B. Dong. Copositive Programming:Separation and Relaxations. PhD Thesis, The University of Iowa,2011.
[66]H.B. Dong and K. Anstreicher. Separating doubly nonnegative and completely positive matrices. Mathematical Programming:Series A,137:131-153,2013.
[67]S. Drewes and S. Ulbrich. Subgradient based outer approximation for mixed integer second-order cone programming. In Mixed Integer Nonlinear Programming, pages 41-59. Springer,2012.
[68]H.Q. Du, T. Ratnarajah, M. Pesavento, and C.B. Papadias. Joint, transceiver beamforming in MIMO cognitive radio network via second-order cone program-ming. IEEE Transactions on Signal Processing.,60(2):781-792,2012.
[69]I. Dukanovic and F. Rendl. Copositive programming motivated bounds on the stability and the chromatic numbers. Mathematical Programming,121(2):249-268,2010.
[70]M. Diir. Copositive programming-a survey. In Recent Advances in Optimization and Its Applications in Engineering, pages 3-20. Springer,2010.
[71]G. Eichfelder and J. Jahn. Set-semidefinite optimization. Journal of Convex Analysis,15(4):767-801.2008.
[72]E. Erdougan and G. Iyengar. An active set method for single-cone second-order cone programs. SIAM Journal on Optimization,17(2):459-484,2006.
[73]L. Fang. A smoothing-typc newton method for second-order cone programming problems based on a new smooth function. Journal of Applied Mathematics and Computing,34(1):147-161,2010.
[74]L. Fang, G.P. He, Z.Z. Feng, and Y.L. Wang. A large-update primal-dual interior-point method for second-order cone programming. In Advances in Neural Networks-ISNN 2010, pages 102-109. Springer,2010.
[75]L. Fang, G.P. He, and Y.H. Hu. A new smoothing newton-type method for second-order cone programming problems. Applied Mathematics and Computa-tion,215(3):1020-1029,2009.
[76]S.C. Fang and S. Puthenpura. Linear Optimization and Extensions:Theory and Algorithms. Prentice-Hall,1993.
[77]L. Faybusovich and T. Mouktonglang. Multi-target linear-quadratic control prob-lem and second-order cone programming. Systems & Control Letters,52(1):17-23, 2004.
[78]U. Feige, G. Kortsarz, and D. Peleg. The dense k-subgraph problem. Algorith-mica,29(3):410-421,2001.
[79]D.D. Ge and Y.Y. Ye. On doubly positive semidefinite programming relaxations. Availabe at http://www.optimizationonline.org/DB HTML/2010/08/2709.html, 2010.
[80]M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM,42(6):1115-1145,1995.
[81]D. Goldfarb and W.T. Yin. Second-order cone programming methods for to-tal variation-based image restoration. SIAM Journal on Scientific Computing, 27(2):622-645,2005.
[82]D. Goldstein and M. Langberg. The dense k-subgraph problem. arXiv preprint arXiv:0912.5327,2009.
[83]M. Grant, S. Boyd, and Y.Y. Ye. CVX:Matlab software for disciplined convex programming. Online accessiable:http://Stanford. edu/-boyd/cvx,2008.
[84]E. Guslitser. Uncertainty-Immunized Solutions in Linear Programming. PhD Thesis, Technion-Israel Institute of Technology,2002.
[85]N. Gvozdenovic and M. Laurent. The operator ψ for the chromatic number of a graph. SIAM Journal on Optimization,19(2):572 591,2008.
[86]C.M. Harvey. Operations Research:An Introduction to Linear Optimization and Decision Analysis. North Holland,1979.
[87]C. Helmberg and F. Rendl. A spectral bundle method for semidefinite program-ming. SIAM Journal on Optimization,10(3):673-696,2000.
[88]C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz. An interior-point method for semidefinite programming. SIAM Journal on Optimization,6(2):342-361,1996.
[89]J.B. Hiriart-Urruty and A. Seeger. A variational approach to copositive matrices. SIAM Review,52(4):593 629,2010.
[90]C. Humes, J. Ou, and P.R. Kumar. The delay of open markovian queueing net-works:uniform functional bounds, heavy traffic pole multiplicities, and stability. Mathematics of Operations Research,22(4):921-954,1997.
[91]K.D. Ikramov and N.V. Savel'eva. Conditionally definite matrices. Journal of Mathematical Sciences,98(1):1-50,2000.
[92]F. Jarre. Burer's key assumption for semidefinite and doubly nonnegative relax-ations. Optimization Letters,6(3):593599,2012.
[93]J.J. Judice, M. Raydan, S.S. Rosa, and S.A. Santos. On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numerical Algorithms,47(4):391-407,2008.
[94]J..J Judice, H.D. Sherali, and I.M. Ribeiro. The eigenvalue complementarity prob-lem. Computational Optimization and Applications,37(2):139-156,2007.
[95]Y. Kanno and M. Ohsaki. Minimum principle of complementary energy of cable networks by using second-order cone programming. International Journal of Solids and Structures,40(17):4437-4460,2003.
[96]Y. Kanno and M. Ohsaki. Contact analysis of cable networks by using second-order cone programming. SI AM Journal on Scientific Computing,27(6):2032-2052,2006.
[97]C. Kanzow and M. Fukushima. Semismooth Methods for Linear and Nonlinear Second-Order Cone Programs. The Institute of Mathematics,2006.
[98]N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 302-311. ACM,1984.
[99]R.M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008, pages 219-241. Springer,2010.
[100]H. Kato and M. Fukushima. An SQP-type algorithm for nonlinear second-order cone programs. Optimization Letters,1(2):129-144,2007.
[101]J.H. Kim, R. Hartley, J.M. Frahm, and M. Pollefeys. Visual odometry for non-overlapping views using second-order cone programming. In Computer Vision-ACCV 2007, pages 353-362. Springer,2007.
[102]S. Kim and M. Kojima. Second-order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods & Software,15(3-4):201-224,2001.
[103]C.H. Ko, J.S. Chen, and C.Y. Yang. Recurrent neural networks for solving second-order cone programs. Neurocomputing,74(17).3646-3653,2011.
[104]M. Kojima and L. Tungel. Cones of matrices and successive convex relaxations of nonconvex sets. SIAM Journal on Optimization,10(3):750-778,2000.
[105]M.P. Kumar, P.H.S. Torr, and A. Zisserman. Solving markov random fields using second-order cone programming relaxations. In IEEE Computer Society Confer-ence on Computer Vision and Pattern Recognition, volume 1, pagos 1045-1052. IEEE,2006.
[106]P.R. Kumar and S.P. Meyn. Duality and linear programs for stability and perfor-mance analysis of queuing networks and scheduling policies. IEEE Transactions on Automatic Control,41(1):4-17,1996.
[107]Y.J. Kuo and H.D. Mittelmann. Interior-point methods for second-order cone programming and or applications. Computational Optimization and Applications, 28(3):255-285,2004.
[108]C. Lacoursiere. Splitting methods for dry frictional contact problems in rigid multibody systems:preliminary performance results. In Conference Proceedings from SIGRAD2003, pages 11-16. Citeseer,2003.
[109]E. Leonardi, M. Mellia, M.A. Marsan, and F. Neri. On the throughput achievable by isolated and interconnected input-queueing switches under multiclass traffic. In Twenty-First Annual Joint Conference of the IEEE Computer and Communi-cations Societies, volume 3, pages 1605-1614. IEEE,2002.
[110]Y.J. Liu and L.W. Zhang. Convergence analysis of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Nonlinear Analy-sis:Theory, Methods & Applications,67(5):1359-1373,2007.
[111]M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret. Second-order cone pro-gramming. Manuscript, Information Systems Laboratory, Electrical Engineering Department, Stanford University, Stanford, CA, USA,1997.
[112]M.S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret. Applications of second-order cone programming. Linear Algebra and its Applications,284(1):193-228, 1998.
[113]R. Loewy and H. Schneider. Positive operators on the n-dimensional ice cream cone. Journal of Mathematical Analysis and Applications,49(2):375-392,1975.
[114]M. Lopez and G. Still. Semi-infinite programming. European Journal of Opera-tional Research,180(2):491-518,2007.
[115]C. Lu, S.C. Fang, Q.W..Jin, Z. Wang, and W.X. Xing. KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems. SI AM Journal on Optimization,21-(4):1475-1490,2011.
[116]C. Lu, Z. Wang, W. Xing, and S.C. Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Indus-trial and Management Optimization,6(4):779-793,2010.
[117]W.S. Lu, T. Saramaki, and R. Bregovic. Design of practically perfect-reconstruction cosine-modulated filter banks:A second-order cone program-ming approach. IEEE Transactions on Circuits and Systems Ⅰ:Regular Papers, 51(3):552-563,2004.
[118]W.K. Ma, T.N. Davidson, K.M. Wong, Z.Q. Luo, and P.C. Ching. Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with ap-plication to synchronous CDMA. IEEE Transactions on Signal Processing, 50(4):912-922,2002.
[119]W.K. Ma, C.C. Su, J. Jalden, T.H. Chang, and C.Y. Chi. The equivalence of semidefinite relaxation MIMO detectors for higher-order QAM. IEEE Journal of Selected Topics in Signal Processing,3(6):1038-1052,2009.
[120]A. Makrodimopoulos and C.M. Martin. Lower bound limit analysis of cohesive-frictional materials using second-order cone programming. International Journal for Numerical Methods in Engineering,66(4):604-634,2006.
[121]N. Masuda, T. Fujie, and K. Murota. Application of semidefinite programming to maximize the spectral gap produced by node removal. In Complex Networks IV, pages 155-163. Springer,2013.
[122]R.D.C. Monteiro. Primal-dual path-following algorithms for semidefinite program-ming. SI AM Journal on Optimization,7(3):663-678,1997.
[123]R.D.C. Monteiro and T. Tsuchiya. Polynomial convergence of primal-dual algo-rithms for the second-order cone program based on the MZ-family of directions. Mathematical Programming,88(1):61-83,2000.
[124]J.R. Morrison and P.R. Kumar. New linear program performance bounds for closed queueing networks. Discrete Event Dynamic Systems,11(4):291-317,2001.
[125]T.S. Motzkin. National bureau of standards report 1818. Projects and Publications of the National Applied Mathematics Laboratories. Quarterly Report, April-June, 1952.
[126]T.S. Motzkin and E.G. Straus. Maxima for graphs and a new proof of a theorem ofturan. Canadian Journal of Mathematics,17(4):533540,1965.
[127]M. Muramatsu and T. Suzuki. A new second-order cone programming relaxation for max-cut problems. Journal of Operations Research of Japan,46(2):164-177, 2003.
[128]K.G. Murty and S.N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming,39(2):117-129,1987.
[129]A. Nemirovski. Advances in convex optimization:conic programming. In Pro-ceedings oh the International Congress of Mathematicians:Madrid, August 22-30, invited lectures, pages 413-444.2006.
[130]S.H. Pan and J.S. Chen. Proximal-like algorithm using the quasi D-function for convex second-order cone programming. Journal of Optimization Theory and Applications,138(1):95-113,2008.
[131]P.M. Pardalos and S.A. Vavasis. Quadratic programming with one negative eigen-value is NP-hard. Journal of Global Optimization, 1(1):15-22,1991.
[132]J.M. Peng. C. Roos. and T. Terlaky. Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities. SIAM Jour-nal on Optimization,13(1):179-203,2002.
[133]J.M. Peng, C. Roos, and T. Terlaky. Self-Regularity:A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press,2002.
[134]X. Peng and I. King. Robust BMPM training based on second-order cone program-ming and its application in medical diagnosis. Neural Networks,21(2):450-457, 2008.
[135]M. Pesavento, A.D. Gershman, and Z.Q. Luo. Robust, array interpolation using second-order cone programming. IEEE Signal Processing Letters,9(1):8-11,2002.
[136]S.H. Piao, Y.Q. Liu, W. Zhao, and Q.B. Zhong. Application and research of humanoid robot based on second-order cone programming. International Journal of Advanced Robotic Systems,8(2):22-28,2011.
[137]S. Poljak, F. Rendl, and H. Wolkowicz. A recipe for semidefinite relaxation for (0, 1)-quadratic programming. Journal of Global Optimization,7(1):51-73,1995.
[138]J. Povh. Application of Semidefinite and Copositive Programming in Combinato-rial Optimization. PhD Thesis, University of Ljubljana, Ljubljana,2006.
[139]J. Povh and F. Rendl. A copositive programming approach to graph partitioning. SI AM Journal on Optimization,18(1):223-241,2007.
[140]J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization,6(3):231-241,2009.
[141]J.C. Preisig. Copositivity and the minimization of quadratic functions with non-negativity and quadratic equality constraints. SI AM Journal on Control and Op-timization,34(4):1135-1150,1996.
[142]A.J. Quist, E. De klerk, C. Roos, and T. Terlaky. Copositive realxation for genera quadratic programming. Optimization methods & software,9(1-3):185-208,1998.
[143]F. Roupin and A. Billionnet. A deterministic approximation algorithm for the densest k-subgraph problem. International Journal of Operational Research, 3(3):301-314,2008.
[144]T. Sasakawa and T. Tsuchiya. Optimal magnetic shield design with second-order cone programming. SIAM Journal on Scientific Computing,24(6):1930-1950, 2003.
[145]S.H. Schmieta. Application of Jordan Algebras to the Design and Analysis of Interior-Point Algorithms for Linear, Quadratically Constrained Quadratic, and Semidefinite Programming. Rutgers University,1999.
[146]P.K. Shivaswamy, C. Bhattacharyya, and A.J. Smola. Second-order cone program-ming approaches for handling missing and uncertain data. Journal of Machine Learning Research.7:1283-1314,2006.
[147]C.K. Sim and G.Y. Zhao. A note on treating a second-order cone program as a special case of a semidefinite program. Mathematical Programming,102(3):609-613,2005.
[148]K.C. Toh, MJ. Todd, and R.H. Tiituncu. SDPT3-a Matlab software package for semidefinite programming, version 1.3. Optimization Methods & Software,11(1-4):545 581,1999.
[149]P. Tseng. Second-order cone programming relaxation of sensor network localiza-tion. SIAM Journal on Optimization,18(1):156-185,2007.
[150]T. Tsuchiya. A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optimization Methods & Software,11 (1-4):141-182,1999.
[151]R.H. Tutuncii, K.C. Toh, and M.J. Todd. SDPT3-a Matlab software package for semidefinite-quadratic-linear programming, version 3.0. http://www.math.nus. edu.sg/~mattohkc/sdptS.html 2001.
[152]L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(l):49-95,1996.
[153]S.A. Vorobyov, A.B. Gershman, and Z.Q. Luo. An application of second-order cone programming to robust adaptive beamforming. In Proceedings on the 5th International Conference on Optimization:Techniques and Applications, volume 1, pages 308-315, Hong Kong,2001.
[154]G.Q. Wang and Y.Q. Bai. A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Applied Mathematics and Computation,215(3):1047 1061,2009.
[155]Z.W. Wen, D. Goldfarb, and W.T. Yin. Alternating direction augmented La-grangian methods for semidefinite programming. Mathematical Programming Computation,2(3):203-230,2010.
[156]H. Wolkowicz, R. Saigal, and L. Vandenberghe. Handbook of Semidefinite Pro-gramming:Theory, Algorithms, and Applications, volume 27. Springer,2000.
[157]Y. Xia and F. Alizadeh. The Q method for second-order cone programming. Computers & Operations Research,35(5):1510-1538,2008.
[158]Y. Xia, R.L. Sheu, X.L. Sun, and D. Li. Tightening a copositive relaxation for standard quadratic optimization problems. Computational Optimization and Ap-plications, pages 1-20,2012.
[159]J.P. Xu and J. Li. A class of stochastie optimization problems with one quadratic & several linear objective functions and extended portfolio selection model. Journal of Computational and Applied Mathematics,146(1):99-113,2002.
[160]G.L. Xue and Y.Y. Ye. An efficient algorithm for minimizing a sum of euclidean norms with applications. SIAM Journal on Optimization,7(4):1017-1036,1997.
[161]H. Yamashita and H. Yabe. A primal-dual interior-point method for nonlinear op-timization over second-order cones. Optimization Methods & Software,24(3):407-426,2009.
[162]Y. Ye and S. Zhang. New results on quadratic minimization. SIAM Journal on Optimization,14(1):245-267,2004.
[163]E.A. Yildrim. On the accuracy of uniform polyhedral approximations of the copositive cone. Optimization Methods & Software,27(1):155-173,2012.
[164]A. Yoshise and Y. Matsukawa. On optimization over the doubly nonnegative cone. In IEEE International Symposium on Computer-Aided Control System Design, pages 13-18. IEEE,2010.
[165]L.W. Zhang, J. Gu, and X.T. Xiao. A class of nonlinear lagrangians for nonconvex second-order cone programming. Computational Optimization and Applications, 49(1):61-99,2011.
[166]X.S. Zhang, Z.H. Liu, and S.Y. Liu. A trust region SQP-filter method for nonlinear second-order cone programming. Computers & Mathematics with Applications, 63(12):1569-1576,2012.
[167]P. Zhong and M. Fukushima. Second-order cone programming formulations for robust multiclass classification. Neural Computation,19(1):258-282,2007.