IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p40-56.html
   My bibliography  Save this article

Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Author

Listed:
  • Wei Xia

    (Industrial and Systems Engineering Department, Lehigh University, Bethlehem, Pennsylvania 18015;)

  • Juan C. Vera

    (Tilburg School of Economics and Management, Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands)

  • Luis F. Zuluaga

    (Industrial and Systems Engineering Department, Lehigh University, Bethlehem, Pennsylvania 18015;)

Abstract

We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

Suggested Citation

  • Wei Xia & Juan C. Vera & Luis F. Zuluaga, 2020. "Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 40-56, January.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:40-56
    DOI: 10.1287/ijoc.2018.0883
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0883
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0883?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jing Hu & John Mitchell & Jong-Shi Pang & Bin Yu, 2012. "On linear programs with linear complementarity constraints," Journal of Global Optimization, Springer, vol. 53(1), pages 29-51, May.
    2. Pierre Hansen & Brigitte Jaumard & MichèLe Ruiz & Junjie Xiong, 1993. "Global minimization of indefinite quadratic functions subject to box constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 373-392, April.
    3. NESTEROV, Yu., 1998. "Semidefinite relaxation and nonconvex quadratic optimization," LIDAM Reprints CORE 1362, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Samuel Burer & Dieter Vandenbussche, 2009. "Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound," Computational Optimization and Applications, Springer, vol. 43(2), pages 181-195, June.
    5. Ruth Misener & Christodoulos Floudas, 2013. "GloMIQO: Global mixed-integer quadratic optimizer," Journal of Global Optimization, Springer, vol. 57(1), pages 3-50, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Francisco Fernández-Navarro & Luisa Martínez-Nieto & Mariano Carbonero-Ruz & Teresa Montero-Romero, 2021. "Mean Squared Variance Portfolio: A Mixed-Integer Linear Programming Formulation," Mathematics, MDPI, vol. 9(3), pages 1-13, January.
    2. Marcia Fampa & Jon Lee, 2021. "Convexification of bilinear forms through non-symmetric lifting," Journal of Global Optimization, Springer, vol. 80(2), pages 287-305, June.
    3. Riley Badenbroek & Etienne Klerk, 2022. "Simulated Annealing for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives," Journal of Optimization Theory and Applications, Springer, vol. 194(2), pages 465-491, August.
    4. Riley Badenbroek & Etienne de Klerk, 2022. "An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1115-1125, March.
    5. de Klerk, Etienne & Badenbroek, Riley, 2022. "Simulated annealing with hit-and-run for convex optimization: complexity analysis and practical perspectives," Other publications TiSEM 323b4588-65e0-4889-a555-9, Tilburg University, School of Economics and Management.
    6. Jacek Gondzio & E. Alper Yıldırım, 2021. "Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations," Journal of Global Optimization, Springer, vol. 81(2), pages 293-321, October.
    7. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    8. G. Liuzzi & M. Locatelli & V. Piccialli & S. Rass, 2021. "Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems," Computational Optimization and Applications, Springer, vol. 79(3), pages 561-599, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hezhi Luo & Yuanyuan Chen & Xianye Zhang & Duan Li & Huixian Wu, 2020. "Effective Algorithms for Optimal Portfolio Deleveraging Problem with Cross Impact," Papers 2012.07368, arXiv.org, revised Jan 2021.
    2. Hezhi Luo & Xiaodong Ding & Jiming Peng & Rujun Jiang & Duan Li, 2021. "Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 180-197, January.
    3. Xiaodong Ding & Hezhi Luo & Huixian Wu & Jianzhen Liu, 2021. "An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation," Computational Optimization and Applications, Springer, vol. 80(1), pages 89-120, September.
    4. Yash Puranik & Nikolaos V. Sahinidis, 2017. "Bounds tightening based on optimality conditions for nonconvex box-constrained optimization," Journal of Global Optimization, Springer, vol. 67(1), pages 59-77, January.
    5. Huixian Wu & Hezhi Luo & Xianye Zhang & Haiqiang Qi, 2023. "An effective global algorithm for worst-case linear optimization under polyhedral uncertainty," Journal of Global Optimization, Springer, vol. 87(1), pages 191-219, September.
    6. Hezhi Luo & Xianye Zhang & Huixian Wu & Weiqiang Xu, 2023. "Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints," Computational Optimization and Applications, Springer, vol. 86(1), pages 199-240, September.
    7. Karan N. Chadha & Ankur A. Kulkarni, 2022. "On independent cliques and linear complementarity problems," Indian Journal of Pure and Applied Mathematics, Springer, vol. 53(4), pages 1036-1057, December.
    8. Jiao, Hongwei & Liu, Sanyang & Lu, Nan, 2015. "A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming," Applied Mathematics and Computation, Elsevier, vol. 250(C), pages 973-985.
    9. Ben-Tal, A. & den Hertog, D., 2011. "Immunizing Conic Quadratic Optimization Problems Against Implementation Errors," Discussion Paper 2011-060, Tilburg University, Center for Economic Research.
    10. de Klerk, E., 2006. "The Complexity of Optimizing over a Simplex, Hypercube or Sphere : A Short Survey," Discussion Paper 2006-85, Tilburg University, Center for Economic Research.
    11. Yanchao Liu, 2019. "A Progressive Motion-Planning Algorithm and Traffic Flow Analysis for High-Density 2D Traffic," Transportation Science, INFORMS, vol. 53(6), pages 1501-1525, November.
    12. Alberto Pia & Jeff Linderoth & Haoran Zhu, 2024. "Relaxations and cutting planes for linear programs with complementarity constraints," Journal of Global Optimization, Springer, vol. 90(1), pages 27-51, September.
    13. Jun Tong & Jian-Qiang Hu & Jiaqiao Hu, 2017. "A Computational Algorithm for Equilibrium Asset Pricing Under Heterogeneous Information and Short-Sale Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-16, October.
    14. Hezhi Luo & Xiaodi Bai & Jiming Peng, 2019. "Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods," Journal of Optimization Theory and Applications, Springer, vol. 180(3), pages 964-992, March.
    15. Christoph Buchheim & Maribel Montenegro & Angelika Wiegele, 2019. "SDP-based branch-and-bound for non-convex quadratic integer optimization," Journal of Global Optimization, Springer, vol. 73(3), pages 485-514, March.
    16. Lei, Chao & Jiang, Zhoutong & Ouyang, Yanfeng, 2020. "Path-based dynamic pricing for vehicle allocation in ridesharing systems with fully compliant drivers," Transportation Research Part B: Methodological, Elsevier, vol. 132(C), pages 60-75.
    17. D. Henrion & S. Tarbouriech & D. Arzelier, 2001. "LMI Approximations for the Radius of the Intersection of Ellipsoids: Survey," Journal of Optimization Theory and Applications, Springer, vol. 108(1), pages 1-28, January.
    18. Florian Jarre & Felix Lieder & Ya-Feng Liu & Cheng Lu, 2020. "Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting," Journal of Global Optimization, Springer, vol. 76(4), pages 913-932, April.
    19. Samuel Burer & Dieter Vandenbussche, 2009. "Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound," Computational Optimization and Applications, Springer, vol. 43(2), pages 181-195, June.
    20. Polyak, B.T. & Nazin, S.A., 2004. "Interval solutions for interval algebraic equations," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 66(2), pages 207-217.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:40-56. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.