# A Continuous Reformulation of Cardinality Constraint Optimization Problems

Many practical and theoretical questions from a vast range of areas in science and industry can be modelled using a nonlinear constrained optimization problem. In this project a certain type of constraint is of special interest to us: the Cardinality Constraint. Let $$\kappa\in\mathbb{N}$$. The Cardinality Constraint is given by

\begin{equation*} |\text{supp}(x)|:=|\{i\in\{1,\dots,n\}\,:\,x_i\not=0\}|\leq \kappa, \end{equation*}

for a vector $$x\in\mathbb{R}^n$$. This constraint ensures that only a maximum number $$\kappa$$ of entries of the vector $$x$$ are nonzero. Cardinality constrained optimization problems are of the form

\begin{align} \min\limits_{x\in\mathbb{R}^n}\ f(x)\quad \text{s.t.}\quad x\in X,\quad|\text{supp}(x)|\leq \kappa. &\notag \end{align}

where $$f:\mathbb{R}^n\rightarrow\mathbb{R}$$ is a given objective function. Further constraints can be modelled with the set $$X\subseteq\mathbb{R}^n$$.

A recent approach for solving the above optimization problem, is to reformulate the cardinality constraint with complementarity constraints using continuous auxiliary variables (see Burdakov, Kanzow, Schwartz 2015). This continuous reformulation opens up the possibility to use methods from nonlinear programming to compute solutions. However, standard conditions that are perquisites for such results do not hold for the reformulation. It possesses a strong similarity to mathematical programs with complementarity constraints (MPCC), a class of optimization problems that also require a customized theory and numerical methods.

The goal of this project is to use the strong link between the aforementioned reformulation of cardinality constrained problems and MPCCs, to transfer existing knowledge on MPCCs and thus obtain new insights into cardinality constrained optimization problems.

# Contact

Max Bucher
M.Sc.

 Address: Dolivostr. 15 D-64293 Darmstadt Germany Phone: +49 6151 16 - 24385 Fax: +49 6151 16 - 24404 Office: S4|10-221 Email: bucher (at) gsc.tu...