A bundle-trust method via gradient sampling technique for nonsmooth optimization using exact and inexact gradients

Based on the proximal bundle and gradient sampling (GS) methods, we develop a robust algorithm
for minimizing a locally Lipschitz function. As an interesting feature of the proposed
method, thanks to the GS technique, we sample a set of differentiable auxiliary points from the vicinity
of the current point to construct an initial piecewise linear model for the objective function. If necessary,
inspired by bundle methods, we iteratively enrich the set of sampled points by using a single nonredundant
auxiliary point suggested by a modified variant of Mifflin’s line search. However, we may terminate the
enrichment process without achieving a descent step, which is different from classic bundle methods.
Indeed, the proposed enrichment process only accepts those auxiliary points having a small gradient
locality measure, which significantly improves the efficiency of the method in practice. In theory, our
method keeps iterations where the objective function is differentiable, and consequently, it works only
with the gradient vectors of the objective function. In contrast with existing GS methods, the radius of
the sampling region is not monotone. More precisely, by proposing a nonmonotone proximity parameter
based on the radius of the sampling region, we add some valuable features of the trust region philosophy to
our algorithm. The convergence analysis of the proposed method is comprehensively studied using exact
and inexact gradients. By means of various academic and semi-academic test problems, we demonstrate the reliability and efficiency of the proposed method in practice.