TR2026-085

Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions


    •  Strahl, W., Raghunathan, A., Sahinidis, N.V., Gounaris, C., "Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions", Journal of Global Optimization, DOI: 10.1007/​s10898-025-01567-5, Vol. 93, pp. 953–987, December 2025.
      BibTeX TR2026-085 PDF
      • @article{Strahl2025dec,
      • author = {Strahl, William and Raghunathan, Arvind and Sahinidis, Nikolaos V. and Gounaris, Chrysanthose},
      • title = {{Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions}},
      • journal = {Journal of Global Optimization},
      • year = 2025,
      • volume = 93,
      • pages = {953–987},
      • month = dec,
      • doi = {10.1007/s10898-025-01567-5},
      • url = {https://www.merl.com/publications/TR2026-085}
      • }
  • MERL Contact:
  • Research Area:

    Optimization

Abstract:

Recent advances in the efficiency and robustness of algorithms solving convex quadratically constrained quadratic programming (QCQP) problems motivate developing techniques for creating convex quadratic relaxations that, although more expensive to compute, provide tighter bounds than their classical linear counterparts. In the first part of this two-paper series [Strahl et al., 2024], we developed a cutting-plane algorithm to construct convex quadratic underestimators for twice-differentiable convex functions, which we extend here to address the case of non-convex difference-of-convex (d.c.) functions as well. Furthermore, we generalize our approach to consider a hierarchy of quadratic forms, thereby allowing the construction of even tighter underestimators. Utilizing a benchmark library of d.c. functions, we demonstrate noteworthy reduction in the hypervolume between our quadratic underestimators and linear ones constructed at the same points. Additionally, we construct convex QCQP relaxations at the root node of a spatial branch-and-bound tree for a set of systematically created d.c. optimization problems in up to four dimensions, and we show that our relaxations reduce the gap between the lower bound computed by the state-of-the-art global optimization solver BARON and the optimal solution by an excess of 90%, on average.

 

  • Related Publication

  •  Strahl, W., Raghunathan, A., Sahinidis, N.V., Gounaris, C., "Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions", arXiv, August 2024.
    BibTeX arXiv
    • @article{Strahl2024aug2,
    • author = {Strahl, William and Raghunathan, Arvind and Sahinidis, Nikolaos V. and Gounaris, Chrysanthose},
    • title = {{Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions}},
    • journal = {arXiv},
    • year = 2024,
    • month = aug,
    • url = {https://arxiv.org/abs/2408.13058v1}
    • }