A quasi-Newton proximal bundle method using gradient sampling technique for minimizing nonsmooth convex functions
Authors:
- 14 February 2022
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 37 (4) , 1415-1446
Abstract
This study aims to merge the well-established ideas of bundle and Gradient Sampling (GS) methods to develop an algorithm for locating a minimizer of a nonsmooth convex function. In the proposed method, with the help of the GS technique, we sample a number of differentiable auxiliary points around the current iterate. Then, by applying the standard techniques used in bundle methods, we construct a polyhedral (piecewise linear) model of the objective function. Moreover, by performing quasi-Newton updates on the set of auxiliary points, this polyhedral model is augmented with a regularization term that enjoys second-order information. If required, this initial model is improved by the techniques frequently used in GS and bundle methods. We analyse the global convergence of the proposed method. As opposed to the original GS method and some of its variants, our convergence analysis is independent of the size of the sample. In our numerical experiments, various aspects of the proposed method are examined using a variety of test problems. In particular, in contrast with many variants of bundle methods, we will see that the user can supply gradients approximately. Moreover, we compare the proposed method with some efficient variants of GS and bundle methods.Keywords
This publication has 37 references indexed in Scilit:
- Nonsmooth optimization via quasi-Newton methodsMathematical Programming, 2012
- Molecular Distance Geometry Problem2008
- Convergence of the Gradient Sampling Algorithm for Nonsmooth Nonconvex OptimizationSIAM Journal on Optimization, 2007
- A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex OptimizationSIAM Journal on Optimization, 2005
- New limited memory bundle method for large-scale nonsmooth optimizationOptimization Methods and Software, 2004
- A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimizationOptimization Methods and Software, 2004
- Data miningACM SIGMOD Record, 2002
- Minimizers of Cost-Functions Involving Nonsmooth Data-Fidelity Terms. Application to the Processing of OutliersSIAM Journal on Numerical Analysis, 2002
- An Efficient Method to Solve the Minimax Problem DirectlySIAM Journal on Numerical Analysis, 1978
- Pracniques: construction of nonlinear programming test problemsCommunications of the ACM, 1965