A practical second-order optimality condition for cardinality-constrained problems with application to an augmented Lagrangian method

This paper addresses the mathematical programs with cardinality constraints (MPCaC). We first define two new tailored (strong and weak) second-order necessary conditions, MPCaC-SSONC and MPCaC-WSONC. We then propose a constraint qualification (CQ), namely, MPCaC-relaxed constant rank constraint qualification (MPCaC-RCRCQ), and establish the validity of MPCaC-SSONC at minimizers under this new CQ. All proposed concepts are based on the so-called M-stationarity, which is the suitable first-order stationarity for MPCaC. Furthermore, they are defined using only original variables, without the help of exogenous auxiliary variables commonly considered in this context. We illustrate the applicability of MPCaC-WSONC to derive global convergence for a second-order augmented Lagrangian algorithm under MPCaC-RCRCQ. The advantages of the tailored MPCaC-WSONC over the standard WSONC are discussed, showing that MPCaC-WSONC is the appropriate condition to study the global convergence of algorithms for MPCaC.

Article

Download

View PDF