Finite convergence of an active signature method to local minima of piecewise linear functions. (3rd September 2019)

• Record Type: Journal Article
• Authors: Griewank, Andreas; Walther, Andrea
• Is Part Of: Optimization methods and software. Volume 34:Number 5(2019)
• Page Start: 1035
• Page End: 1055
• Publication Date: 2019-09-03
• Subjects: Successive abs-linear minimization (SALMIN) -- quadratic regularization -- abs-normal form -- linear independence kink qualification (LIKQ) -- tangential stationarity -- Karush–Kuhn–Tucker (KKT) -- normal growth -- active set and signature; 90C56 -- 49J52; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1546856
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: We previously derived first-order (KKT) and second-order (SOSC) optimality conditions for functions defined by evaluation programs involving smooth elementals and absolute values. For this class of problems we showed that the algorithm of successive abs-linear minimization with a proximal term (SALMIN) achieves a linear or even quadratic rate of convergence under suitable assumptions. An implementation of SALMIN called LiPsMin has been implemented and tested. It uses a bundle-type method direction finder for the inner loop, i.e. the minimization of the local piecewise linear model with a quadratic proximal term. As a consequence the inner solver can get stuck at stationary points of the piecewise linearization and the overall algorithm can only guarantee Clarke stationarity of its cluster points. Here we present a new method that computes a local minimizer of the proximal model objective. As a consequence all cluster points of the outer iteration must be first-order minimal, which is also known as criticality in nonsmooth optimization. The active signature strategy employed very much resembles the classical method for convex QOPs and utilizes the same numerical linear algebra techniques. The new custom-made algorithm provides opportunities for structure exploitation like warm starts in the context of the nonlinear, outer loop.