Optimization Online


Characterizing and testing subdifferential regularity for piecewise smooth objective functions

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

Abstract: Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT and SSC theory assumed that the given representation of the function satisfies the Linear- Independence-Kink-Qualification (LIKQ). In this paper we relax LIKQ to the Mangasarin-Fromovitz- Kink-Qualification (MFKQ) and develop a constructive condition for a local convexity concept, i.e., the convexity of the local piecewise linearization on a neighborhood. As a consequence we show that this first order convexity (FOC) is always required by subdifferential regularity (REG) as defined in [20], and is even equivalent to it under MFKQ. Whereas it was observed in [7] that testing for MIN is polynomial under LIKQ, we show here that even under this strong kink qualification, testing for FOC and thus REG is co-NP complete. We conjecture that this is also true for testing MFKQ itself.

Keywords: Subdifferential Regularity, First-Order-Convexity, Clarke Gradient, Linear-Independence-Kink-Qualification, Mordukhovich Gradient, Mangasarin-Fromovitz-Kink-Qualification, Abs-Normal-Form

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 11/05/2017
Entry Accepted: 11/05/2017
Entry Last Modified: 11/05/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