Relaxation via separable estimators: arithmetic and implementation.
- 1The Sargent Centre for Process Systems Engineering, Department of Chemical Engineering, Imperial College London, London, UK.
- 2DYSCO Unit, IMT School for Advanced Studies Lucca, Lucca, Italy.
- 3School of Information Science and Technology, ShanghaiTech University, Shanghai, China.
Abstract
This article presents an arithmetic, called superposition relaxation, for bracketing the graph of a multivariate factorable function on a compact domain between a pair of underestimating and overestimating functions that are both separable. Propagation rules are established for affine and nonlinear composition operations, with a focus on exploiting global monotonicity and convexity properties in the composition. The local convergence properties of this arithmetic are also analyzed in both the pointwise and Hausdorff sense, including conditions under which quadratic pointwise convergence propagates through composition. Parameterizations of the univariate summands in a superposition relaxation either as piecewise-constant or continuous piecewise-linear functions are discussed for a practical implementation. It is shown through numerical case studies that superposition relaxations can be consistently tighter than McCormick relaxations, including for the relaxation of artificial neural networks. But superposition relaxations also incur a higher computational cost than McCormick relaxations. Further investigations are thus warranted as applications in global optimization seek to balance a relaxation's tightness with its computational cost.
Related
- Statistical-computational trade-offs for recursive adaptive partitioning estimators
- Eigenvector distributions and optimal shrinkage estimators for large covariance and precision matrices
- HEDE: Heritability estimation in high dimensions by ensembling debiased estimators in genome-wide association studies
- Optimal Two‐Phase Sampling Designs for Generalized Raking Estimators With Multiple Parameters of Interest
- Bayes Estimators with Performance Comparable to Empirical Bayes Estimators and Improved Local Robustness
BibTeX
@article{zha2026relaxation,
title = {{Relaxation via separable estimators: arithmetic and implementation.}},
author = {Yanlin Zha and Mario Eduardo Villanueva and Boris Houska and Benoît Chachuat},
journal = {Journal of global optimization : an international journal dealing with theoretical and computational aspects of seeking global optima and their applications in science, management and engineering},
year = {2026},
month = oct,
doi = {10.1007/s10898-026-01648-z},
url = {https://europepmc.org/article/MED/42948171},
note = {CC BY},
}
RIS
TY - JOUR
TI - Relaxation via separable estimators: arithmetic and implementation.
AU - Yanlin Zha
AU - Mario Eduardo Villanueva
AU - Boris Houska
AU - Benoît Chachuat
PY - 2026
DA - 2026/10/01
JO - Journal of global optimization : an international journal dealing with theoretical and computational aspects of seeking global optima and their applications in science, management and engineering
DO - 10.1007/s10898-026-01648-z
UR - https://europepmc.org/article/MED/42948171
AB - This article presents an arithmetic, called superposition relaxation, for bracketing the graph of a multivariate factorable function on a compact domain between a pair of underestimating and overestimating functions that are both separable. Propagation rules are established for affine and nonlinear composition operations, with a focus on exploiting global monotonicity and convexity properties in the composition. The local convergence properties of this arithmetic are also analyzed in both the pointwise and Hausdorff sense, including conditions under which quadratic pointwise convergence propagates through composition. Parameterizations of the univariate summands in a superposition relaxation either as piecewise-constant or continuous piecewise-linear functions are discussed for a practical implementation. It is shown through numerical case studies that superposition relaxations can be consistently tighter than McCormick relaxations, including for the relaxation of artificial neural networks. But superposition relaxations also incur a higher computational cost than McCormick relaxations. Further investigations are thus warranted as applications in global optimization seek to balance a relaxation's tightness with its computational cost.
SN - 0925-5001
SN - 1573-2916
ER -