Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method
2014 (English)Report (Other academic)
Optimization problems with cardinality constraints are very diﬃcult mathematical programs which are typically solved by global techniques from discreteoptimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between thelocal minima is also discussed in detail. Since our reformulation is a mini-mization problem in continuous variables, it allows to apply ideas from thatﬁeld to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinalityconstraints. This regularization method is shown to be globally convergentto a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.
Place, publisher, year, edition, pages
Würzburg: University of Würzburg , 2014. , 41 p.
Cardinality constraints, global minima, local minima, stationary points, M-stationarity, relaxation, regularization method
IdentifiersURN: urn:nbn:se:liu:diva-112137OAI: oai:DiVA.org:liu-112137DiVA: diva2:763733