American Institute of Mathematical Sciences

Advanced
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

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 & 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.   Google Scholar

[2]

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

[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.   Google Scholar

[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.  doi: 10.1007/s10898-008-9378-7.  Google Scholar

[5]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127.  doi: 10.1023/A:1026537630859.  Google Scholar

[6]

D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, available at: , ().   Google Scholar

[7]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", W. H. Freeman, (1979).   Google Scholar

[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.  doi: 10.1145/227683.227684.  Google Scholar

[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.  doi: 10.1007/s10107-006-0012-5.  Google Scholar

[10]

Q. Jin, S.-C. Fang and W. Xing, On the global optimality of generalized trust region subproblems,, Optimization., ().  doi: DOI:10.1080/02331930902995236.  Google Scholar

[11]

E. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming,, SIAM J. Optimization, 12 (2002), 875.  doi: 10.1137/S1052623401383248.  Google Scholar

[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.  Google Scholar

[13]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses,", Springer-Verlag, (2003).   Google Scholar

[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.  doi: 10.1007/BF02247879.  Google Scholar

[15]

J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[16]

X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, aviable at: , ().   Google Scholar

[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.   Google Scholar

[18]

Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Canonical dual approach to solving the maximum cut problem,, Working Paper, ().   Google Scholar

[19]

L. A. Wolsey, "Integer Programming,", Wiley-Interscience, (1998).   Google Scholar

[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.   Google Scholar

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.   Google Scholar

[2]

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

[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.   Google Scholar

[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.  doi: 10.1007/s10898-008-9378-7.  Google Scholar

[5]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127.  doi: 10.1023/A:1026537630859.  Google Scholar

[6]

D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, available at: , ().   Google Scholar

[7]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", W. H. Freeman, (1979).   Google Scholar

[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.  doi: 10.1145/227683.227684.  Google Scholar

[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.  doi: 10.1007/s10107-006-0012-5.  Google Scholar

[10]

Q. Jin, S.-C. Fang and W. Xing, On the global optimality of generalized trust region subproblems,, Optimization., ().  doi: DOI:10.1080/02331930902995236.  Google Scholar

[11]

E. Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming,, SIAM J. Optimization, 12 (2002), 875.  doi: 10.1137/S1052623401383248.  Google Scholar

[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.  Google Scholar

[13]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses,", Springer-Verlag, (2003).   Google Scholar

[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.  doi: 10.1007/BF02247879.  Google Scholar

[15]

J. F. Sturm and S. Z. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[16]

X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, aviable at: , ().   Google Scholar

[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.   Google Scholar

[18]

Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Canonical dual approach to solving the maximum cut problem,, Working Paper, ().   Google Scholar

[19]

L. A. Wolsey, "Integer Programming,", Wiley-Interscience, (1998).   Google Scholar

[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.   Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2017, 13 (5) : 1-13. 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 & 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 & 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 & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[12]

Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial & Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385
[13]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497
[14]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131
[15]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[16]

Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063
[17]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089
[18]

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
[19]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[20]

Renato Manfrin. On the boundedness of solutions of the equation $u''+(1+f(t))u=0$. Discrete & Continuous Dynamical Systems - A, 2009, 23 (3) : 991-1008. doi: 10.3934/dcds.2009.23.991

2018 Impact Factor: 1.025

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences