# American Institute of Mathematical Sciences

July  2013, 9(3): 703-721. doi: 10.3934/jimo.2013.9.703

## Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming

 1 School of Business Administration, Southwestern University of Finance and Economics, Chengdu, 611130, China 2 Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, United States, United States 3 Department of Mathematical Sciences, Tsinghua University, Beijing

Received  October 2012 Revised  February 2013 Published  April 2013

In this paper, we provide a computable representation of the cone of nonnegative quadratic forms over a general nontrivial second-order cone using linear matrix inequalities (LMI). By constructing a sequence of such computable cones over a union of second-order cones, an efficient algorithm is designed to find an approximate solution to a completely positive programming problem using semidefinite programming techniques. In order to accelerate the convergence of the approximation sequence, an adaptive scheme is adopted, and reformulation-linearization technique'' (RLT) constraints are added to further improve its efficiency.
Citation: Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
##### References:
 [1] K. Anstreicher, Semidefinite programming versus the Reformulation-Linearization Technique for nonconvex quadratically constrained quadratic programming,, Journal of Global Optimization, 43 (2009), 471. doi: 10.1007/s10898-008-9372-0. [2] A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,", SIAM, (2001). doi: 10.1137/1.9780898718829. [3] I. Bomze and E. de Klerk, Solving standard quadratic optimization problem via linear, semidefinite and copositive programming,, Journal of Global Optimization, 24 (2002), 163. doi: 10.1023/A:1020209017701. [4] I. Bomze and G. Eichfelder, Copositivity Detection by difference-of-convex decomposition and $\omega$-subdivision,, to appear in Mathematical Programming., (). doi: 10.1007/s10107-012-0543-x. [5] I. Bomze, F. Jarre and F. Rendl, Quadratic factorization heuristics for copositive programming,, Mathematical Programming Computation, 3 (2011), 37. doi: 10.1007/s12532-011-0022-z. [6] M. Brockington and J. Culberson, "Camouflaging Independent Sets in Quasi-random Graphs,", Clique Coloring and Satisfiability: Second DIMACS Implementation Challenge, 26 (1994). [7] S. Bundfuss and M. Dür, An adaptive linear approximation algorithm for copositive programs,, SIAM Journal on Optimization, 20 (2009), 30. doi: 10.1137/070711815. [8] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479. doi: 10.1007/s10107-008-0223-z. [9] S. Burer and K. Anstreicher, Second-order cone constraints for extended trust-region subproblems,, submitted to SIAM Journal on Optimization, (2011). doi: 10.1137/110826862. [10] Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme,, accepted by European Journal of Operational Research, (2013). doi: 10.1016/j.ejor.2013.02.031. [11] , DIMACS Implementation Challenges., , (). [12] M. Dür, "Copositive Programming: A Survey,", Recent Advances in Optimization and Its Application in Engineering, (2012). [13] N. Govozdenovic and M. Laurent, The operator $\Psi$ for the chromatic number of a graph,, SIAM Journal on Optimization, 19 (2008), 572. doi: 10.1137/050648237. [14] M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming,", version 1.2, (2010). [15] P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, Global minimization of indefinite quadratic functions subject to box constraints,, Naval Research Logistics, 40 (1993), 373. doi: 10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A. [16] K. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix,, Computational Mathematics and Mathmetical Physics, 42 (2002), 1701. [17] E. de Klerk and D. Pasechnik, Approximation of the stability number of a graph via copositive programming,, Journal of Global Optimization, 12 (2002), 875. doi: 10.1137/S1052623401383248. [18] C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, SIAM Journal on Optimization, 21 (2010), 1475. doi: 10.1137/100793955. [19] C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, An LMI based adaptive approximation scheme to cones of nonnegative quadratic functions,, Submitted to Mathematical Programming, (2011). [20] T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Turan,, Canadian Journal of Mathematics, 17 (1965), 533. doi: 10.4153/CJM-1965-053-6. [21] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117. doi: 10.1007/BF02592948. [22] J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem,, Discrete Optimization, 6 (2009), 231. doi: 10.1016/j.disopt.2009.01.002. [23] J. Preisig, Copositivity and the minimization of quadratic functions with nonnegativity and quadratic equality constraints,, SIAM Journal on Control and Optimization, 34 (1996), 1135. doi: 10.1137/S0363012993251894. [24] R. Rockafellar, "Convex Analysis,", Princeton University Press, (1996). [25] N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs,", 2010. , (). [26] L. Sanchis, Test case construction for the vertex cover problem,, in, 15 (1992). [27] J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones,, Optimization Methods and Software, 11$&$12 (1999), 625. doi: 10.1080/10556789908805766. [28] J. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. [29] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X. [30] J. Žilinskas, Copositive programming by simplicial partition,, Informatica, 22 (2011), 601.

show all references

##### References:
 [1] K. Anstreicher, Semidefinite programming versus the Reformulation-Linearization Technique for nonconvex quadratically constrained quadratic programming,, Journal of Global Optimization, 43 (2009), 471. doi: 10.1007/s10898-008-9372-0. [2] A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,", SIAM, (2001). doi: 10.1137/1.9780898718829. [3] I. Bomze and E. de Klerk, Solving standard quadratic optimization problem via linear, semidefinite and copositive programming,, Journal of Global Optimization, 24 (2002), 163. doi: 10.1023/A:1020209017701. [4] I. Bomze and G. Eichfelder, Copositivity Detection by difference-of-convex decomposition and $\omega$-subdivision,, to appear in Mathematical Programming., (). doi: 10.1007/s10107-012-0543-x. [5] I. Bomze, F. Jarre and F. Rendl, Quadratic factorization heuristics for copositive programming,, Mathematical Programming Computation, 3 (2011), 37. doi: 10.1007/s12532-011-0022-z. [6] M. Brockington and J. Culberson, "Camouflaging Independent Sets in Quasi-random Graphs,", Clique Coloring and Satisfiability: Second DIMACS Implementation Challenge, 26 (1994). [7] S. Bundfuss and M. Dür, An adaptive linear approximation algorithm for copositive programs,, SIAM Journal on Optimization, 20 (2009), 30. doi: 10.1137/070711815. [8] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Mathematical Programming, 120 (2009), 479. doi: 10.1007/s10107-008-0223-z. [9] S. Burer and K. Anstreicher, Second-order cone constraints for extended trust-region subproblems,, submitted to SIAM Journal on Optimization, (2011). doi: 10.1137/110826862. [10] Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme,, accepted by European Journal of Operational Research, (2013). doi: 10.1016/j.ejor.2013.02.031. [11] , DIMACS Implementation Challenges., , (). [12] M. Dür, "Copositive Programming: A Survey,", Recent Advances in Optimization and Its Application in Engineering, (2012). [13] N. Govozdenovic and M. Laurent, The operator $\Psi$ for the chromatic number of a graph,, SIAM Journal on Optimization, 19 (2008), 572. doi: 10.1137/050648237. [14] M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming,", version 1.2, (2010). [15] P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, Global minimization of indefinite quadratic functions subject to box constraints,, Naval Research Logistics, 40 (1993), 373. doi: 10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A. [16] K. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix,, Computational Mathematics and Mathmetical Physics, 42 (2002), 1701. [17] E. de Klerk and D. Pasechnik, Approximation of the stability number of a graph via copositive programming,, Journal of Global Optimization, 12 (2002), 875. doi: 10.1137/S1052623401383248. [18] C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, SIAM Journal on Optimization, 21 (2010), 1475. doi: 10.1137/100793955. [19] C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, An LMI based adaptive approximation scheme to cones of nonnegative quadratic functions,, Submitted to Mathematical Programming, (2011). [20] T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Turan,, Canadian Journal of Mathematics, 17 (1965), 533. doi: 10.4153/CJM-1965-053-6. [21] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117. doi: 10.1007/BF02592948. [22] J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem,, Discrete Optimization, 6 (2009), 231. doi: 10.1016/j.disopt.2009.01.002. [23] J. Preisig, Copositivity and the minimization of quadratic functions with nonnegativity and quadratic equality constraints,, SIAM Journal on Control and Optimization, 34 (1996), 1135. doi: 10.1137/S0363012993251894. [24] R. Rockafellar, "Convex Analysis,", Princeton University Press, (1996). [25] N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs,", 2010. , (). [26] L. Sanchis, Test case construction for the vertex cover problem,, in, 15 (1992). [27] J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones,, Optimization Methods and Software, 11$&$12 (1999), 625. doi: 10.1080/10556789908805766. [28] J. Sturm and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. [29] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245. doi: 10.1137/S105262340139001X. [30] J. Žilinskas, Copositive programming by simplicial partition,, Informatica, 22 (2011), 601.
 [1] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [2] Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 [3] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965 [4] Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [5] Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 [6] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [7] Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033 [8] Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial & Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945 [9] Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 [10] Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 [11] Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 [12] Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021 [13] Maurizio Grasselli, Morgan Pierre. Convergence to equilibrium of solutions of the backward Euler scheme for asymptotically autonomous second-order gradient-like systems. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2393-2416. doi: 10.3934/cpaa.2012.11.2393 [14] Johnny Henderson, Rodica Luca. Existence of positive solutions for a system of nonlinear second-order integral boundary value problems. Conference Publications, 2015, 2015 (special) : 596-604. doi: 10.3934/proc.2015.0596 [15] Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129 [16] Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871 [17] Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 [18] Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041 [19] José F. Cariñena, Javier de Lucas Araujo. Superposition rules and second-order Riccati equations. Journal of Geometric Mechanics, 2011, 3 (1) : 1-22. doi: 10.3934/jgm.2011.3.1 [20] Eugenii Shustin, Emilia Fridman, Leonid Fridman. Oscillations in a second-order discontinuous system with delay. Discrete & Continuous Dynamical Systems - A, 2003, 9 (2) : 339-358. doi: 10.3934/dcds.2003.9.339

2017 Impact Factor: 0.994