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 the concepts proposed here 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 auxiliary variables of an augmented problem commonly considered in this context. This makes the proposed second-order stationarity concepts suitable to MPCaC. Moreover, we discuss the application of a second-order augmented Lagrangian algorithm on MPCaCs and prove its global convergence to MPCaC-WSONC points under our MPCaC-RCRCQ. The relationship between the tailored MPCaC-WSONC and the standard WSONC (applied to a reformulated problem) are also discussed and shows that the tailored condition is more adequate for studying global convergence of algorithms for the MPCaC context.

Article

Download

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