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

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

October 2011, 7(4): 1027-1039. doi: 10.3934/jimo.2011.7.1027

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

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

Received October 2010 Revised July 2011 Published August 2011

Abstract
Related Papers

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: Equivalence, Conic reformulation, Practical algorithm., Second order sufficient global optimality condition.

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

Citation: 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

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. Google Scholar
[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 (2003). Google Scholar
[3]	A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 310. doi: 10.1016/0377-2217(94)00229-0. Google Scholar
[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. doi: 10.1016/S0377-2217(97)00414-1. Google Scholar
[5]	D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems,, Math. Program, 74 (1996), 121. doi: 10.1007/BF02592208. Google Scholar
[6]	I. M. Bomze, Global optimization: A quadratic programming perspective,, in, 1989 (2010), 1. Google Scholar
[7]	I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs,, Optimization Letter, 4 (2010), 465. doi: 10.1007/s11590-010-0174-1. Google Scholar
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 120 (2009), 479. doi: 10.1007/s10107-008-0223-z. Google Scholar
[9]	S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs,", Manuscript, (2008). Google Scholar
[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. Google Scholar
[11]	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
[12]	D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, Available from: \url{http://www.math.vt.edu/people/gao/papers/focapo08.pdf}., (). Google Scholar
[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, (1979). Google Scholar
[14]	G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography,", Computer Science and Applied Mathematics. Academic Press, (1980). Google Scholar
[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. doi: 10.1007/s10107-006-0012-5. Google Scholar
[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. doi: 10.1137/S1052623401383248. Google Scholar
[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). Google Scholar
[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. doi: 10.3934/jimo.2010.6.779. Google Scholar
[19]	C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint,, in, 54 (2001), 119. Google Scholar
[20]	J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM J. Optimization, 11 (): 796. doi: 10.1137/S1052623400366802. Google Scholar
[21]	P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables,, BIT, 24 (1984), 206. Google Scholar
[22]	P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization,", Ph.D. Thesis, (2000). Google Scholar
[23]	J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. Google Scholar
[24]	X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, Available from: \url{http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf}., (). Google Scholar
[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. doi: 10.3934/jimo.2008.4.213. Google Scholar
[26]	L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms,, SIAM J. Optimization, 16 (2006), 1076. 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,, Math. Program, 91 (2001), 49. Google Scholar
[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 (2003). Google Scholar
[3]	A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 310. doi: 10.1016/0377-2217(94)00229-0. Google Scholar
[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. doi: 10.1016/S0377-2217(97)00414-1. Google Scholar
[5]	D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems,, Math. Program, 74 (1996), 121. doi: 10.1007/BF02592208. Google Scholar
[6]	I. M. Bomze, Global optimization: A quadratic programming perspective,, in, 1989 (2010), 1. Google Scholar
[7]	I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs,, Optimization Letter, 4 (2010), 465. doi: 10.1007/s11590-010-0174-1. Google Scholar
[8]	S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 120 (2009), 479. doi: 10.1007/s10107-008-0223-z. Google Scholar
[9]	S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs,", Manuscript, (2008). Google Scholar
[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. Google Scholar
[11]	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
[12]	D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, Available from: \url{http://www.math.vt.edu/people/gao/papers/focapo08.pdf}., (). Google Scholar
[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, (1979). Google Scholar
[14]	G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography,", Computer Science and Applied Mathematics. Academic Press, (1980). Google Scholar
[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. doi: 10.1007/s10107-006-0012-5. Google Scholar
[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. doi: 10.1137/S1052623401383248. Google Scholar
[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). Google Scholar
[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. doi: 10.3934/jimo.2010.6.779. Google Scholar
[19]	C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint,, in, 54 (2001), 119. Google Scholar
[20]	J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM J. Optimization, 11 (): 796. doi: 10.1137/S1052623400366802. Google Scholar
[21]	P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables,, BIT, 24 (1984), 206. Google Scholar
[22]	P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization,", Ph.D. Thesis, (2000). Google Scholar
[23]	J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246. doi: 10.1287/moor.28.2.246.14485. Google Scholar
[24]	X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, Available from: \url{http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf}., (). Google Scholar
[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. doi: 10.3934/jimo.2008.4.213. Google Scholar
[26]	L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms,, SIAM J. Optimization, 16 (2006), 1076. Google Scholar

[1]	Lihua Li, Yan Gao, Hongjie Wang. Second order sufficient optimality conditions for hybrid control problems with state jump. Journal of Industrial & Management Optimization, 2015, 11 (1) : 329-343. doi: 10.3934/jimo.2015.11.329
[2]	RazIye Mert, A. Zafer. A necessary and sufficient condition for oscillation of second order sublinear delay dynamic equations. Conference Publications, 2011, 2011 (Special) : 1061-1067. doi: 10.3934/proc.2011.2011.1061
[3]	M. Soledad Aronna. Second order necessary and sufficient optimality conditions for singular solutions of partially-affine control problems. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1233-1258. doi: 10.3934/dcdss.2018070
[4]	J.-P. Raymond, F. Tröltzsch. Second order sufficient optimality conditions for nonlinear parabolic control problems with state constraints. Discrete & Continuous Dynamical Systems - A, 2000, 6 (2) : 431-450. doi: 10.3934/dcds.2000.6.431
[5]	B. Bonnard, J.-B. Caillau, E. Trélat. Second order optimality conditions with applications. Conference Publications, 2007, 2007 (Special) : 145-154. doi: 10.3934/proc.2007.2007.145
[6]	A. C. Eberhard, C.E.M. Pearce. A sufficient optimality condition for nonregular problems via a nonlinear Lagrangian. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 301-331. doi: 10.3934/naco.2012.2.301
[7]	Ana P. Lemos-Paião, Cristiana J. Silva, Delfim F. M. Torres. A sufficient optimality condition for delayed state-linear optimal control problems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2293-2313. doi: 10.3934/dcdsb.2019096
[8]	Louis Tcheugoue Tebou. Equivalence between observability and stabilization for a class of second order semilinear evolution. Conference Publications, 2009, 2009 (Special) : 744-752. doi: 10.3934/proc.2009.2009.744
[9]	Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[10]	Lucas Bonifacius, Ira Neitzel. Second order optimality conditions for optimal control of quasilinear parabolic equations. Mathematical Control & Related Fields, 2018, 8 (1) : 1-34. doi: 10.3934/mcrf.2018001
[11]	Qilin Wang, Xiao-Bing Li, Guolin Yu. Second-order weak composed epiderivatives and applications to optimality conditions. Journal of Industrial & Management Optimization, 2013, 9 (2) : 455-470. doi: 10.3934/jimo.2013.9.455
[12]	Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial & Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881
[13]	Hongwei Lou. Second-order necessary/sufficient conditions for optimal control problems in the absence of linear structure. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1445-1464. doi: 10.3934/dcdsb.2010.14.1445
[14]	Ferenc A. Bartha, Ábel Garab. Necessary and sufficient condition for the global stability of a delayed discrete-time single neuron model. Journal of Computational Dynamics, 2014, 1 (2) : 213-232. doi: 10.3934/jcd.2014.1.213
[15]	Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921
[16]	Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[17]	Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[18]	Li-Li Wan, Chun-Lei Tang. Existence and multiplicity of homoclinic orbits for second order Hamiltonian systems without (AR) condition. Discrete & Continuous Dynamical Systems - B, 2011, 15 (1) : 255-271. doi: 10.3934/dcdsb.2011.15.255
[19]	Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[20]	Miniak-Górecka Alicja, Nowakowski Andrzej. Sufficient optimality conditions for a class of epidemic problems with control on the boundary. Mathematical Biosciences & Engineering, 2017, 14 (1) : 263-275. doi: 10.3934/mbe.2017017

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences