Characterizing and testing subdifferential regularity in piecewise smooth optimization

Abstract:

Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max and min operators are piecewise smooth. They can be approximated by piecewise linear functions in abs-linear form. Using this second-order approximation, in [Optim. Methods Softw., 31 (2016), pp. 904–930] we derived local first- and second-order minimality conditions for the underlying piecewise smooth functions. They are necessary and sufficient, respectively. These generalizations of the classical KKT and sufficient second-order theory assumed that the given abs-linear approximation satisfies the linear independence kink qualification (LIKQ). In this paper we relax LIKQ to the Mangasarian–Fromovitz kink qualification (MFKQ) and develop constructive conditions for several local convexity concepts. These are the existence of a supporting hyperplane at a given point for the function itself (SUP), the same for its local piecewise linearization (FOS), and the convexity of its local piecewise linearization on a neighborhood (FOC). As a consequence we show that first-order convexity in the sense of (FOC) is always required by subdifferential regularity (REG) as defined in Rockafellar and Wets [Variational Analysis, Springer, Cham, 1998], and is even equivalent to it under MFKQ. Whereas it was observed by Griewank and Walther that testing for local minimality (MIN) is polynomial under LIKQ, in this paper we show that, even under this strong linear independence kink qualification, testing for FOC and thus REG is co-NP-complete. We conjecture that this is also true for testing MFKQ itself.

Año de publicación:

2019

Keywords:

• Linear independence kink qualification
• Subdifferential regularity
• Mangasarin–Fromovitz kink qualification
• Clarke generalized gradient
• Mordukhovich subdifferential
• abs-normal form
• First-order-convexity

Fuente:

scopus