Theory and algorithms for sparsity constrained optimization problems

This dissertation is concerned with mathematical optimization problems where a sparsity constraint appears. The sparsity of the solution is a valu- able requirement in many applications of operations research. Several classes of very different approaches have been proposed in the literature for this sort of problems; when the objective function is nonconvex, in presence of difficult additional constraints or in the high-dimensional case, the problem shall be addressed as a continuous optimization task, even though it naturally has an intrinsic combinatorial nature. Within this setting, we first review the existing knowledge and the theoretical tools concerning the considered problem; we try to provide a unified view of parallel streams of research and we propose a new general stationarity condition, based on the concept of neighborhood, which somehow allows to take into account both the continuous and the combinatorial aspects of the problem. Then, after a brief overview of the main algorithmic approaches in the related literature, we propose suitable variants of some of these schemes that can be effectively employed in complex settings, such as the nonconvex one, the derivative-free one or the multi-objective one. For each of the proposed algorithms we provide a detailed convergence analysis showing that these methods enjoy important theoretical guarantees, in line with the state-of-the-art algorithms. Afterwards, exploiting the newly introduced concept of stationarity, we propose a completely novel algorithmic scheme that, combining continuous local searches and discrete moves, can be proved to guarantee stronger theoretical properties than most approaches from the literature and to exhibit strong exploration capabilities in a global optimization perspective. All the proposed algorithms have finally been experimentally tested on a benchmark of relevant problems from machine learning and decision science applications. The computational results show the actual quality of the proposed methods when practically employed.