-
Previous Article
Externality of contracts on supply chains with two suppliers and a common retailer
- JIMO Home
- This Issue
-
Next Article
Optimal financing and dividend strategies in a dual model with proportional costs
Extended canonical duality and conic programming for solving 0-1 quadratic programming problems
1. | Department of Mathematical Sciences, Tsinghua University, Beijing, China |
2. | Department of Industrial and System Engineering, North Carolina State University, Raleigh, NC 27695, United States |
References:
[1] |
K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization, Mathematical Programming, 91 (2001), 49-52. |
[2] |
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. |
[3] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problem, J. Industrial and Management Optimization, 3 (2007), 125-142. |
[4] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and W. Xing, Global optimization for a class of fractional programming problems, J. Global Optimization, 45 (2009), 337-353.
doi: 10.1007/s10898-008-9378-7. |
[5] |
D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optimization, 17 (2000), 127-160.
doi: 10.1023/A:1026537630859. |
[6] |
D. Y. Gao, Advances in canonical duality theory with applications to global optimization, available at: http://www.math.vt.edu/people/gao/papers/focapo08.pdf. |
[7] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman, San Francisco, CA, 1979. |
[8] |
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), 1115-1145.
doi: 10.1145/227683.227684. |
[9] |
V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Mathematical Programming, 110 (2007), 521-541.
doi: 10.1007/s10107-006-0012-5. |
[10] |
Q. Jin, S.-C. Fang and W. Xing, On the global optimality of generalized trust region subproblems, Optimization.
doi: DOI:10.1080/02331930902995236. |
[11] |
E. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optimization, 12 (2002), 875-892.
doi: 10.1137/S1052623401383248. |
[12] |
C. Lu, Z. Wang and W. Xing, An improved lower bound and approximation algorithm for binary constrained quadratic programming problem, J. Global Optimization.
doi: DOI: 10.1007/s10898-009-9504-1. |
[13] |
A. Ben-Israel and T. N. E. Greville, "Generalized Inverses," Springer-Verlag, 2003. |
[14] |
P. M. Pardalos and G. P. Rodgers, Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144.
doi: 10.1007/BF02247879. |
[15] |
J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[16] |
X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, aviable at: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf. |
[17] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming, J. Industrial and Management Optimization, 4 (2008), 213-225. |
[18] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Canonical dual approach to solving the maximum cut problem, Working Paper, to appear in J. Global Optimization. |
[19] |
L. A. Wolsey, "Integer Programming," Wiley-Interscience, 1998. |
[20] |
W. Xing, S.-C. Fang, D. Y. Gao and L. Zhang, Canonical duality solutions to quadratic programming over a quadratic constraint, Proceedings of ICOTA7, (2007), 35-36. |
show all references
References:
[1] |
K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization, Mathematical Programming, 91 (2001), 49-52. |
[2] |
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. |
[3] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problem, J. Industrial and Management Optimization, 3 (2007), 125-142. |
[4] |
S.-C. Fang, D. Y. Gao, R.-L. Sheu and W. Xing, Global optimization for a class of fractional programming problems, J. Global Optimization, 45 (2009), 337-353.
doi: 10.1007/s10898-008-9378-7. |
[5] |
D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optimization, 17 (2000), 127-160.
doi: 10.1023/A:1026537630859. |
[6] |
D. Y. Gao, Advances in canonical duality theory with applications to global optimization, available at: http://www.math.vt.edu/people/gao/papers/focapo08.pdf. |
[7] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman, San Francisco, CA, 1979. |
[8] |
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), 1115-1145.
doi: 10.1145/227683.227684. |
[9] |
V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Mathematical Programming, 110 (2007), 521-541.
doi: 10.1007/s10107-006-0012-5. |
[10] |
Q. Jin, S.-C. Fang and W. Xing, On the global optimality of generalized trust region subproblems, Optimization.
doi: DOI:10.1080/02331930902995236. |
[11] |
E. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optimization, 12 (2002), 875-892.
doi: 10.1137/S1052623401383248. |
[12] |
C. Lu, Z. Wang and W. Xing, An improved lower bound and approximation algorithm for binary constrained quadratic programming problem, J. Global Optimization.
doi: DOI: 10.1007/s10898-009-9504-1. |
[13] |
A. Ben-Israel and T. N. E. Greville, "Generalized Inverses," Springer-Verlag, 2003. |
[14] |
P. M. Pardalos and G. P. Rodgers, Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144.
doi: 10.1007/BF02247879. |
[15] |
J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.
doi: 10.1287/moor.28.2.246.14485. |
[16] |
X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, aviable at: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf. |
[17] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming, J. Industrial and Management Optimization, 4 (2008), 213-225. |
[18] |
Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Canonical dual approach to solving the maximum cut problem, Working Paper, to appear in J. Global Optimization. |
[19] |
L. A. Wolsey, "Integer Programming," Wiley-Interscience, 1998. |
[20] |
W. Xing, S.-C. Fang, D. Y. Gao and L. Zhang, Canonical duality solutions to quadratic programming over a quadratic constraint, Proceedings of ICOTA7, (2007), 35-36. |
[1] |
Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125 |
[2] |
Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531 |
[3] |
Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223 |
[4] |
Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543 |
[5] |
Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185 |
[6] |
Yubo Yuan. Canonical duality solution for alternating support vector machine. Journal of Industrial and Management Optimization, 2012, 8 (3) : 611-621. doi: 10.3934/jimo.2012.8.611 |
[7] |
Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 |
[8] |
Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 |
[9] |
Ziran Yin, Liwei Zhang. Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1387-1397. doi: 10.3934/jimo.2018100 |
[10] |
Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003 |
[11] |
Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697 |
[12] |
Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055 |
[13] |
Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial and Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385 |
[14] |
Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial and Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497 |
[15] |
Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063 |
[16] |
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 |
[17] |
Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131 |
[18] |
Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361 |
[19] |
Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089 |
[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]