A Cubic Underestimator for Deterministic Global Optimization
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
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- Global Regularity for the 3D Incompressible Navier–Stokes Equations via the Frohmanian Symplectic Tether: Lean 4 Formalization and Conditional Cubic Comparison Framework (v2.1)
- Global well-posedness and scattering for the three-dimensional defocusing cubic Schrödinger equation in Hs, s>1/2
- Cubic Optimization over Three Nonnegative Integers Is NP-hard
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
BibTeX
@misc{kumar2026cubic,
title = {{A Cubic Underestimator for Deterministic Global Optimization}},
author = {Krishan Kumar and Ishan Bajaj},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33836},
eprint = {2610.33836},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33836},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Cubic Underestimator for Deterministic Global Optimization
AU - Krishan Kumar
AU - Ishan Bajaj
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33836
UR - https://arxiv.org/abs/2610.33836
AB - 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.
ER -