Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C26, 90C20, 90C11; Secondary: 49M37.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    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.


    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.


    D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Math. Program, 74 (1996), 121-140.doi: 10.1007/BF02592208.


    I. M. Bomze, Global optimization: A quadratic programming perspective, in "Nonlinear Optimization," Lecture Notes in Mathematics, 1989, Springer, Berlin, (2010), 1-53.


    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.


    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.


    S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs," Manuscript, Department of Mathematics, Technische Universitat Darmstadt, Darmstadt, Germany, 2008.


    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.


    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.


    D. Y. GaoAdvances in canonical duality theory with applications to global optimization, Available from: http://www.math.vt.edu/people/gao/papers/focapo08.pdf.


    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.


    G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography," Computer Science and Applied Mathematics. Academic Press,Inc., New York-London, 1980.


    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.


    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.


    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.


    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.


    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.


    J. B. LasserreGlobal optimization with polynomials and the problem of moments, SIAM J. Optimization, 11 (2001/01), 796-817. doi: 10.1137/S1052623400366802.


    P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables, BIT, 24 (1984), 206-224.


    P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization," Ph.D. Thesis, California Institute of Technology, 2000.


    J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.doi: 10.1287/moor.


    X. Sun, C. Liu, D. Li and J. GaoOn duality gap in binary quadratic programming, Available from: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf.


    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.


    L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms, SIAM J. Optimization, 16 (2006), 1076-1091.

  • 加载中

Article Metrics

HTML views() PDF downloads(129) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint