Bundle trust region algorithm based on linear subproblem

Abstract

Bundle algorithms are currently considered as the most efficient methods for nonsmooth optimization. In most existing bundle methods (proximal, level, and trust region versions), it is necessary to solve at least one quadratic subproblem at each iteration. In this paper, a new bundle trust region algorithm with linear programming subproblems is proposed for solving nonsmooth nonconvex optimization problems. At each iteration, a piecewise linear model is defined, and using the infinity norm and the trust region technique, a linear subproblem is generalized. The algorithm is studied from both theoretical and practical points of view. Under the locally Lipschitz assumption on the objective function, global convergence of it is verified to stationary points. In the end, some encouraging numerical results with a MATLAB implementation are also reported. Computational results show that the developed method is efficient and robust for solving nonsmooth problems. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.