On the Minimization Over Sparse Symmetric Sets: Projections, Optimality Conditions, and Algorithms

We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve because the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to be nonconvex. We begin with a study of the properties of the orthogonal projection operator onto sparse symmetric sets. Based on this study, we derive efficient methods for computing sparse projections under various symmetry assumptions. We then introduce and study three types of optimality conditions: basic feasibility, L-stationarity, and coordinatewise optimality. A hierarchy between the optimality conditions is established by using the results derived on the orthogonal projection operator. Methods for generating points satisfying the various optimality conditions are presented, analyzed, and finally tested on specific applications.