Linear and parabolic relaxations for quadratic constraints

Ferenc Domes () and Arnold Neumaier
Additional contact information
Ferenc Domes: University of Vienna
Arnold Neumaier: University of Vienna

Journal of Global Optimization, 2016, vol. 65, issue 3, No 3, 457-486

Abstract: Abstract This paper presents new techniques for filtering boxes in the presence of an additional quadratic constraint, a problem relevant for branch and bound methods for global optimization and constraint satisfaction. This is done by generating powerful linear and parabolic relaxations from a quadratic constraint and bound constraints, which are then subject to standard constraint propagation techniques. The techniques are often applicable even if the original box is unbounded in some but not all variables. As an auxiliary tool—needed to make our theoretical results implementable in floating-point arithmetic without sacrificing mathematical rigor—we extend the directed Cholesky factorization from Domes and Neumaier (SIAM J Matrix Anal Appl 32:262–285, 2011) to a partial directed Cholesky factorization with pivoting. If the quadratic constraint is convex and the initial bounds are sufficiently wide, the final relaxation and the enclosure are optimal up to rounding errors. Numerical tests show the usefulness of the new factorization methods in the context of filtering.

Keywords: Quadratic constraints; Non-convex constraints; Interval analysis; Constraint satisfaction problems; Parabolic relaxations; Ellipsoid relaxations; Linear relaxations; Interval hull; Directed modified Cholesky factorization; Rounding error control; Verified computing; 90C26 nonconvex programming; global optimization; 90C20 quadratic programming; 65F30 other matrix algorithms; 65G20 algorithms with automatic result verification (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0381-5 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:65:y:2016:i:3:d:10.1007_s10898-015-0381-5

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

DOI: 10.1007/s10898-015-0381-5

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 ().