Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method
Oleg Burdakov (oleg.burdakovliu.se)
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.
Entry Submitted: 07/19/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|