Extended canonical duality and conic programming for solving 0-1 quadratic programming problems

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

October 2010, 6(4): 779-793. doi: 10.3934/jimo.2010.6.779

Extended canonical duality and conic programming for solving 0-1 quadratic programming problems

Cheng Lu ^1, , Zhenbo Wang ^1, , Wenxun Xing ^1, and Shu-Cherng Fang ^2,

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

Received February 2010 Revised April 2010 Published September 2010

Abstract
Related Papers

An extended canonical dual approach for solving 0-1 quadratic programming problems is introduced. We derive the relationship between the optimal solutions to the extended canonical dual problem and the original problem and prove that there exists no duality gap in-between. The extended canonical dual approach leads to a sufficient condition for global optimality, which is more general than known results of this kind. To solve the extended canonical dual problem, we construct corresponding conic programming problems and study their relationship to the extended canonical dual problem. Using this relationship, we design an algorithm for solving the extended canonical dual problem. Our work extends the known solvable sub-class of 0-1 quadratic programming problems.

Keywords: 0-1 quadratic programming, canonical duality, conic relaxation..

Mathematics Subject Classification: 49N15, 49M37, 90C26, 90C2.

Citation: Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

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

on AIMS
Cheng Lu Zhenbo Wang Wenxun Xing Shu-Cherng Fang
on Google Scholar
Cheng Lu Zhenbo Wang Wenxun Xing Shu-Cherng Fang

[Back to Top]