A Target-Feasibility Branch-and-Prune Algorithm for Nonconvex Constrained Optimization

Abstract

We present a branch-and-prune algorithm for nonconvex constrained optimization in which each box is treated as a target-level feasibility problem and solved through an extended Lagrangian saddle-point formulation. The current incumbent objective value $U$ is incorporated directly as an additional inequality constraint $f_0(x) - U \leq 0$, with its own nonnegative multiplier $y_U$. The resulting extended Lagrangian is L(x,y) = (1 + y_U) f₀(x) + Σᵢ₌₁ᵐ yᵢ fᵢ(x) − y_U U. For a fixed dual vector, the method minimizes the Lagrangian over the current box; the resulting primal point is then used to update the dual variables by ascent. A box is retained when the oracle returns a feasible point and is pruned when the associated target-feasibility problem is certified infeasible. The central theoretical observation is that when the original constraints are feasible but the incumbent target is unattainable, compactness and continuity imply a uniform positive objective gap on the feasible portion of the box. Consequently, under the idealized dual-ascent iteration with positive step sizes, the specific multiplier $y_U$ must diverge. This provides a mathematical basis for the pruning mechanism. Separately, continuity and compactness imply that exhaustive subdivision of the box containing a global minimizer produces feasible points whose objective values converge to the global optimum. These two results together establish global convergence of the idealized branch-and-prune procedure under the stated assumptions. The numerical implementation approximates the per-box minimization and detects divergence using finite tolerances and thresholds. Numerical experiments on a collection of convex and nonconvex test problems demonstrate that the implementation successfully recovers the known global optima, including problems with multiple local minima, active and inactive constraints, multiple global minimizers, and disconnected feasible regions.