×

On the local convergence analysis of the gradient sampling method for finite max-functions. (English) Zbl 1386.90148

Summary: The gradient sampling method is a recently developed tool for solving unconstrained nonsmooth optimization problems. Using just first-order information about the objective function, it generalizes the steepest descent method, one of the most classical methods for minimizing a smooth function. This study aims at determining under which circumstances one can expect the same local convergence result of the Cauchy method for the gradient sampling algorithm under the assumption that the problem is stated by a finite max-function around the optimal point. Additionally, at the end, we show how to practically accomplish the required hypotheses during the execution of the algorithm.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods

Software:

GradSamp; PLCP; SQPlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burke, J.V., Lewis, A.S., Overton, M.L.: 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] Burke, J.V., Henrion, D., Lewis, A.S., Overton, M.L.: Stabilization via nonsmooth, nonconvex optimization. IEEE Trans. Autom. Control 51(11), 1760-1769 (2006) · Zbl 1366.93490 · doi:10.1109/TAC.2006.884944
[3] Kiwiel, K.C.: 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
[4] Clarke, F.H.: Optimization and Nonsmooth Analysis, vol. 5. SIAM, Montreal (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309
[5] Goldstein, A.A.: Optimization of Lipschitz continuous functions. Math. Program. 13(1), 14-22 (1977) · Zbl 0394.90088 · doi:10.1007/BF01584320
[6] Helou, E.S., Santos, S.A., Simões, L.E.A.: On the differentiability check in gradient sampling methods. Optim. Methods Softw. 31(5), 983-1007 (2016) · Zbl 1354.65122 · doi:10.1080/10556788.2016.1178262
[7] Mifflin, R.; Sagastizábal, C.; Théra, M. (ed.); Tichatschke, R. (ed.), VU-decomposition derivatives for convex max-functions, No. 477, 167-186 (1999), Berlin · Zbl 0944.65069 · doi:10.1007/978-3-642-45780-7_11
[8] Daniilidis, A., Sagastizábal, C., Solodov, M.: Identifying structure of nonsmooth convex functions by the bundle technique. SIAM J. Optim. 20(2), 820-840 (2009) · Zbl 1191.90066 · doi:10.1137/080729864
[9] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer, New York (1993) · Zbl 0795.49001
[10] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006) · Zbl 1104.65059
[11] Mifflin, R., Sagastizábal, C.: A VU-algorithm for convex minimization. Math. Program. 104(2-3), 583-608 (2005) · Zbl 1085.65051 · doi:10.1007/s10107-005-0630-3
[12] Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006) · Zbl 1108.65060
[13] Skajaa, A.: Limited memory BFGS for nonsmooth optimization. Master’s thesis, Courant Institute of Mathematical Science. New York University (2010)
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.