Sparse Optimization: Optimality Conditions and Algorithms
Sparse optimization problems are problems containing a combinatorial term that directly depends on the sparsity of the solution, i.e. on the number of nonzero elements in the solution, and as such are hard to solve in general. These problems appear in almost any field, as sparse solution is a common goal in many applications. Sparse optimization problems can be divided into two classes: constrained, in which the number of nonzero elements is bounded above; penalized, in which the objective function contains a penalty for the number of nonzero elements. These two general models will be discussed, and optimality conditions and algorithms for each will be presented. In particular, efficient algorithms that obtain a solution to the fundamental problems of the sparse orthogonal projection and the sparse proximal mapping will presented and used in the process of defining optimality conditions for the general problems, and to prove a hierarchy between them. The group-sparsity problem, in which the number of nonzero elements is replaced by the number of nonzero groups, will also be discussed. This model is highly versatile and is suited for problems in which the decision variables might be correlated, or a-priori be partitioned into non-overlapping groups belonging to different sets.
This talk comprises some of the study conducted under the supervision and guidance of Prof. Amir Beck as part of my M.Sc and Phd research.