Optimization Online


Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method

Oleg Burdakov (oleg.burdakov***at***liu.se)
Christian Kanzow (kanzow***at***mathematik.uni-wuerzburg.de)
Alexandra Schwartz (schwartz***at***gsc.tu-darmstadt.de)

Abstract: Optimization problems with cardinality constraints are very dicult 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.

Keywords: Cardinality constraints, complementarity constraints, global minima, local minima, stationary points, M-stationarity, relaxation, regularization method

Category 1: Nonlinear Optimization

Category 2: Complementarity and Variational Inequalities

Category 3: Global Optimization

Citation: Preprint 324, Institute of Mathematics, University of Würzburg, Würzburg, Germany, July 2014.

Download: [PDF]

Entry Submitted: 07/19/2014
Entry Accepted: 07/19/2014
Entry Last Modified: 02/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society