×

On Lipschitz optimization based on gray-box piecewise linearization. (English) Zbl 1350.49038

Authors’ abstract: We address the problem of minimizing objectives from the class of piecewise differentiable functions whose nonsmoothness can be encapsulated in the absolute value function. They possess local piecewise linear approximations with a discrepancy that can be bounded by a quadratic proximal term. This overestimating local model is continuous but generally nonconvex. It can be generated in its abs-normal form by a minor extension of standard algorithmic differentiation tools. Here we demonstrate how the local model can be minimized by a bundle-type method, which benefits from the availability of additional gray-box information via the abs-normal form. In the convex case our algorithm realizes the consistent steepest descent trajectory for which finite convergence was established earlier, specifically covering counterexamples where steepest descent with exact line-search famously fails. The analysis of the abs-normal representation and the design of the optimization algorithm are geared toward the general case, whereas the convergence proof so far covers only the convex case.

MSC:

49M30 Other numerical methods in calculus of variations (MSC2010)
49J52 Nonsmooth analysis
90C56 Derivative-free methods and methods using generalized derivatives

Software:

ADOL-C; SQPlab; PLCP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alt, W.: Numerische Verfahren der konvexen, nichtglatten Optimierung. Eine anwendungsorientierte Einführung. Teubner, Leipzig (2004) · Zbl 1068.65072 · doi:10.1007/978-3-322-80083-1
[2] Aubin, J.-P., Arriga, C.: Differential Inclusions. Set-Valued Maps and Viability Theory. Springer, Berlin (1984) · doi:10.1007/978-3-642-69512-4
[3] Bonnans, F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Theoretical and Practical Aspects. Transl. from the French. 2nd revised edn. Springer, Berlin (2006) · Zbl 1108.65060
[4] Clarke, F.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309
[5] Cominetti, R., Courdurier, M.: Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm. SIAM J. Optim. 13(3), 745-765 (2002) · Zbl 1049.90056 · doi:10.1137/S1052623401397242
[6] de Oliveira, W., Sagastizábal, C.: Bundle methods in the XXIst century: a birds’-eye view. Pesquisa Operacional 34(3), 647-670 (2014) · doi:10.1590/0101-7438.2014.034.03.0647
[7] Fiege, S., Griewank, A., Walther, A.: An exploratory line search for piecewise differentiable objective functions based on algorithmic differentiation. PAMM 12, 631-632 (2012) · doi:10.1002/pamm.201210304
[8] Fourer, R.: A simplex algorithm for piecewise-linear programming. I. Derivation and proof. Math. Program. 33, 204-233 (1985) · Zbl 0579.90084
[9] Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979) · Zbl 0411.68039
[10] Goffin, J.-L.: Subgradient optimization in nonsmooth optimization (including the soviet revolution). Doc. Math. Extra Vol., 277-290 (2012) · Zbl 1282.90135
[11] Griewank, A.: On stable piecewise linearization and generalized algorithmic differentiation. Opt. Meth. Softw. 28(6), 1139-1178 (2013) · Zbl 1278.65021 · doi:10.1080/10556788.2013.796683
[12] Griewank, A., Bernt, J.-U., Randons, M., Streubel, T.: Solving Piecewise Linear Equations in abs-normal Form. Technical report, Humboldt Universität zu Berlin (2013). To appear in Linear Algebra and its Applications · Zbl 1198.90359
[13] Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Philadelphia (2008) · Zbl 1159.65026 · doi:10.1137/1.9780898717761
[14] Fiege, S., Griewank, A., Kulshreshta, K., Walther, A.: An algorithm for nonsmooth optimization by successive piecewise linearization. Technical report, HU Berlin (2015) · Zbl 1420.49015
[15] Gürbüzbalaban, M., Overton, M.L.: On Nesterov’s nonsmooth Chebyshev-Rosenbrock functions. Nonlinear Anal.: Theory Methods Appl. 75(3), 1282-1289 (2012) · Zbl 1269.49018 · doi:10.1016/j.na.2011.07.062
[16] Hare, W., Nutini, J.: A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput. Optim. Appl. 56(1), 1-38 (2013) · Zbl 1300.90064 · doi:10.1007/s10589-013-9547-6
[17] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993) · Zbl 0795.49001
[18] Karmitsa, N., Mäkelä, M.: Limited memory bundle method for large bound constrained nonsmooth optimization: convergence analysis. Optim. Methods Softw. 25(6), 895-916 (2010) · Zbl 1198.90359 · doi:10.1080/10556780902842495
[19] Lemaréchal, C.: Nonsmooth Optimization and Descent Methods. Technical Report 78,4, IIASA (1978) · Zbl 0398.90090
[20] Lemaréchal, C., Sagastizábal, C.: Variable metric bundle methods: from conceptual to implementable forms. Math. Program. 76(3), 393-410 (1997) · Zbl 0872.90072 · doi:10.1007/BF02614390
[21] Lewis, A., Overton, M.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1-2), 135-163 (2013) · Zbl 1280.90118 · doi:10.1007/s10107-012-0514-2
[22] Mifflin, R., Sagastizábal, C.: A science fiction story in nonsmooth optimization originating at IIASA. Doc. Math. Extra Vol., 291-300 (2012) · Zbl 1264.01016
[23] Nesterov, Y.: Lexicographic differentiation of nonsmooth functions. Math. Program. 104(2-3), 669-700 (2005) · Zbl 1082.49023 · doi:10.1007/s10107-005-0633-0
[24] Scholtes, S.: Introduction to Piecewise Differentiable Functions. Springer, Berlin (2012) · Zbl 1453.49002 · doi:10.1007/978-1-4614-4340-7
[25] Shen, J., Han, L., Pang, J.S.: Switching and stability properties of conewise linear systems. ESAIM: Control Optim. Calc. Var. 16(3), 764-793 (2010) · Zbl 1195.93028 · doi:10.1051/cocv/2009021
[26] Shor, N.Z.: Nondifferentiable Optimization and Polynomial Problems. Kluwer, Dordrecht (1998) · Zbl 0901.49015 · doi:10.1007/978-1-4757-6015-6
[27] Walther, A., Griewank, A.: Combinatorial Scientific Computing. Chapter Getting Started with ADOL-C, pp. 181-202. Chapman-Hall CRC Computational Science (2012) · Zbl 1278.65021
[28] Wolfe, P.: A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Stud. 3, 145-173 (1975) · Zbl 0369.90093 · doi:10.1007/BFb0120703
[29] Yuan, G., Wei, Z., Wang, Z.: Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex optimization. Comp. Opt. Appl. 54(1), 45-64 (2012) · Zbl 1267.90101 · doi:10.1007/s10589-012-9485-8
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.