A Cubic Underestimator for Deterministic Global Optimization
math.OC
Submitted: 2026-10-24
Updated: 2026-10-24
License: http://creativecommons.org/licenses/by/4.0/
The gist: We propose a new underestimator with pointwise and Hausdorff convergence of order three for deterministic global optimization of twice continuously differentiable functions with Lipschitz continuous…
Abstract
We propose a new underestimator with pointwise and Hausdorff convergence of order three for deterministic global optimization of twice continuously differentiable functions with Lipschitz continuous Hessians. The proposed underestimator is obtained by augmenting the second-order Taylor expansion with a cubic remainder term of the objective function yielding a valid global underestimator that can be used to obtain lower bounds in a branch-and-bound method to solve nonconvex global optimization problems. The underestimator is nonconvex, and finding its global minimum could be computationally expensive. Accordingly, we derive a sufficient condition under which the proposed cubic underestimator is edge-concave, so that its minimum over a box can be found by vertex evaluation, while retaining third-order convergence. We show that the maximum separation distance between the objective function and the underestimator decreases cubically with the width of the box. This higher order convergence enables the lower bounds to converge more rapidly to the optimal value as the variable bounds are progressively tightened. The proposed underestimator is incorporated into a deterministic branch-and-bound algorithm and compared with the αBB and second-order edge-concave underestimators on a collection of 130 benchmark problems. The numerical results show that the proposed underestimator outperforms the compared underestimators in terms of both the number of explored branch-and-bound nodes and total CPU time, while maintaining a competitive computational cost per node. These results demonstrate that the proposed cubic edge-concave underestimator can provide more effective lower bounds and better computational performance in deterministic global optimization.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise