American Institute of Mathematical Sciences

Advanced
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

Ye Tian 1, , Shu-Cherng Fang 2, , Zhibin Deng 2, and  Wenxun Xing 3,

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.
Keywords: Cone of nonnegative quadratic forms general nontrivial second-order cone completely positive programming approximation adaptive scheme..
Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E1.
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

Tools

Metrics

  • PDF downloads (96)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences