Linear and parabolic relaxations for quadratic constraints

Linear and parabolic relaxations for quadratic constraints

0.00 Avg rating0 Votes
Article ID: iaor20162381
Volume: 65
Issue: 3
Start Page Number: 457
End Page Number: 486
Publication Date: Jul 2016
Journal: Journal of Global Optimization
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.