Invited Session Tue.1.H 2035

Tuesday, 10:30 - 12:00 h, Room: H 2035

Cluster 24: Variational analysis [...]

Nonsmooth analysis via piecewise-linearization


Chair: Andreas Griewank



Tuesday, 10:30 - 10:55 h, Room: H 2035, Talk 1

Kamil Khan
Evaluating an element of the Clarke generalized Jacobian of a piecewise differentiable function

Coauthor: Paul I. Barton


The (Clarke) generalized Jacobian of a locally Lipschitz continuous function is a derivative-like set-valued mapping that contains slope information. Bundle methods for nonsmooth optimization and semismooth Newton methods for equation solving require evaluation of generalized Jacobian elements. However, since the generalized Jacobian does not satisfy calculus rules sharply, this evaluation can be difficult.
In this work, a method is presented for evaluating generalized Jacobian elements of a nonsmooth function that is expressed as a finite composition of absolute value functions and continuously differentiable functions. The method makes use of the principles of automatic differentiation and the theory of piecewise differentiable functions, and is guaranteed to be computationally tractable relative to the cost of a function evaluation. The presented techniques are applied to nonsmooth example problems for illustration.



Tuesday, 11:00 - 11:25 h, Room: H 2035, Talk 2

Andreas Griewank
On piecewise linearization and lexicographic differentiation


It is shown how functions that are defined by an evaluation programs can be approximated locally by a piecewise-linear model. In contrast to the standard approach in algorithmic or automatic differentiation, we allow for the occurrence of nonsmooth but Lipschitz continuous elemental functions like the absolute value function \operatorname{abs}(), min(), max(),
and more general table look ups. Then the resulting composite function is piecewise differentiable in that it is everywhere the continuous selection of a finite number of smooth functions (Scholtes). Moreover, it can be locally approximated by a piecewise-linear model with a finite
number of kinks between open polyhedra decomposing the function domain.The model can easily be generated by a minor modification of the ADOL-C and other standard AD tools.
The discrepancy between the original function and the model is of second order in the distance from the development point. Consequently, successive piecewise linearization yields bundle type methods for unconstrained minimization and Newton type equation solvers, for which we establish
local convergence under standard assumptions.



Tuesday, 11:30 - 11:55 h, Room: H 2035, Talk 3

Sabrina Fiege
An exploratory line-search for piecewise smooth functions

Coauthors: Andreas Griewank, Andrea Walther


Many scalar or vector functions occurring in numerical applications are not continuously differentiable. This situation arises in particular through the use of l1 or l penalty terms or the occurrence of abs(), min() and max() in the problem function evaluations themselves. If no other nonsmooth elemental functions are present, generalized gradients and Jacobians of these piecewise smooth functions can now be computed in an AD like fashion by lexicographic differentiation as introduced by Barton & Kahn, Griewank and Nesterov.
However, at almost all points these generalized derivatives reduce to classical derivatives, so that the effort to provide procedures that can calculate generalized Jacobians nearly never pay off. At the same time the Taylor approximations based on these classical derivative singeltons may have a miniscule range of validity. Therefore, one alternative goal is to compute the critical step multiplier along a given search direction that leads to either the nearest kink. The achievement of this goal can not be guaranteed absolutely, but we verify necessary conditions. We will present numerical results verifying the theoretical results.


  pay day loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.