Algorithmic differentiation for piecewise smooth functions: a case study for robust optimization. (English) Zbl 1401.90168

Summary: This paper presents a minimization method for Lipschitz continuous, piecewise smooth objective functions based on algorithmic differentiation (AD). We assume that all nondifferentiabilities are caused by abs(), min(), and max(). The optimization method generates successively piecewise linearizations in abs-normal form and solves these local subproblems by exploiting the resulting kink structure. Both the generation of the abs-normal form and the exploitation of the kink structure are possible due to extensions of standard AD tools. This work presents corresponding drivers for the AD tool ADOL-C which are embedded in the nonsmooth solver LiPsMin. Finally, minimax problems from robust optimization are considered. Numerical results and a comparison of LiPsMin with other nonsmooth optimization methods are discussed.


90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C47 Minimax problems in mathematical programming
Full Text: DOI


[1] Burke, J. V.; Lewis, A. S.; Overton, M. L., A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15, 751-779, (2005) · Zbl 1078.65048
[2] An algorithm for nonsmooth optimization by successive piecewise linearizationAvailable on
[3] Griewank, A., on stable piecewise linearization and generalized algorithmic differentiation, Optim. Methods Softw., 28, 1139-1178, (2013) · Zbl 1278.65021
[4] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia, PA, USA · Zbl 1159.65026
[5] Griewank, A.; Walther, A., first- and second-order optimality conditions for piecewise smooth objective functions, Optim. Methods Softw., 31, 904-930, (2016) · Zbl 1385.90026
[6] Griewank, A.; Walther, A.; Fiege, S.; Bosse, T., on Lipschitz optimization based on gray-box piecewise linearization, Math. Program. Ser. A, 1-33, (2015)
[7] Griewank, A.; Bernt, J. -U.; Radons, M.; Streubel, T., solving piecewise linear systems in ABS-normal form, Linear Algebra Appl., 471, 500-530, (2015) · Zbl 1308.90179
[8] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms I, (1993), Springer, Heidelberg
[9] Karmitsa, N.; Mäkelä, M. M., limited memory bundle method for large bound constrained nonsmooth optimization: convergence analysis, Optim. Methods Softw., 25, 895-916, (2010) · Zbl 1198.90359
[10] Lewis, A. S.; Overton, M. L., nonsmooth optimization via quasi-Newton methods, Math. Program., 141, 135-163, (2013) · Zbl 1280.90118
[11] Test problems for nonsmooth unconstrained and linearly constrained optimization, Tech. Rep. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic, 2000
[12] Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0, Reports of the Department of Mathematical Information Technology, Series B, Scientific Computing No. B 13/2003, University of Jyväskylä, 2003
[13] Mäkelä, M.; Neittaanmäki, P., Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, (1992), World Scientific, Singapore · Zbl 0757.49017
[14] Scholtes, S., Introduction to Piecewise Differentiable Functions, (2012), Springer, Berlin · Zbl 1453.49002
[15] Getting Started with ADOL-C, in Combinatorial Scientific ComputingChapman-Hall CRC Computational ScienceLondon2012181202
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.