- Previous Article
- JIMO Home
- This Issue
-
Next Article
Convex hull of the orthogonal similarity set with applications in quadratic assignment problems
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 |
References:
[1] |
K. Anstreicher, Semidefinite programming versus the Reformulation-Linearization Technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484.
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, Philadelphis, 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-185.
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-57.
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, Amer Mathematical Society, 1994. |
[7] |
S. Bundfuss and M. Dür, An adaptive linear approximation algorithm for copositive programs, SIAM Journal on Optimization, 20 (2009), 30-53.
doi: 10.1137/070711815. |
[8] |
S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.
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. ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique |
[12] |
M. Dür, "Copositive Programming: A Survey," Recent Advances in Optimization and Its Application in Engineering, Springer, New York, 2012. |
[13] |
N. Govozdenovic and M. Laurent, The operator $\Psi$ for the chromatic number of a graph, SIAM Journal on Optimization, 19 (2008), 572-591.
doi: 10.1137/050648237. |
[14] |
M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming," version 1.2, 2010. http://cvxr.com/cvx |
[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-392.
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-1703. |
[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-892.
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-1490.
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-540.
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-129.
doi: 10.1007/BF02592948. |
[22] |
J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimization, 6 (2009), 231-241.
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-1150.
doi: 10.1137/S0363012993251894. |
[24] |
R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1996. |
[25] |
N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs," 2010. http://archimedes.cheme.cmu.edu/baron/baron.html |
[26] |
L. Sanchis, Test case construction for the vertex cover problem, in "Computational Support for Discrete Mathematics," DIMACS Series in Discrete Mathematics and Theoretical American Mathematical Society, 15 (1992), Providence, Rhodle Island, (1992). |
[27] |
J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones, Optimization Methods and Software, 11&12 (1999), 625-653.
doi: 10.1080/10556789908805766. |
[28] |
J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
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-267.
doi: 10.1137/S105262340139001X. |
[30] |
J. Žilinskas, Copositive programming by simplicial partition, Informatica, 22 (2011), 601-614. |
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-484.
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, Philadelphis, 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-185.
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-57.
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, Amer Mathematical Society, 1994. |
[7] |
S. Bundfuss and M. Dür, An adaptive linear approximation algorithm for copositive programs, SIAM Journal on Optimization, 20 (2009), 30-53.
doi: 10.1137/070711815. |
[8] |
S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.
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. ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique |
[12] |
M. Dür, "Copositive Programming: A Survey," Recent Advances in Optimization and Its Application in Engineering, Springer, New York, 2012. |
[13] |
N. Govozdenovic and M. Laurent, The operator $\Psi$ for the chromatic number of a graph, SIAM Journal on Optimization, 19 (2008), 572-591.
doi: 10.1137/050648237. |
[14] |
M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming," version 1.2, 2010. http://cvxr.com/cvx |
[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-392.
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-1703. |
[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-892.
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-1490.
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-540.
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-129.
doi: 10.1007/BF02592948. |
[22] |
J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimization, 6 (2009), 231-241.
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-1150.
doi: 10.1137/S0363012993251894. |
[24] |
R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1996. |
[25] |
N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs," 2010. http://archimedes.cheme.cmu.edu/baron/baron.html |
[26] |
L. Sanchis, Test case construction for the vertex cover problem, in "Computational Support for Discrete Mathematics," DIMACS Series in Discrete Mathematics and Theoretical American Mathematical Society, 15 (1992), Providence, Rhodle Island, (1992). |
[27] |
J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones, Optimization Methods and Software, 11&12 (1999), 625-653.
doi: 10.1080/10556789908805766. |
[28] |
J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
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-267.
doi: 10.1137/S105262340139001X. |
[30] |
J. Žilinskas, Copositive programming by simplicial partition, Informatica, 22 (2011), 601-614. |
[1] |
Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 |
[7] |
Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 |
[8] |
Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050 |
[9] |
Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 |
[10] |
Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021032 |
[11] |
Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033 |
[12] |
Xiaoling Guo, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing. Quadratic optimization over one first-order cone. Journal of Industrial and Management Optimization, 2014, 10 (3) : 945-963. doi: 10.3934/jimo.2014.10.945 |
[13] |
Guanrong Li, Yanping Chen, Yunqing Huang. A hybridized weak Galerkin finite element scheme for general second-order elliptic problems. Electronic Research Archive, 2020, 28 (2) : 821-836. doi: 10.3934/era.2020042 |
[14] |
Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial and Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 |
[15] |
Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040 |
[16] |
Fasma Diele, Angela Martiradonna, Catalin Trenchea. Stability and errors estimates of a second-order IMSP scheme. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022076 |
[17] |
Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 |
[18] |
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 and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 |
[19] |
Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021 |
[20] |
Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]