Polynomial Optimization: Tightening RLT-Based Branch-and-Bound Schemes with Conic Constraints

Brais González-Rodríguez (), Raúl Alvite-Pazó (), Samuel Alvite-Pazó (), Bissan Ghaddar () and Julio González-Díaz ()
Additional contact information
Brais González-Rodríguez: University of Vigo Ourense
Raúl Alvite-Pazó: CITMAga (Galician Center for Mathematical Research and Technology)
Samuel Alvite-Pazó: CITMAga (Galician Center for Mathematical Research and Technology)
Bissan Ghaddar: Western University London
Julio González-Díaz: CITMAga (Galician Center for Mathematical Research and Technology)

Journal of Optimization Theory and Applications, 2025, vol. 204, issue 1, No 12, 34 pages

Abstract: Abstract This paper explores the potential of (nonlinear) conic constraints to tighten the relaxations of spatial branch-and-bound algorithms. More precisely, we contribute to the literature on the use of conic optimization for the efficient solution, to global optimality, of nonconvex polynomial optimization problems. Taking as baseline an RLT-based algorithm, we present different families of well-known conic-driven constraints: linear SDP-cuts, second-order cone constraints, and SDP constraints. We integrate these constraints in the baseline algorithm and present a thorough computational study to assess their performance, both with respect to each other and with respect to the standard RLT relaxations for polynomial optimization problems. Our main finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around $$50\%$$ 50 % of the instances in widely used test sets. Additionally, we discuss how one can benefit from the use of machine learning to decide on the most suitable constraints to add to a given instance. The computational results show that the machine learning approach significantly outperforms each of the individual approaches.

Keywords: Global optimization; Reformulation–linearization technique; Polynomial programming; Conic optimization; Machine learning; 90C23; 90C22; 90C26; 90C30 (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/s10957-024-02558-4 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:joptap:v:204:y:2025:i:1:d:10.1007_s10957-024-02558-4

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-024-02558-4

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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