Concave programming for minimizing the zero-norm over polyhedral sets (Q989849)

Given a non empty polyhedral set \(P\subset R^n\) , consider the NP-hard problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This combinatorial optimization problem arises in various fields such as machine learning, pattern recognition, signal processing. The authors of this paper propose two new smooth approximations of the zero-norm function, where the approximating functions are separable and concave. They formally prove the equivalence between the approximating problems and the original nonsmooth problem. To this aim, they propose two formulations of concave problems and prove their theoretic equivalence to the original problems. Finally, they propose an effective and efficient version of the Frank-Wolfe algorithm for the minimization of concave separable functions over polyhedral sets in which variables which are null at an iteration are eliminated for all the following ones, with significant savings in computational time, and prove the global convergence of the method. The final chapter of the paper summarizes the numerical results on test problems (they use four different independently structured datasets) showing both the usefulness of the new concave formulations and the efficiency in terms of computational time of the implemented minimization algorithm.