TR2022-001

SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs


    •  Nohra, C.J., Raghunathan, A., Sahinidis, N.V., "SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs", Mathematical Programming B, December 2021.
      BibTeX TR2022-001 PDF
      • @article{Nohra2021dec,
      • author = {Nohra, Carlos J. and Raghunathan, Arvind and Sahinidis, Nikolaos V.},
      • title = {SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs},
      • journal = {Mathematical Programming B},
      • year = 2021,
      • month = dec,
      • url = {https://www.merl.com/publications/TR2022-001}
      • }
  • MERL Contact:
  • Research Area:

    Optimization

Abstract:

We consider the global optimization of nonconvex mixed-integer quadratic programs with linear constraints. In particular, we present a new class of convex quadratic relaxations which are derived via convex quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms. Our relaxations are an outer-approximation of a semi-infinite convex program which under certain conditions is equivalent to a well-known semidefinite program relaxation. The new relaxations are implemented in the global optimization solver BARON, and tested by conducting numerical experiments on a large collection of problems. Results demonstrate that, for our test problems, these relaxations lead to a significant improvement in the performance of BARON.

 

  • Related Publication

  •  Nohra, C.J., Raghunathan, A., Sahinidis, N.V., "SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs", arXiv, June 2021.
    BibTeX arXiv
    • @article{Nohra2021jun,
    • author = {Nohra, Carlos J. and Raghunathan, Arvind and Sahinidis, Nikolaos V.},
    • title = {SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs},
    • journal = {arXiv},
    • year = 2021,
    • month = jun,
    • url = {https://arxiv.org/abs/2106.13721}
    • }