On the Exploitation of Sparsity in Regression and Global Optimization Models

This dissertation is concerned with the employment of sparsity in regression and global optimization contexts. Sparse regression models are useful in many contexts because of, for instance, their robustness to noisy data, their lightweight and, in some cases, their out-of-sample prediction performances. In the present thesis three different classes of problems are considered. For each of these classes, specialized optimization methods are used in order to build sparse regression models. The first part of the thesis is concerned with the problem of best subset selection in linear regression models. In order to deal with this class of problems, a two-block decomposition strategy is proposed. After a theoretical analysis of the convergence of the algorithm, an extensive comparison with respect to the state-of-the-art approaches present in the literature have been performed, showing the superiority of the method both in terms of CPU time and quality of the solution. A modification of this scheme for model selection and fitting of auto-regressive models is also proposed. The second part of this thesis is concerned with the problem of best subset selection in logistic regression models. Firstly, a piecewice approximation of the convex log-likelihood function is considered; secondly, in order to deal with large scale problems, a block coordinate descent decomposition strategy is proposed. Also here, a theoretical analysis about the convergence of the proposed procedure is provided, characterizing the optimality properties of the solution. A wide numerical comparison shows the effectiveness of the proposed approach with respect to state-of-the-art solvers, especially in high-dimensional problems. Finally, the last part of the thesis deals with the problem of building an accurate approximation for a noisy function. Here, by making use of the expressiveness of radial basis functions (RBF) and the robustness of a sparse regression model, very accurate models of the true function could be built. In addition to some theoretical analysis, an extensive numerical comparison is performed. First of all, the quality of the sparse RBF regression models is assessed on large datasets. In the second place, the sparse RBF regression models are exploited to build good surrogate models in global optimization contexts for noisy and expensive functions. Numerical results show that the proposed method is competitive with respect to alternatives available in the literature.