In the paper [11] we derived first order (KKT) and second order (SSC) optimality conditions for functions defined by evaluation programs involving smooth elementals and absolute values. For this class of problems we showed in [12] that the natural algorithm of successive piecewise linear optimization with a proximal term (SPLOP) achieves a linear or even quadratic rate of convergence under suitable assumptions. A version of SPLOP called LiPsMin has already been implemented and tested in [13, 3]. In this paper, we develop a more efficient method for the inner loop, i.e., the minimization of the local piecewise linear model with a quadratic regularization term. Rather than completely solving each Quadratic Optimization Problem (QOP) on one of the signature domains, we may switch between them as soon as we have reached a merely stationary point. The resulting active set and signature strategy very much resembles the classical method for convex QOPs and utilizes the very same numerical linear algebra techniques. Preliminary numerical results document an order of magnitude improvement compared to the original proof of concept implementation, which was already competitive with alternative nonsmooth optimization methods.
Article
View An Algorithm for Piecewise Linear Optimization of Objective Functions in Abs-normal Form