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.
Citation
Yachaytech, Urcuqui, Ecuador