Global solution of quadratic problems using interval methods and convex relaxations

Sourour Elloumi (), Amélie Lambert (), Bertrand Neveu () and Gilles Trombettoni ()
Additional contact information
Sourour Elloumi: Institut Polytechnique de Paris
Amélie Lambert: Cnam
Bertrand Neveu: Univ. Gustave Eiffel
Gilles Trombettoni: University of Montpellier

Journal of Global Optimization, 2025, vol. 91, issue 2, No 5, 353 pages

Abstract: Abstract Interval branch-and-bound solvers provide reliable algorithms for handling non-convex optimization problems by ensuring the feasibility and the optimality of the computed solutions, i.e. independently from the floating-point rounding errors. Moreover, these solvers deal with a wide variety of mathematical operators. However, these solvers are not dedicated to quadratic optimization and do not exploit nonlinear convex relaxations in their framework. We present an interval branch-and-bound method that can efficiently solve quadratic optimization problems. At each node explored by the algorithm, our solver uses a quadratic convex relaxation which is as strong as a semi-definite programming relaxation, and a variable selection strategy dedicated to quadratic problems. The interval features can then propagate efficiently this information for contracting all variable domains. We also propose to make our algorithm rigorous by certifying firstly the convexity of the objective function of our relaxation, and secondly the validity of the lower bound calculated at each node. In the non-rigorous case, our experiments show significant speedups on general integer quadratic instances, and when reliability is required, our first results show that we are able to handle medium-sized instances in a reasonable running time.

Keywords: MINLP; Quadratic programming; Interval methods; Semi-definite programming; Reliable solver; Experiments (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01370-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:91:y:2025:i:2:d:10.1007_s10898-024-01370-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01370-8

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().