Abstract
We present an algorithm for minimizing locally Lipschitz functions being continuously differentiable in an open dense subset of \(\mathbb {R}^n\). The function may be nonsmooth and/or nonconvex. The method makes use of a gradient sampling method along with a conjugate gradient scheme. To find search directions, we make use of a sequence of positive definite approximate Hessians based on conjugate gradient matrices. The algorithm benefits from a restart procedure to improve upon poor search directions or to make sure that the approximate Hessians remain bounded. The global convergence of the algorithm is established. An implementation of the algorithm is executed on a collection of well-known test problems. Comparative numerical results clearly show outperformance of the algorithm over some recent well-known nonsmooth algorithms using the Dolan–Moré performance profiles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andrei N (2010) Accelerated scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization. Eur. J. Oper. Res. 204:410–420
Beale EML (1972) A derivation of conjugate gradients. In: Lootsma FA (ed) Numerical Methods for Nonlinear Optimization. Academic Press, London, pp 39–43
Burke JV, Lewis AS, Overton ML (2005) A robust gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 15:751–779
Chen X, Fukushima M (1999) Proximal quasi-Newton methods for nondifferentiable convex optimization. Math. Program. 85:313–334
Clarke FH (1983) Optimization and Nonsmooth Analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, New York
Curtis FE, Overton ML (2012) A sequential quadratic programming method for nonconvex nonsmooth constrained optimization. SIAM J. Optim. 22:474–500
Curtis FE, Que X (2013) An adaptive gradient sampling algorithm for nonsmooth optimization. Optim. Methods Softw. 28:1302–1324
Daniilidis A, Sagastizábal C, Solodov M (2009) Identifying structure of nonsmooth convex functions by the bundle techniques. SIAM J. Optim. 20:820–840
Dolan E, Moré J (2002) Benchmarking optimization software with performance profiles. Math. Program. 91:201–213
Goldstein AA (1977) Optimization of Lipschitz continuous functions. Math. Program. 13:14–22
Haarala M, Miettinen K, Mäkelä MM (2004) New limited memory bundle method for large-scale nonsmooth optimization. Optim. Methods Softw. 19:673–692
Karmitsa N, Mäkelä MM, Ali MM (2008) Limited memory interior point bundle method for large inequality constrained nonsmooth minimization. Appl. Math. Comput. 198(1):382–400
Kiwiel KC (2007) Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18:379–388
Kiwiel KC (2010) A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20:1983–1994
Lewis AS, Overton ML (2013) Nonsmooth optimization via quasi-Newton methods. Math. Program. 141:135–163
Lukšan, L., Tuma, M., Siska, M., Vlček, J., Ramesova, N.: Interactive system for universal functional optimization. Technical Report UFO 2002/No. 883, Academy of Science of the Czech Republic, Czech Republic (2002)
Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical Report No. 798, Academy of Science of the Czech Republic, Czech Republic (2000)
Mahdavi-Amiri N, Yousefpour R (2012) An effective nonsmooth optimization algorithm for locally Lipschitz functions. J. Optim. Theory Appl. 155:180–195
Mifflin R, Sagastizábal C (2005) A VU-algorithm for convex minimization. Math. Program. 104:583–608
Nocedal J, Wright SJ (2006) Numerical Optimization, 2nd edn. Springer, New York
Shanno DF (1978) Conjugate gradient methods with inexact searches. Math. Oper. Res. 3:244–256
Shanno DF (1978) On the convergence of a new conjugate gradient algorithm. SIAM J. Numer. Anal. 15:1247–1257
Skajaa A (2010) Limited memory BFGS for Nonsmooth Optimization. New York University, New York
Acknowledgements
The authors thank the research council of Sharif University of Technology for supporting this work. Personal discussion with Rohollah Yousefpour on early stages of our work is acknowledged.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Mahdavi-Amiri, N., Shaeiri, M. A conjugate gradient sampling method for nonsmooth optimization. 4OR-Q J Oper Res 18, 73–90 (2020). https://doi.org/10.1007/s10288-019-00404-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-019-00404-2