{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:02:32Z","timestamp":1760238152068,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T00:00:00Z","timestamp":1594425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>For piecewise linear functions     f :  R n  \u21a6 R     we show how their abs-linear representation can be extended to yield simultaneously their decomposition into a convex     f \u02c7     and a concave part     f ^    , including a pair of generalized gradients      g \u02c7  \u2208  R n  \u220b  g ^     . The latter satisfy strict chain rules and can be computed in the reverse mode of algorithmic differentiation, at a small multiple of the cost of evaluating f itself. It is shown how     f \u02c7     and     f ^     can be expressed as a single maximum and a single minimum of affine functions, respectively. The two subgradients     g \u02c7     and     \u2212  g ^      are then used to drive DCA algorithms, where the (convex) inner problem can be solved in finitely many steps, e.g., by a Simplex variant or the true steepest descent method. Using a reflection technique to update the gradients of the concave part, one can ensure finite convergence to a local minimizer of f, provided the Linear Independence Kink Qualification holds. For piecewise smooth objectives the approach can be used as an inner method for successive piecewise linearization.<\/jats:p>","DOI":"10.3390\/a13070166","type":"journal-article","created":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T04:46:01Z","timestamp":1594701961000},"page":"166","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Polyhedral DC Decomposition and DCA Optimization of Piecewise Linear Functions"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9839-1473","authenticated-orcid":false,"given":"Andreas","family":"Griewank","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Mathematik, Humboldt-Universit\u00e4t zu Berlin, 10099 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3516-4641","authenticated-orcid":false,"given":"Andrea","family":"Walther","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Mathematik, Humboldt-Universit\u00e4t zu Berlin, 10099 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s10898-016-0488-3","article-title":"A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes","volume":"68","author":"Joki","year":"2017","journal-title":"J. Glob. Optim."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Tuy, H. (1995). DC optimization: Theory, methods and algorithms. Handbook of Global Optimization, Springer.","DOI":"10.1007\/978-1-4615-2025-2_4"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1023\/A:1022374804152","article-title":"Fast and parallel interval arithmetic","volume":"39","author":"Rump","year":"1999","journal-title":"BIT"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1080\/02331931003770411","article-title":"On difference convexity of locally Lipschitz functions","volume":"60","author":"Borwein","year":"2011","journal-title":"Optimization"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Griewank, A., and Walther, A. (2008). Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898717761"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1016\/j.na.2011.07.062","article-title":"On Nesterov\u2019s nonsmooth Chebyshev-Rosenbrock functions","volume":"75","author":"Overton","year":"2012","journal-title":"Nonlinear Anal. Theory Methods Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1080\/10556788.2016.1189549","article-title":"First and second order optimality conditions for piecewise smooth objective functions","volume":"31","author":"Griewank","year":"2016","journal-title":"Optim. Methods Softw."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Strekalovsky, A. (2020). Local Search for Nonsmooth DC Optimization with DC Equality and Inequality Constraints. Numerical Nonsmooth Optimization. State of the Art Algorithms, Springer Nature Switzerland AG.","DOI":"10.1007\/978-3-030-34910-3_7"},{"key":"ref_9","unstructured":"Hansen, E. (1969). The centred form. Topics in Interval Analysis, Oxford University Press."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Scholtes, S. (2012). Introduction to Piecewise Differentiable Functions, Springer.","DOI":"10.1007\/978-1-4614-4340-7"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1139","DOI":"10.1080\/10556788.2013.796683","article-title":"On Stable Piecewise Linearization and Generalized Algorithmic Differentiation","volume":"28","author":"Griewank","year":"2013","journal-title":"Optim. Methods Softw."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1016\/j.laa.2014.12.017","article-title":"Solving piecewise linear equations in abs-normal form","volume":"471","author":"Griewank","year":"2015","journal-title":"Linear Algebra Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10107-015-0934-x","article-title":"On Lipschitz optimization based on gray-box piecewise linearization","volume":"158","author":"Griewank","year":"2016","journal-title":"Math. Program. Ser. A"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Golub, G., and Van Loan, C. (2013). Matrix Computations, Johns Hopkins University Press. [4th ed.].","DOI":"10.56021\/9781421407944"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Rockafellar, R., and Wets, R.B. (1998). Variational Analysis, Springer.","DOI":"10.1007\/978-3-642-02431-3"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s10479-016-2385-z","article-title":"Combinatorial redundancy detection","volume":"265","author":"Fukuda","year":"2018","journal-title":"Ann. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10107-018-1235-y","article-title":"DC programming and DCA: Thirty years of developments","volume":"169","year":"2018","journal-title":"Math. Program. Ser. B"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Griewank, A., and Walther, A. (2020). Beyond the Oracle: Opportunities of Piecewise Differentiation. Numerical Nonsmooth Optimization. State of the Art Algorithms, Springer.","DOI":"10.1007\/978-3-030-34910-3_10"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1473","DOI":"10.1137\/17M115520X","article-title":"Characterizing and testing subdifferential regularity in piecewise smooth optimization","volume":"29","author":"Walther","year":"2019","journal-title":"SIAM J. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Griewank, A. (2012). Who invented the reverse mode of differentiation?. Doc. Math., 389\u2013400.","DOI":"10.4171\/dms\/6\/38"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/BF01931367","article-title":"Taylor expansion of the accumulated rounding error","volume":"16","author":"Linnainmaa","year":"1976","journal-title":"BIT"},{"key":"ref_22","first-page":"451","article-title":"Proximal point algorithm for minimization of DC function","volume":"21","author":"Sun","year":"2003","journal-title":"J. Comput. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1080\/10556788.2018.1546856","article-title":"Finite convergence of an active signature method to local minima of piecewise linear functions","volume":"34","author":"Griewank","year":"2019","journal-title":"Optim. Methods Softw."},{"key":"ref_24","unstructured":"Griewank, A., and Walther, A. (2020). The True Steepest Descent Methods Revisited, Humboldt-Universit\u00e4t zu Berlin. Technical Report."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/17M1157623","article-title":"Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization","volume":"29","author":"Griewank","year":"2019","journal-title":"SIAM J. Optim."},{"key":"ref_26","unstructured":"Niu, Y. (2010). Programmation DC & DCA en Optimisation Combinatoire et Optimisation Polynomiale via les Techniques de SDP. [Ph.D. Thesis, INSA Rouen]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1080\/10556788.2017.1333613","article-title":"Algorithmic differentiation for piecewise smooth functions: A case study for robust optimization","volume":"33","author":"Fiege","year":"2018","journal-title":"Optim. Methods Softw."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Walther, A., and Griewank, A. (2012). Getting Started with ADOL-C. Combinatorial Scientific Computing, CRC Press.","DOI":"10.1201\/b11644-8"},{"key":"ref_29","first-page":"20:1","article-title":"The Tapenade Automatic Differentiation tool: Principles, Model, and Specification","volume":"39","author":"Pascual","year":"2013","journal-title":"ACM Trans. Math. Softw."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/166\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:50:09Z","timestamp":1760176209000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,11]]},"references-count":29,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2020,7]]}},"alternative-id":["a13070166"],"URL":"https:\/\/doi.org\/10.3390\/a13070166","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,7,11]]}}}