Tighter McCormick relaxations through subgradient propagation
From MaRDI portal
Publication:2010084
DOI10.1007/S10898-019-00791-0zbMATH Open1429.49033arXiv1710.09188OpenAlexW2962939142MaRDI QIDQ2010084FDOQ2010084
Authors: Jaromił Najman, Alexander Mitsos 
Publication date: 3 December 2019
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: Tight convex and concave relaxations are of high importance in the field of deterministic global optimization. We present a heuristic to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al., SIAM J. Optim., 2009) to construct simple affine under- and overestimators of each factor of the original factorable function. Then, we minimize and maximize these affine relaxations in order to obtain possibly improved range bounds for every factor resulting in possibly tighter final McCormick relaxations. We discuss the heuristic and its limitations, in particular the lack of guarantee for improvement. Subsequently, we provide numerical results for benchmark cases found in the COCONUT library and case studies presented in previous works and discuss computational efficiency. We see that the presented heuristic provides a significant improvement in tightness and decrease in computational time in many cases.
Full work available at URL: https://arxiv.org/abs/1710.09188
Recommendations
global optimizationrange reductionMAiNGOconcave relaxationsMcCormick subgradient propagationMcCormick technique
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Numerical methods based on nonlinear programming (49M37) Numerical methods of relaxation type (49M20)
Cites Work
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- The global solver in the LINDO API
- McCormick-Based Relaxations of Algorithms
- Title not available (Why is that?)
- A note on performance profiles for benchmarking software
- A polyhedral branch-and-cut approach to global optimization
- Title not available (Why is that?)
- ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- An analytical approach to global optimization
- Calculation of bounds on variables satisfying nonlinear inequality constraints
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- A branch-and-reduce approach to global optimization
- Global optimization. Theory, algorithms, and applications
- Branching and bounds tighteningtechniques for non-convex MINLP
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- The cluster problem in multivariate global optimization
- A finite algorithm for global minimization of separable concave programs
- Affine arithmetic: concepts and applications
- A reliable affine relaxation method for global optimization
- Interval analysis on directed acyclic graphs for global optimization
- Multivariate McCormick relaxations
- Generalized McCormick relaxations
- The cluster problem revisited
- Convergence analysis of Taylor models and McCormick-Taylor models
- Title not available (Why is that?)
- Title not available (Why is that?)
- Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs
- Title not available (Why is that?)
- Reverse propagation of McCormick relaxations
- Convex optimization algorithms
- Bounds tightening based on optimality conditions for nonconvex box-constrained optimization
- Three enhancements for optimization-based bound tightening
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- Computing the range of values of real functions with accuracy higher than second order
- Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations
- Deterministic global optimization with artificial neural networks embedded
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
- The cluster problem in constrained global optimization
- Convergence-order analysis of branch-and-bound algorithms for constrained problems
- Erratum to: ``Multivariate McCormick relaxations
- Domain reduction techniques for global NLP and MINLP optimization
- On tightness and anchoring of McCormick and other relaxations
Cited In (12)
- Optimization-based convex relaxations for nonconvex parametric systems of ordinary differential equations
- Linearization of McCormick relaxations and hybridization with the auxiliary variable method
- A new framework to relax composite functions in nonlinear programs
- Extended McCormick relaxation rules for handling empty arguments representing infeasibility
- Improved convex and concave relaxations of composite bilinear forms
- EAGO.jl: easy advanced global optimization in Julia
- Reverse propagation of McCormick relaxations
- Computing subgradients of convex relaxations for solutions of parametric ordinary differential equations
- Global dynamic optimization with Hammerstein-Wiener models embedded
- Deterministic global optimization with artificial neural networks embedded
- Adjoint mode computation of subgradients for McCormick relaxations
- Multivariate McCormick relaxations
Uses Software
This page was built for publication: Tighter McCormick relaxations through subgradient propagation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010084)
