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

Metrics

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

Other articles
by authors

[Back to Top]