Cardinality constraints are used to model the fact that the solution of an optimization
problem is expected or desired to be sparse. They impose an upper bound on the cardinality of the support of feasible points. An objective function, possibly nonlinear, is to be
minimized subject to the cardinality constraint as well as further nonlinear constraints.
Applications of cardinality constraints include portfolio optimization, compressed sensing
or the subset selection problem in regression.
Cardinality constrained optimization problems are difficult to solve, since the mapping
of a vector to the cardinality of its support is a discontinuous function. Even testing
feasibility is known to be NP-hard (Bienstock 1996). Solution techniques for cardinality constrained
optimization problems include the reformulation as a mixed-integer nonlinear program or
the approximation of the cardinality constraint with a l1 -norm.
We follow an approach by Burdakov, Kanzow and Schwartz which is a reformulation
of the cardinality constraint with complementarity constraints using continuous auxiliary variables. This opens up the possibility to use methods from nonlinear optimization.
The reformulation possesses a strong similarity to a mathematical program with complementarity constraints (MPCC) and, like an MPCC, does not fulfil standard constraint
qualifications. We use the strong link between the aforementioned reformulation of cardinality constrained optimization problems and MPCCs to derive optimality conditions
and numerical methods. Particularly we investigate second order optimality conditions for
the reformulation. We then use these to derive new convergence results for a Scholtes-type
regularization.
This work is supported by the ’Excellence Initiative’ of the German Federal and State
Governments and the Graduate School of Computational Engineering at Technische Universität Darmstadt Darmstadt.