Optimization Online


An Algorithm for Piecewise Linear Optimization of Objective Functions in Abs-normal Form

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

Abstract: 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.

Keywords: Successive Piecewise Linear Optimization (SPLOP), Quadratic Regularization, Abs-Normal Form, Linear Independence Kink Qualification (LIKQ), Tangential Stationarity, Karush Kuhn Tucker (KKT), Normal Growth, Active Set and Signature

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 12/22/2017
Entry Accepted: 12/22/2017
Entry Last Modified: 12/22/2017

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