非负二次函数锥规划
|
摘要
非负二次函数锥，即在给定的区域上全体非负的二次函数构成的锥，是经典的半正定锥及共正锥的扩展。由于任意二次规划问题均可转化为与其等价的非负二次函数锥规划问题。因此，对非负二次函数锥规划问题进行深入研究，可以进一步促进二次规划的发展。
在二次规划领域的传统研究方法中，拉格朗日对偶方法及半正定松弛方法是两类重要理论工具。然而这两类方法具有一定局限性。特别对于非凸情形，上述方法通常引入非零对偶间隙或松弛间隙。为了克服传统方法的局限性，本文将利用非负二次函数锥规划的理论与方法对二次规划进行研究。通过建立非负二次函数锥规划问题与二次规划问题拉格朗日乘子之间的理论联系，可以从线性锥规划的视角对二次规划问题的全局最优性条件，松弛算法，可解子类进行深入研究。基于这样的研究视角，本文提出了二次约束二次规划问题及0-1二次规划问题的新的全局最优性条件，该条件比以往文献中的半正定性条件更具一般性。同时，基于该条件，得到了一类可多项式时间求解的二次规划子类问题，从而扩大了问题的可解情形。在算法方面，为了有效求解非负二次函数锥规划问题，本文设计了自适应逼近策略。该策略可以根据问题数值特性自动地提高逼近效果。相关算法收敛性得到了证明，同时数值算例表明了其有效性。
本文的主要创新点包括：
通过建立非负二次函数锥规划与二次规划拉格朗日乘子之间的理论联系，提出了二次规划问题的新的全局最优性条件，该条件比以往文献中提到的半正定性条件更具一般性。
基于锥规划的方法，给出了二次规划问题的新的可多项式时间求解的子类问题，从而进一步扩展了二次规划问题的可多项式时间求解情形。
为了有效求解非负二次函数锥规划问题，设计了非负二次函数锥的可计算逼近策略。该策略对问题具有自适应性，即根据问题本身的数值特性，可自动地改进逼近效果。
Cone of nonnegative quadratic functions is the cone of all quadratic functionsbeing nonnegative over a given feasible set. It is an extension of the well-known posi-tive semidefinite cone and copositive cone. Any quadratic programming problem canbe transformed to a conic programming problem over cones of nonnegative quadraticfunctions. Hence, it can further improves the development in quadratic programmingby study the conic programming over cones of nonnegative quadratic functions.
In the literature, Lagrangian dual method and semidefinite relaxation method aretwo of the most important tools for studying quadratic programming. However, thesetwo methods have some limitations, especially for non-convex cases, they usually in-troduce a nonzero duality gap or slack gap. In order to overcome the limitations oftraditional methods, this thesis will use the theory of cones of nonnegative quadraticfunctions to study quadratic programming. In this thesis, we establish the theoreti-cal connections between programming problems over cones of nonnegative quadraticfunctions and quadratic programming problems, and then study the global optimal-ity conditions, solvable subclasses and relaxation methods of quadratic programmingfrom the view point of linear conic programming. Based on this research direction,we propose new global optimality conditions for quadratically constrained quadraticprogramming and0-1quadratic programming. These new conditions are more generalthan the positive semidefiniteness condition in the literature. We also propose a newpolynomial time solvable subclass of quadratic programming problems, which expandspreviously known solvable cases. To solve conic programming problems over cones ofnonnegative quadratic functions, we design an adaptive approximation scheme, whichcan automatically improve the approximation efectiveness based on the properties ofgiven problem instances. The convergence property of this scheme is proved. Somenumerical examples are shown to demonstrate the efectiveness of this scheme.
The main contributions of the thesis are:
By constructing the theoretical connections between conic programming prob-lems over cones of nonnegative quadratic functions and the Lagrangian multi-plier of quadratic programming problems, we propose a new global optimalitycondition, which is more general than the positive semidefiniteness condition inthe literature, for quadratic programming.
Based on the algorithms for conic programming, we propose a new algorithm tosolve a subclass of quadratic programming problems. This result extends previ-ously known solvable class to more general cases.
To solve the conic programming problems over cones of nonnegative quadraticfunctions, we design an adaptive approximation scheme, which can automati-cally improve the approximation efectiveness for given instances.
在二次规划领域的传统研究方法中，拉格朗日对偶方法及半正定松弛方法是两类重要理论工具。然而这两类方法具有一定局限性。特别对于非凸情形，上述方法通常引入非零对偶间隙或松弛间隙。为了克服传统方法的局限性，本文将利用非负二次函数锥规划的理论与方法对二次规划进行研究。通过建立非负二次函数锥规划问题与二次规划问题拉格朗日乘子之间的理论联系，可以从线性锥规划的视角对二次规划问题的全局最优性条件，松弛算法，可解子类进行深入研究。基于这样的研究视角，本文提出了二次约束二次规划问题及0-1二次规划问题的新的全局最优性条件，该条件比以往文献中的半正定性条件更具一般性。同时，基于该条件，得到了一类可多项式时间求解的二次规划子类问题，从而扩大了问题的可解情形。在算法方面，为了有效求解非负二次函数锥规划问题，本文设计了自适应逼近策略。该策略可以根据问题数值特性自动地提高逼近效果。相关算法收敛性得到了证明，同时数值算例表明了其有效性。
本文的主要创新点包括：
通过建立非负二次函数锥规划与二次规划拉格朗日乘子之间的理论联系，提出了二次规划问题的新的全局最优性条件，该条件比以往文献中提到的半正定性条件更具一般性。
基于锥规划的方法，给出了二次规划问题的新的可多项式时间求解的子类问题，从而进一步扩展了二次规划问题的可多项式时间求解情形。
为了有效求解非负二次函数锥规划问题，设计了非负二次函数锥的可计算逼近策略。该策略对问题具有自适应性，即根据问题本身的数值特性，可自动地改进逼近效果。
Cone of nonnegative quadratic functions is the cone of all quadratic functionsbeing nonnegative over a given feasible set. It is an extension of the well-known posi-tive semidefinite cone and copositive cone. Any quadratic programming problem canbe transformed to a conic programming problem over cones of nonnegative quadraticfunctions. Hence, it can further improves the development in quadratic programmingby study the conic programming over cones of nonnegative quadratic functions.
In the literature, Lagrangian dual method and semidefinite relaxation method aretwo of the most important tools for studying quadratic programming. However, thesetwo methods have some limitations, especially for non-convex cases, they usually in-troduce a nonzero duality gap or slack gap. In order to overcome the limitations oftraditional methods, this thesis will use the theory of cones of nonnegative quadraticfunctions to study quadratic programming. In this thesis, we establish the theoreti-cal connections between programming problems over cones of nonnegative quadraticfunctions and quadratic programming problems, and then study the global optimal-ity conditions, solvable subclasses and relaxation methods of quadratic programmingfrom the view point of linear conic programming. Based on this research direction,we propose new global optimality conditions for quadratically constrained quadraticprogramming and0-1quadratic programming. These new conditions are more generalthan the positive semidefiniteness condition in the literature. We also propose a newpolynomial time solvable subclass of quadratic programming problems, which expandspreviously known solvable cases. To solve conic programming problems over cones ofnonnegative quadratic functions, we design an adaptive approximation scheme, whichcan automatically improve the approximation efectiveness based on the properties ofgiven problem instances. The convergence property of this scheme is proved. Somenumerical examples are shown to demonstrate the efectiveness of this scheme.
The main contributions of the thesis are:
By constructing the theoretical connections between conic programming prob-lems over cones of nonnegative quadratic functions and the Lagrangian multi-plier of quadratic programming problems, we propose a new global optimalitycondition, which is more general than the positive semidefiniteness condition inthe literature, for quadratic programming.
Based on the algorithms for conic programming, we propose a new algorithm tosolve a subclass of quadratic programming problems. This result extends previ-ously known solvable class to more general cases.
To solve the conic programming problems over cones of nonnegative quadraticfunctions, we design an adaptive approximation scheme, which can automati-cally improve the approximation efectiveness for given instances.
引文
1此处提到的多项式时间算法并不是严格意义的多项式时间算法。实际上，对矩阵M非常接近Ci边界的情形，在有限数值精度下，判定算法的正确性都难以保证。然而，该判定问题通常可以转化为等价的优化问题，并根据该优化问题的最优值是否非负来判定M∈Ci是否成立。因此采用如下意义的多项式时间判定算法：若相关的优化问题可多项式时间求解，则称M∈Ci可多项式时间判定。
[1] Sturm J, Zhang S. On cones of nonnegative quadratic functions. Mathematics of OperationsResearch,2003,28:246–267.
[2] Mulvey J. Introduction to financial optimization: Mathematical Programming Special Issue.Mathematical Programming,2001,89:205–216.
[3] Burges C. A tutorial on support vector machines for pattern recognition. Data Mining andKnowledge Discovery,1998,2:121–167.
[4] Cho J D, Raje S, Sarrafzadeh M. Fast approximation algorithms on maxcut, k-coloring, andk-color ordering for VLSI applications. IEEE Transactions on Computers,1998,47:1253–1266.
[5] Horst R, Pardalos P, Thoai N. Introduction to global optimization. Norwell, MA: Kluwer,1995.
[6] Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman,1979.
[7] Kabadi S, Murty K. Some NP-complete problems in quadratic and nonlinear programming.Mathematical Programming,1987,39:117–129.
[8] Pardalos P M, Rodgers G. Computational aspects of a branch and bound algorithm forquadratic zero-one programming. Computing,1990,45:131–144.
[9] Lemarechal C, Oustry F. SDP relaxations in combinatorial optimization from a Lagrangianpoint of view. In: Hadjisavvas N, Pardalos P,(eds.). Proceedings of Advances in ConvexAnalysis and Global Optimization. Netherlands: Kluwer,2001:119–134.
[10] Ye Y. Interior Point Algorithms: Theory and Analysis. New Yokr: John Wiley&Sons,1997.
[11] Nesterov Y, Nemirovsky A. Interior-Point Polynomial Methods in Convex Programming.Philadelphia, PA: SIAM,1994.
[12] Goemans M, Williamson D. Improved approximation algorithms for maximum cut and sat-isfiability problems using semidefinite programming. Journal of the ACM,1995,42:1115–1145.
[13] Billionnet A, Elloumi S. Using a mixed integer quadratic programming solver for the un-constrained quadratic0-1problem. Mathematical Programming,2007,109:55–68.
[14] Poljak S, Wolkowicz H. Convex relaxations of (0-1) quadratic programming. Mathematicsof Operation Research,1995,20:550–561.
[15] de Klerk E. Aspects of Semidefinite Programming: Interior Point Algorithms and SelectedApplications. Dordrecht: Kluwer,2002.
[16] Wolkowicz H, Saigal R, Vandenberghe L e. Handbook of Semidefinite Programming: The-ory, Algorithms and Applications. Boston, MA: Kluwer Academic Publishers,2000.
[17] Sun X, Liu C, Li D, et al. On duality gap in binary quadratic programming. Journal ofGlobal Optimization, to appear.
[18] Malik U, Jaimoukha I, Halikias G, et al. On the gap between the quadratic integer program-ming problem and its semidefinite relaxation. Mathematical Programming,2006,107:505–515.
[19] Halikias G, Jaimoukha I, Malik U, et al. New bounds on the unconstrained quadratic integerproblem. Journal of Global Optimization,2007,39:543–554.
[20] Lu C, Wang Z, Xing W. An improved lower bound and approximation algorithm for bi-nary constrained quadratic programming problem. Journal of Global Optimizationh,2010,48:497–508.
[21] Sherali H, Liberti L. Reformulation-Linearization methods for global optimization. Tech-nical report,2007. http://www.lix.polytechnique.fr/～liberti/rlt encopt2.pdf.
[22] Adams W P, Sherali H D. A tight linearization and an algorithm for zero-one quadraticprogramming problems. Management Science,1986,32:1274–1290.
[23] Adams W P, Sherali H D. Linearization strategies for a class of zero-one mixed integerprogramming problems. Operations Research,1990,38:217–226.
[24] Adams W P, Sherali H D. A hierarchy of relaxations leading to the convex hull represen-tation for general discrete optimization problems. Annals of Operations Research,2005,140:21–47.
[25] Sherali H D, Alameddine A. A new reformulation-linearization technique for solving bilin-ear programming problems. Journal of Global Optimizationh,1992,2:379–410.
[26] Sherali H D, Alameddine A. A global optimization algorithm for polynomial programmingproblems using a reformulation-linearization technique. Journal of Global Optimizationh,1992,2:101–112.
[27] Sun X, Li J, Luo H. Convex relaxation and Lagrangian decomposition for indefinite integerquadratic programming. Optimization,2010,59:621–647.
[28] Billionnet A, Elloumi S,, et al. Quadratic0-1programming: tightening linear or quadraticconvex reformulation by use of relaxations. RAIRO-Operations Research,2008,42:103–121.
[29] Bomze I, Locatelli M, Tardella F. New and old bounds for standard quadratic optimization:dominance, equivalence and incomparability. Mathematical Programming,2008,115:31–64.
[30] Anstreicher K. Semidefinite programming versus the reformulation-linearization techniquefor nonconvex quadratically constrained quadratic programming. Journal of Global Opti-mization,2009,43:471–484.
[31] Ahuja R, Magnanti T, Orlin J. Network Flows: Theory, Algorithms, and Applications. NewJersey: Prentice Hall,1993.
[32] Lobo M, Vandenberghe L, Boyd S, et al. Applications of second-order cone programming.Linear Algebra and its Applications,1998,284:193–228.
[33] Yuan Y. On a subproblem of trust region algorithms for constrained optimization. Mathe-matical Programming,1990,47:53–63.
[34] Ye Y. On afne scaling algorithms for nonconvex quadratic programming. MathematicalProgramming,1992,56:285–300.
[35] Stern R, Wolkowicz H. Indefinite trust region subproblems and nonsymmetric eigenvalueperturbations. SIAM Journal on Optimization,1995,5:286–313.
[36] Jin Q, Fang S, Xing W. On the global optimality of generalized trust region subproblems.Optimization,2010,59:1139–1151.
[37] Ye Y, Zhang S. New results on quadratic minimization. SIAM Journal on Optimization,2003,14:245–267.
[38] Edelsburunner H. Algorithms in Combinatorial Geometry. Berlin, German: Springer,1987.
[39] Allemand K, Fukuda K, Liebling T, et al. A polynomial case of unconstrained zero-onequadratic optimization. Mathematical Programming,2001,91:49–52.
[40] Avis D, Fukuda K. Reverse search for enumeration. Discrete Applied Mathematics,1996,65:21–46.
[41] Picard J, Ratlif H. Minimum cuts and related problems. Networks,1974,5:357–370.
[42] Gao D. Canonical dual transformation method and generalized triality theory in nonsmoothglobal optimization. Journal of Global Optimization,2000,17:127–160.
[43] Fang S C, Gao D, Sheu R L, et al. Canonical dual approach to solving0-1quadratic pro-gramming problem. Journal of Industrial and Management Optimization,2007,3:125–142.
[44] Bomze I, de Klerk E. Solving standard quadratic optimization problems via linear, semidef-inite and copositive programming. Journal of Global Optimization,2002,24:163–185.
[45] Bomze I, Du¨r M, de Klerk E, et al. On copositive programming and standard quadraticoptimization problems. Journal of Global Optimization,2000,18:301–320.
[46] Bomze I, Palagi L. Quartic formulation of standard quadratic optimization problems. Jour-nal of Global Optimization,2005,32:181–205.
[47] de Klerk E, Pasechnik D. A linear programming reformulation of the standard quadraticoptimization problem. Journal of Global Optimization,2007,37:75–84.
[48] Quist A, de Klerk E, Roos C, et al. Copositive relaxation for general quadratic programming.Optimization Methods Software,1998,9:185–208.
[49] Burer S. On the copositive representation of binary and continuous nonconvex quadraticprograms. Mathematical Programming,2009,120:479–495.
[50] de Klerk E, Pasechnik D. Approximation of the stability number of a graph via copositiveprogramming. SIAM Journal on Optimization,2002,12:875–892.
[51] Dukanovic I, Rendl F. Copositive programming motivated bounds on the stability and thechromatic numbers. Mathematical Programming,2009,121:249–268.
[52] Povh J, Rendl F. A copositive programming approach to graph partitioning. SIAM Journalon Optimization,2007,18:223–241.
[53] Du¨r M. Copositive programming-a survey. Technical report,2009.http://www.optimization-online.org/DB FILE/2009/11/2464.pdf.
[54] Parrilo P. Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Ro-bustness and Optimization[D]. USA: California Institute of Technology, May,2000.
[55] Parrilo P. Semidefinite programming relaxations for semialgebraic problems. MathematicalProgramming,2003,96:293–320.
[56] Bundfuss S, Du¨r M. An adaptive linear approximation algorithm for copositive programs.SIAM Journal on Optimization,2009,20:30–53.
[57] Zuluage L, Vera J, Pena J. LMI approximations for cones of positive semidefinite forms.SIAM Journal on Optimization,2006,16:1076–1091.
[58] Boyd S, Ghaoui L, Feron E, et al. Linear Matrix Inequalities in System and Control Theory.Philadelphia: SIAM,1994.
[59] Bundfuss S, Du¨r M. Algorithmic copositivity detection by simplicial partition. LinearAlgebra and Its Application,2008,428:1511–1523.
[60] Danninger G. Role of copositivity in optimality criteria for nonconvex optimization prob-lems. Journal of Optimization Theory and Application,1992,75:535–558.
[61] Danninger G, Bomze I. Using copositivity for global optimality criteria in concave quadraticprogramming problems. Mathematical Programming,1993,62:575–580.
[62] Li P, Feng Y. Criteria for copositive matrices of order four. Linear Algebra and itsApplica-tion,1993,194:109–124.
[63] Burer S, Anstreicher K, Du¨r M. The diference between5×5doubly nonnegative andcompletely positive matrices. Linear Algoebra and its Application,2009,431:1539–1552.
[64] Hiriart-Urruty J B, Seeger A. A variational approach to copositive matrices. SIAM Review,2010,52:593–629.
[65] Rockafellar R. Convex Analysis. Princeton: Princeton University Press,1970.
[66] Ben-Tal A, Nemirovski A. Lectures on Modern Convex Optimization, Analysis, Algorithmsand Engineering Applications. Philadelphia: SIAM,2001.
[67] Lasserre J. Global optimization with polynomials and the problem of moments. SIAMJournal on Optimization,2001,11:796–817.
[68] Putinar M. Positive polynomials on compact semi-algebraic sets. Indiana University Math-ematics Journal,1999,42:969–984.
[69] Jacobi T. A representation theorem for certain partially ordered commutative rings. Mathe-matische Zeitschrift,2001,237:259–273.
[70] Bazaraa M, Sherali H, Shetty C. Nonlinear Programming: Theory and Algorithms. Hobo-ken, NJ: John Wiley&Sons Inc.,2006.
[71] Jeyakumar V, Rubinov A, Wu Z. Non-convex quadratic minimization problems withquadratic constraints: Global optimality conditions. Mathematical Programming,2007,110:521–541.
[72] Gao D. Advances in canonical duality theory with applications to global optimization. Pro-ceedings of Proceedings of the Fifth International Conference on Foundations of Computer-Aided Process Operations (FOCAPO2008),2008.
[73] Peng J M, Yuan Y. Optimality conditions for the minimization of a quadratic with twoquadratic constraints. SIAM Journal on Optimization,1997,7:579–594.
[74] Bomze I. Copositivity conditions for global optimality in indefinite quadratic programmingproblems. Czechoslovak Journal for Operations Research,1992,1:7–19.
[75] Fang S C, Gao D, Sheu R L, et al. Global optimization for a class of fractional programmingproblems. Journal of Global Optimization,2009,45:337–353.
[76] Wang Z, Fang S C, Gao D, et al. Global extremal conditions for multi-integer quadraticprogramming. Journal of Industrial and Management Optimization,2008,4:213–225.
[77] Xing W, Fang S C, Gao D, et al. Canonical duality solutions to quadratic programming overa quadratic constraint. Proceedings of Proceedings of ICOTA7, Japan,2007.
[78] Lu C, Wang Z, Xing W, et al. Extended canonical duality and conic programming for solving0-1quadratic programming problems. Journal of Industrial and Management Optimization,2010,6:779–793.
[79] Rendl F, Wolkowicz H. A semidefinite framework for trust region subproblems with appli-cations to large scale minimization. Mathematical Programming,1997,77:273–299.
[80] Fu M, Luo Z, Ye Y. Approximation algorithms for quadratic programming. Journal ofCombinatorial Optimization,1998,2:29–50.
[81] Pardalos P, Vavasis S. Quadratic programming with one negative eigenvalue is NP-Hard.Journal of Global Optimization,1991,1:15–22.
[1] Sturm J, Zhang S. On cones of nonnegative quadratic functions. Mathematics of OperationsResearch,2003,28:246–267.
[2] Mulvey J. Introduction to financial optimization: Mathematical Programming Special Issue.Mathematical Programming,2001,89:205–216.
[3] Burges C. A tutorial on support vector machines for pattern recognition. Data Mining andKnowledge Discovery,1998,2:121–167.
[4] Cho J D, Raje S, Sarrafzadeh M. Fast approximation algorithms on maxcut, k-coloring, andk-color ordering for VLSI applications. IEEE Transactions on Computers,1998,47:1253–1266.
[5] Horst R, Pardalos P, Thoai N. Introduction to global optimization. Norwell, MA: Kluwer,1995.
[6] Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman,1979.
[7] Kabadi S, Murty K. Some NP-complete problems in quadratic and nonlinear programming.Mathematical Programming,1987,39:117–129.
[8] Pardalos P M, Rodgers G. Computational aspects of a branch and bound algorithm forquadratic zero-one programming. Computing,1990,45:131–144.
[9] Lemarechal C, Oustry F. SDP relaxations in combinatorial optimization from a Lagrangianpoint of view. In: Hadjisavvas N, Pardalos P,(eds.). Proceedings of Advances in ConvexAnalysis and Global Optimization. Netherlands: Kluwer,2001:119–134.
[10] Ye Y. Interior Point Algorithms: Theory and Analysis. New Yokr: John Wiley&Sons,1997.
[11] Nesterov Y, Nemirovsky A. Interior-Point Polynomial Methods in Convex Programming.Philadelphia, PA: SIAM,1994.
[12] Goemans M, Williamson D. Improved approximation algorithms for maximum cut and sat-isfiability problems using semidefinite programming. Journal of the ACM,1995,42:1115–1145.
[13] Billionnet A, Elloumi S. Using a mixed integer quadratic programming solver for the un-constrained quadratic0-1problem. Mathematical Programming,2007,109:55–68.
[14] Poljak S, Wolkowicz H. Convex relaxations of (0-1) quadratic programming. Mathematicsof Operation Research,1995,20:550–561.
[15] de Klerk E. Aspects of Semidefinite Programming: Interior Point Algorithms and SelectedApplications. Dordrecht: Kluwer,2002.
[16] Wolkowicz H, Saigal R, Vandenberghe L e. Handbook of Semidefinite Programming: The-ory, Algorithms and Applications. Boston, MA: Kluwer Academic Publishers,2000.
[17] Sun X, Liu C, Li D, et al. On duality gap in binary quadratic programming. Journal ofGlobal Optimization, to appear.
[18] Malik U, Jaimoukha I, Halikias G, et al. On the gap between the quadratic integer program-ming problem and its semidefinite relaxation. Mathematical Programming,2006,107:505–515.
[19] Halikias G, Jaimoukha I, Malik U, et al. New bounds on the unconstrained quadratic integerproblem. Journal of Global Optimization,2007,39:543–554.
[20] Lu C, Wang Z, Xing W. An improved lower bound and approximation algorithm for bi-nary constrained quadratic programming problem. Journal of Global Optimizationh,2010,48:497–508.
[21] Sherali H, Liberti L. Reformulation-Linearization methods for global optimization. Tech-nical report,2007. http://www.lix.polytechnique.fr/～liberti/rlt encopt2.pdf.
[22] Adams W P, Sherali H D. A tight linearization and an algorithm for zero-one quadraticprogramming problems. Management Science,1986,32:1274–1290.
[23] Adams W P, Sherali H D. Linearization strategies for a class of zero-one mixed integerprogramming problems. Operations Research,1990,38:217–226.
[24] Adams W P, Sherali H D. A hierarchy of relaxations leading to the convex hull represen-tation for general discrete optimization problems. Annals of Operations Research,2005,140:21–47.
[25] Sherali H D, Alameddine A. A new reformulation-linearization technique for solving bilin-ear programming problems. Journal of Global Optimizationh,1992,2:379–410.
[26] Sherali H D, Alameddine A. A global optimization algorithm for polynomial programmingproblems using a reformulation-linearization technique. Journal of Global Optimizationh,1992,2:101–112.
[27] Sun X, Li J, Luo H. Convex relaxation and Lagrangian decomposition for indefinite integerquadratic programming. Optimization,2010,59:621–647.
[28] Billionnet A, Elloumi S,, et al. Quadratic0-1programming: tightening linear or quadraticconvex reformulation by use of relaxations. RAIRO-Operations Research,2008,42:103–121.
[29] Bomze I, Locatelli M, Tardella F. New and old bounds for standard quadratic optimization:dominance, equivalence and incomparability. Mathematical Programming,2008,115:31–64.
[30] Anstreicher K. Semidefinite programming versus the reformulation-linearization techniquefor nonconvex quadratically constrained quadratic programming. Journal of Global Opti-mization,2009,43:471–484.
[31] Ahuja R, Magnanti T, Orlin J. Network Flows: Theory, Algorithms, and Applications. NewJersey: Prentice Hall,1993.
[32] Lobo M, Vandenberghe L, Boyd S, et al. Applications of second-order cone programming.Linear Algebra and its Applications,1998,284:193–228.
[33] Yuan Y. On a subproblem of trust region algorithms for constrained optimization. Mathe-matical Programming,1990,47:53–63.
[34] Ye Y. On afne scaling algorithms for nonconvex quadratic programming. MathematicalProgramming,1992,56:285–300.
[35] Stern R, Wolkowicz H. Indefinite trust region subproblems and nonsymmetric eigenvalueperturbations. SIAM Journal on Optimization,1995,5:286–313.
[36] Jin Q, Fang S, Xing W. On the global optimality of generalized trust region subproblems.Optimization,2010,59:1139–1151.
[37] Ye Y, Zhang S. New results on quadratic minimization. SIAM Journal on Optimization,2003,14:245–267.
[38] Edelsburunner H. Algorithms in Combinatorial Geometry. Berlin, German: Springer,1987.
[39] Allemand K, Fukuda K, Liebling T, et al. A polynomial case of unconstrained zero-onequadratic optimization. Mathematical Programming,2001,91:49–52.
[40] Avis D, Fukuda K. Reverse search for enumeration. Discrete Applied Mathematics,1996,65:21–46.
[41] Picard J, Ratlif H. Minimum cuts and related problems. Networks,1974,5:357–370.
[42] Gao D. Canonical dual transformation method and generalized triality theory in nonsmoothglobal optimization. Journal of Global Optimization,2000,17:127–160.
[43] Fang S C, Gao D, Sheu R L, et al. Canonical dual approach to solving0-1quadratic pro-gramming problem. Journal of Industrial and Management Optimization,2007,3:125–142.
[44] Bomze I, de Klerk E. Solving standard quadratic optimization problems via linear, semidef-inite and copositive programming. Journal of Global Optimization,2002,24:163–185.
[45] Bomze I, Du¨r M, de Klerk E, et al. On copositive programming and standard quadraticoptimization problems. Journal of Global Optimization,2000,18:301–320.
[46] Bomze I, Palagi L. Quartic formulation of standard quadratic optimization problems. Jour-nal of Global Optimization,2005,32:181–205.
[47] de Klerk E, Pasechnik D. A linear programming reformulation of the standard quadraticoptimization problem. Journal of Global Optimization,2007,37:75–84.
[48] Quist A, de Klerk E, Roos C, et al. Copositive relaxation for general quadratic programming.Optimization Methods Software,1998,9:185–208.
[49] Burer S. On the copositive representation of binary and continuous nonconvex quadraticprograms. Mathematical Programming,2009,120:479–495.
[50] de Klerk E, Pasechnik D. Approximation of the stability number of a graph via copositiveprogramming. SIAM Journal on Optimization,2002,12:875–892.
[51] Dukanovic I, Rendl F. Copositive programming motivated bounds on the stability and thechromatic numbers. Mathematical Programming,2009,121:249–268.
[52] Povh J, Rendl F. A copositive programming approach to graph partitioning. SIAM Journalon Optimization,2007,18:223–241.
[53] Du¨r M. Copositive programming-a survey. Technical report,2009.http://www.optimization-online.org/DB FILE/2009/11/2464.pdf.
[54] Parrilo P. Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Ro-bustness and Optimization[D]. USA: California Institute of Technology, May,2000.
[55] Parrilo P. Semidefinite programming relaxations for semialgebraic problems. MathematicalProgramming,2003,96:293–320.
[56] Bundfuss S, Du¨r M. An adaptive linear approximation algorithm for copositive programs.SIAM Journal on Optimization,2009,20:30–53.
[57] Zuluage L, Vera J, Pena J. LMI approximations for cones of positive semidefinite forms.SIAM Journal on Optimization,2006,16:1076–1091.
[58] Boyd S, Ghaoui L, Feron E, et al. Linear Matrix Inequalities in System and Control Theory.Philadelphia: SIAM,1994.
[59] Bundfuss S, Du¨r M. Algorithmic copositivity detection by simplicial partition. LinearAlgebra and Its Application,2008,428:1511–1523.
[60] Danninger G. Role of copositivity in optimality criteria for nonconvex optimization prob-lems. Journal of Optimization Theory and Application,1992,75:535–558.
[61] Danninger G, Bomze I. Using copositivity for global optimality criteria in concave quadraticprogramming problems. Mathematical Programming,1993,62:575–580.
[62] Li P, Feng Y. Criteria for copositive matrices of order four. Linear Algebra and itsApplica-tion,1993,194:109–124.
[63] Burer S, Anstreicher K, Du¨r M. The diference between5×5doubly nonnegative andcompletely positive matrices. Linear Algoebra and its Application,2009,431:1539–1552.
[64] Hiriart-Urruty J B, Seeger A. A variational approach to copositive matrices. SIAM Review,2010,52:593–629.
[65] Rockafellar R. Convex Analysis. Princeton: Princeton University Press,1970.
[66] Ben-Tal A, Nemirovski A. Lectures on Modern Convex Optimization, Analysis, Algorithmsand Engineering Applications. Philadelphia: SIAM,2001.
[67] Lasserre J. Global optimization with polynomials and the problem of moments. SIAMJournal on Optimization,2001,11:796–817.
[68] Putinar M. Positive polynomials on compact semi-algebraic sets. Indiana University Math-ematics Journal,1999,42:969–984.
[69] Jacobi T. A representation theorem for certain partially ordered commutative rings. Mathe-matische Zeitschrift,2001,237:259–273.
[70] Bazaraa M, Sherali H, Shetty C. Nonlinear Programming: Theory and Algorithms. Hobo-ken, NJ: John Wiley&Sons Inc.,2006.
[71] Jeyakumar V, Rubinov A, Wu Z. Non-convex quadratic minimization problems withquadratic constraints: Global optimality conditions. Mathematical Programming,2007,110:521–541.
[72] Gao D. Advances in canonical duality theory with applications to global optimization. Pro-ceedings of Proceedings of the Fifth International Conference on Foundations of Computer-Aided Process Operations (FOCAPO2008),2008.
[73] Peng J M, Yuan Y. Optimality conditions for the minimization of a quadratic with twoquadratic constraints. SIAM Journal on Optimization,1997,7:579–594.
[74] Bomze I. Copositivity conditions for global optimality in indefinite quadratic programmingproblems. Czechoslovak Journal for Operations Research,1992,1:7–19.
[75] Fang S C, Gao D, Sheu R L, et al. Global optimization for a class of fractional programmingproblems. Journal of Global Optimization,2009,45:337–353.
[76] Wang Z, Fang S C, Gao D, et al. Global extremal conditions for multi-integer quadraticprogramming. Journal of Industrial and Management Optimization,2008,4:213–225.
[77] Xing W, Fang S C, Gao D, et al. Canonical duality solutions to quadratic programming overa quadratic constraint. Proceedings of Proceedings of ICOTA7, Japan,2007.
[78] Lu C, Wang Z, Xing W, et al. Extended canonical duality and conic programming for solving0-1quadratic programming problems. Journal of Industrial and Management Optimization,2010,6:779–793.
[79] Rendl F, Wolkowicz H. A semidefinite framework for trust region subproblems with appli-cations to large scale minimization. Mathematical Programming,1997,77:273–299.
[80] Fu M, Luo Z, Ye Y. Approximation algorithms for quadratic programming. Journal ofCombinatorial Optimization,1998,2:29–50.
[81] Pardalos P, Vavasis S. Quadratic programming with one negative eigenvalue is NP-Hard.Journal of Global Optimization,1991,1:15–22.