Relaxation via Separable Estimators: Arithmetic and Implementation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916001260503040 |
|---|---|
| author | Zha, Yanlin Villanueva, Mario Eduardo Houska, Boris Chachuat, Benoît |
| author_facet | Zha, Yanlin Villanueva, Mario Eduardo Houska, Boris Chachuat, Benoît |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10854 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Relaxation via Separable Estimators: Arithmetic and Implementation Zha, Yanlin Villanueva, Mario Eduardo Houska, Boris Chachuat, Benoît Numerical Analysis Optimization and Control 26B40, 41A30, 90C26, 90C59 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. |
| title | Relaxation via Separable Estimators: Arithmetic and Implementation |
| topic | Numerical Analysis Optimization and Control 26B40, 41A30, 90C26, 90C59 |
| url | https://arxiv.org/abs/2605.10854 |