×

A gradient sampling method based on ideal direction for solving nonsmooth optimization problems. (English) Zbl 1467.90042

Summary: In this paper, a modification to the original gradient sampling method for minimizing nonsmooth nonconvex functions is presented. One computational component in the gradient sampling method is the need to solve a quadratic optimization problem at each iteration, which may result in a time-consuming process, especially for large-scale objectives. To resolve this difficulty, this study proposes a new descent direction, for which there is no need to consider any quadratic or linear subproblem. It is shown that this direction satisfies the Armijo step size condition. We also prove that under proposed modifications, the global convergence of the gradient sampling method is preserved. Moreover, under some moderate assumptions, an upper bound for the number of serious iterations is presented. Using this upper bound, we develop a different strategy to study the convergence of the method. We also demonstrate the efficiency of the proposed method using small-, medium- and large-scale problems in our numerical experiments.

MSC:

90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods

Software:

LDGB; GradSamp; UFO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burke, JV; Lewis, AS; Overton, ML, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15, 3, 751-779 (2005) · Zbl 1078.65048 · doi:10.1137/030601296
[2] Kiwiel, KC, Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 18, 2, 379-388 (2007) · Zbl 1149.65043 · doi:10.1137/050639673
[3] Kiwiel, KC, A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 20, 4, 1983-1994 (2010) · Zbl 1205.90230 · doi:10.1137/090748408
[4] Curtis, FE; Que, X., An adaptive gradient sampling algorithm for nonconvex nonsmooth optimization, Optim. Methods Softw., 28, 6, 1302-1324 (2013) · Zbl 1284.49036 · doi:10.1080/10556788.2012.714781
[5] Curtis, FE; Overton, ML, A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization, SIAM J. Optim., 22, 2, 474-500 (2012) · Zbl 1246.49031 · doi:10.1137/090780201
[6] Helou, ES; Santos, AS; Simões, LEA, On the local convergence analysis of the gradient sampling method for finite max-functions, J. Optim. Theory Appl., 175, 1, 137-157 (2017) · Zbl 1386.90148 · doi:10.1007/s10957-017-1160-x
[7] Helou, ES; Santos, AS; Simões, LEA, A fast gradient and function sampling method for finite-max functions, Comput. Optim. Appl., 71, 3, 673-717 (2018) · Zbl 1414.90285 · doi:10.1007/s10589-018-0030-2
[8] Evans, LC; Gariepy, RF, Measure Theory and Fine Properties of Functions (1992), Boca Raton: CRC Press, Boca Raton · Zbl 0804.28001
[9] Clarke, FH, Optimization and Nonsmooth Analysis (1990), Montreal: SIAM, Montreal · Zbl 0696.49002
[10] Bagirov, AM; Karmitsa, N.; Mäkelä, MM, Introduction to Nonsmooth Optimization (2014), Berlin: Springer, Berlin · Zbl 1312.90053
[11] Rockafellar, RT; Wets, RJB, Variational Analysis (2004), Berlin: Springer, Berlin
[12] Burke, JV; Curtis, FE; Lewis, AS; Overton, ML; Simões, LEA; Bagirov, AM, Gradient sampling methods for nonsmooth optimization, Numerical Nonsmooth Optimization: State of the Art Algorithms, 201-225 (2020), Cham: Springer, Cham
[13] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0193.18401
[14] Ehrgott, M., Multicriteria Optimization (2005), Berlin: Springer, Berlin · Zbl 1132.90001
[15] Mäkelä, MM; Neittaanmäki, P., Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control (1992), Singapore: World Scientific, Singapore · Zbl 0757.49017
[16] Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical report, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)
[17] Skaaja, M.: Limited memory BFGS for nonsmooth optimization. Master’s Thesis, New York University (2010)
[18] Kiwiel, KC, Methods of Descent for Nondifferentiable Optimization (1985), Berlin: Springer, Berlin · Zbl 0561.90059
[19] Lukšan, L., Tcma, M., Siska, M., Vlček, J., Ramesova, N.: Ufo 2002. Interactive system for universal functional optimization. Technical report, Institute of Computer Science, Academy of Sciences of the Czech Republic (2002)
[20] Haarala, M.; Miettinen, K.; Mäkelä, MM, New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw., 19, 6, 673-692 (2004) · Zbl 1068.90101 · doi:10.1080/10556780410001689225
[21] Grothey, A.: Decomposition methods for nonlinear nonconvex optimization problems. Ph.D. Thesis, University of Edinburgh (2001)
[22] Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.