Enhancing Inner Linearizations Assisted by Gradient-Based Expansion Point Optimization

Abstract

Nonlinear Continuous global Optimization Problems (NCOPs) are well-known problems that arise in many applications, from engineering to robotics. The Branch & Bound method is a widely used approach for solving NCOPs to global optimality, often interleaving techniques like bisection and filtering. A key aspect of this approach is identifying feasible solutions early in the search process, which enables effective pruning of the search tree and avoids unnecessary computational effort. Inner linear relaxation techniques, such as the AbsTaylor strategy, have proven effective for identifying feasible regions; however, they heavily rely on a heuristically chosen expansion point (often the box midpoint), which directly impacts solution quality and relaxation success. In this work, we propose a novel gradient-based strategy to dynamically optimize the selection of this expansion point. By employing Gradient Descent to minimize a Mean Squared Error (MSE) objective formulated exclusively over the active constraints, we systematically guide the expansion point safely away from boundaries and into a strictly feasible interior region. To manage computational overhead, we evaluate restricted iteration budgets alongside algorithmic variants, specifically introducing a point inheritance strategy for warm-starting and comparing Batch versus Incremental gradient updates. Experimental results on a well-known benchmark set demonstrate that this gradient-based approach minimizes the probability of relaxation failure, significantly enhancing pruning effectiveness and overall solver efficiency compared to the original strategy.