Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
2016 (English)In: SIAM Journal on Optimization, ISSN 1052-6234, E-ISSN 1095-7189, Vol. 26, no 1, 397-425 p.Article in journal (Refereed) Published
Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discrete optimization. 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 the local minima is also discussed in detail. Since our reformulation is a minimization problem in continuous variables, it allows to apply ideas from that field 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 cardinality constraints. This regularization method is shown to be globally convergent to a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.
Place, publisher, year, edition, pages
2016. Vol. 26, no 1, 397-425 p.
Cardinality constraints, global minima, local minima, stationary points, M-stationarity, relaxation, regularization method
IdentifiersURN: urn:nbn:se:liu:diva-124611DOI: 10.1137/140978077ISI: 000373631500015OAI: oai:DiVA.org:liu-124611DiVA: diva2:901202