Non-Convex Optimization: Using Preconditioning Matrices for Optimally Improving Variable Bounds in Linear Relaxations

Victor Reyes () and Ignacio Araya
Additional contact information
Victor Reyes: Escuela de Informática y Telecomunicaciones, Universidad Diego Portales, Santiago 8370068, Chile
Ignacio Araya: Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2340000, Chile

Mathematics, 2023, vol. 11, issue 16, 1-19

Abstract: The performance of branch-and-bound algorithms for solving non-convex optimization problems greatly depends on convex relaxation techniques. They generate convex regions which are used for improving the bounds of variable domains. In particular, convex polyhedral regions can be represented by a linear system A . x = b . Then, bounds of variable domains can be improved by minimizing and maximizing variables in the linear system. Reducing or contracting optimally variable domains in linear systems, however, is an expensive task. It requires solving up to two linear programs for each variable (one for each variable bound). Suboptimal strategies, such as preconditioning, may offer satisfactory approximations of the optimal reduction at a lower cost. In non-square linear systems, a preconditioner P can be chosen such that P . A is close to a diagonal matrix. Thus, the projection of the equivalent system P . A . x = P . b over x , by using an iterative method such as Gauss–Seidel, can significantly improve the contraction. In this paper, we show how to generate an optimal preconditioner, i.e., a preconditioner that helps the Gauss–Seidel method to optimally reduce the variable domains. Despite the cost of generating the preconditioner, it can be re-used in sub-regions of the search space without losing too much effectiveness. Experimental results show that, when used for reducing domains in non-square linear systems, the approach is significantly more effective than Gauss-based elimination techniques. Finally, the approach also shows promising results when used as a component of a solver for non-convex optimization problems.

Keywords: optimal preconditioning matrices; interval methods; optimization-based bound tightening; branch-and-bound (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/16/3549/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/16/3549/ (text/html)

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:gam:jmathe:v:11:y:2023:i:16:p:3549-:d:1218757

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().