Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems

Ye Tian; Cheng Lu

doi:10.3934/jimo.2011.7.1027

Article Contents

2011, Volume 7, Issue 4: 1027-1039. Doi: 10.3934/jimo.2011.7.1027

This issue Previous Article Global convergence of an inexact operator splitting method for monotone variational inequalities Next Article A trust-region filter-SQP method for mathematical programs with linear complementarity constraints

Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems

Ye Tian^1, and
Cheng Lu^2,

1.
Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606
2.
Department of Mathematical Sciences, Tsinghua University, Beijing 100084

Received: September 30, 2010

Revised: June 30, 2011

Published: September 2011

Abstract Related Papers Cited by

Abstract

In this paper, we study a mixed integer constrained quadratic programming problem. This problem is NP-Hard. By reformulating the problem to a box constrained quadratic programming and solving the reformulated problem, we can obtain a global optimal solution of a sub-class of the original problem. The reformulated problem may not be convex and may not be solvable in polynomial time. Then we propose a solvability condition for the reformulated problem, and discuss methods to construct a solvable reformulation for the original problem. The reformulation methods identify a solvable subclass of the mixed integer constrained quadratic programming problem.

Keywords:

Second order sufficient global optimality condition,
Equivalence,
Conic reformulation,
Practical algorithm.

Mathematics Subject Classification: Primary: 90C26, 90C20, 90C11; Secondary: 49M37.

Citation:

Related Papers

Cited by

References

[1]	K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization, Math. Program, 91 (2001), 49-52.
[2]	A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," 2nd edition, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15, Springer-Verlag, New York, 2003.
[3]	A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92 (1996), 310-325.doi: 10.1016/0377-2217(94)00229-0.
[4]	A. Billionnet, A. Faye and E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 113 (1999), 664-672.doi: 10.1016/S0377-2217(97)00414-1.
[5]	D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Math. Program, 74 (1996), 121-140.doi: 10.1007/BF02592208.
[6]	I. M. Bomze, Global optimization: A quadratic programming perspective, in "Nonlinear Optimization," Lecture Notes in Mathematics, 1989, Springer, Berlin, (2010), 1-53.
[7]	I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs, Optimization Letter, 4 (2010), 465-472.doi: 10.1007/s11590-010-0174-1.
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120 (2009), 479-495.doi: 10.1007/s10107-008-0223-z.
[9]	S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs," Manuscript, Department of Mathematics, Technische Universitat Darmstadt, Darmstadt, Germany, 2008.
[10]	S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 4 (2008), 125-142.
[11]	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.
[12]	D. Y. Gao, Advances in canonical duality theory with applications to global optimization, Available from: http://www.math.vt.edu/people/gao/papers/focapo08.pdf.
[13]	M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979.
[14]	G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography," Computer Science and Applied Mathematics. Academic Press,Inc., New York-London, 1980.
[15]	V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions, Math. Program., 110 (2007), 521-541.doi: 10.1007/s10107-006-0012-5.
[16]	E. de Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), 875-892.doi: 10.1137/S1052623401383248.
[17]	C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, working paper, 2010.
[18]	C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems, Journal of Industrial and Management Optimization, 6 (2010), 779-793.doi: 10.3934/jimo.2010.6.779.
[19]	C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in "Advances in Convex Analysis and Global Optimization" (eds. N. Hadijsavvas and P. M. Paradalos), Nonconvex Optim. Appl., 54, Kluwer Acad. Publ., Dordrecht, (2001), 119-134.
[20]	J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optimization, 11 (2001/01), 796-817. doi: 10.1137/S1052623400366802.
[21]	P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables, BIT, 24 (1984), 206-224.
[22]	P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization," Ph.D. Thesis, California Institute of Technology, 2000.
[23]	J. F. Strum 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.
[24]	X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming, Available from: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf.
[25]	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.doi: 10.3934/jimo.2008.4.213.
[26]	L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms, SIAM J. Optimization, 16 (2006), 1076-1091.