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]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[2]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[5]

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[6]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[7]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[8]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379
[9]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[10]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[11]

Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128
[12]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617
[13]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences