Optimization Online


First and second order optimality conditions for piecewise smooth objective functions

Andreas Griewank (griewank***at***yachaytech.edu.ec)
Andrea Walther (andrea.walther***at***uni-paderborn.de)

Abstract: Any piecewise smooth function that is specified by an evaluation procedures involving smooth elemental functions and piecewise linear functions like min and max can be represented in the so-called abs-normal form. By an extension of algorithmic, or automatic differentiation, one can then compute certain first and second order derivative vectors and matrices that represent a local piecewise linearization and provide additional curvature information. On the basis of these quantities we characterize local optimality by first and second order necessary and sufficient conditions, which generalize the corresponding KKT theory for smooth problems. The key assumption is the Linear Independence Kink Qualifikation (LIKQ), a generalization of LICQ familiar from NLOP. It implies that the objective has locally a so-called U-V decomposition and renders everything tractable in terms of matrix factorizations and other simple linear algebra operations. By yielding descent directions whenever they are violated the new optimality conditions point the way to a superlinearly convergent generalized QP solver, which is currently under development. We exemplify the theory on two nonsmooth examples of Nesterov.

Keywords: Abs-normal form, Piecewise linearization, Karush-Kuhn-Tucker, Second order optimality, projected Hessian, tangential stationarity, normal growth, U-V shape

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Yachaytech, Urcuqui, Ecuador

Download: [PDF]

Entry Submitted: 11/06/2015
Entry Accepted: 11/06/2015
Entry Last Modified: 03/11/2016

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