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.  Google Scholar [2] A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,", SIAM, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [6] M. Brockington and J. Culberson, "Camouflaging Independent Sets in Quasi-random Graphs,", Clique Coloring and Satisfiability: Second DIMACS Implementation Challenge, 26 (1994).   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [11] , DIMACS Implementation Challenges., , ().   Google Scholar [12] M. Dür, "Copositive Programming: A Survey,", Recent Advances in Optimization and Its Application in Engineering, (2012).   Google Scholar [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.  Google Scholar [14] M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming,", version 1.2, (2010).   Google Scholar [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.  Google Scholar [16] K. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix,, Computational Mathematics and Mathmetical Physics, 42 (2002), 1701.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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).   Google Scholar [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.  Google Scholar [21] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117.  doi: 10.1007/BF02592948.  Google Scholar [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.  Google Scholar [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.  Google Scholar [24] R. Rockafellar, "Convex Analysis,", Princeton University Press, (1996).   Google Scholar [25] N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs,", 2010. , ().   Google Scholar [26] L. Sanchis, Test case construction for the vertex cover problem,, in, 15 (1992).   Google Scholar [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.  Google Scholar [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.  Google Scholar [29] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245.  doi: 10.1137/S105262340139001X.  Google Scholar [30] J. Žilinskas, Copositive programming by simplicial partition,, Informatica, 22 (2011), 601.   Google Scholar

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.  Google Scholar [2] A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications,", SIAM, (2001).  doi: 10.1137/1.9780898718829.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [6] M. Brockington and J. Culberson, "Camouflaging Independent Sets in Quasi-random Graphs,", Clique Coloring and Satisfiability: Second DIMACS Implementation Challenge, 26 (1994).   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [11] , DIMACS Implementation Challenges., , ().   Google Scholar [12] M. Dür, "Copositive Programming: A Survey,", Recent Advances in Optimization and Its Application in Engineering, (2012).   Google Scholar [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.  Google Scholar [14] M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming,", version 1.2, (2010).   Google Scholar [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.  Google Scholar [16] K. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix,, Computational Mathematics and Mathmetical Physics, 42 (2002), 1701.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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).   Google Scholar [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.  Google Scholar [21] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117.  doi: 10.1007/BF02592948.  Google Scholar [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.  Google Scholar [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.  Google Scholar [24] R. Rockafellar, "Convex Analysis,", Princeton University Press, (1996).   Google Scholar [25] N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs,", 2010. , ().   Google Scholar [26] L. Sanchis, Test case construction for the vertex cover problem,, in, 15 (1992).   Google Scholar [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.  Google Scholar [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.  Google Scholar [29] Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245.  doi: 10.1137/S105262340139001X.  Google Scholar [30] J. Žilinskas, Copositive programming by simplicial partition,, Informatica, 22 (2011), 601.   Google Scholar
 [1] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [2] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [3] Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 [4] Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 [5] A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044 [6] Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 [7] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [8] Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 [9] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [10] Horst R. Thieme. Remarks on resolvent positive operators and their perturbation. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 73-90. doi: 10.3934/dcds.1998.4.73 [11] Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597 [12] Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810 [13] Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409 [14] Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009 [15] Marian Gidea, Rafael de la Llave, Tere M. Seara. A general mechanism of instability in Hamiltonian systems: Skipping along a normally hyperbolic invariant manifold. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6795-6813. doi: 10.3934/dcds.2020166 [16] Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 [17] Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044 [18] Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127 [19] Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $\Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109 [20] Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995

2019 Impact Factor: 1.366