Optimization Online


On Lipschitz optimization based on gray-box piecewise linearization

Andreas Griewank (griewank***at***math.hu-berlin.de)
Andrea Walther (andrea.walther***at***uni-paderborn.de)
Sabrina Fiege (sfiege***at***math.uni-paderborn.de)
Torsten Bosse (bosse***at***math.hu-berlin.de)

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 in the book by Hiriart-Urruty and Lemarechal, specifically covering counter examples where steepest descent with exact line-search famously fails. The analysis of the abs-normal representation and the design of the optimization algorithm is geared towards the general case, whereas the convergence proof so far only covers the convex case.

Keywords: Bundle methods, Piecewise linearity, Algorithmic differentiation, Abs-normal form

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Humboldt-Universit├Ąt zu Berlin, June 2014

Download: [PDF]

Entry Submitted: 06/25/2014
Entry Accepted: 06/25/2014
Entry Last Modified: 02/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society