Doctoral Dissertation Defense: Saeed Damadi

We make three theoretical contributions.

First, for an objective function whose restricted gradient Lipschitz constant is L > 0, we extend the valid step length range to include the boundary case 1/L, which was previously untreated in nonconvex and sparse settings. Using a new descent lemma based on a term ignored in the literature, we derive an upper bound linking two consecutive objective values of projected steps, which holds even at 1/L. Using this lemma, we show via a new argument that any accumulation point is a projection-based stationary point. These results apply to the gradient projection scheme on a general closed constraint set, including sparse optimization as a special case.

Second, we introduce the concept of semi-symmetry, i.e., exhibiting symmetry properties only over certain index subsets. We show how these properties can be exploited to reduce computational complexity. We demonstrate that semi-permutation symmetric sets preserve certain order in projection, while semi-sign symmetric sets enable sign-alignment procedures, both of which simplify the projection computation. We provide projection results for semi-symmetric sets over single or multiple index sets. When the non-symmetric part is large, we develop comparison techniques using dominating and inferior index subsets to efficiently reduce computational complexity. We perform numerical tests on the joint sparsity and group sparsity problem and sparse portfolio optimization, and show improved performance.

Third, we introduce a framework of general sorting functions for sparse projection beyond fully symmetric constraint sets. We establish necessary and/or sufficient conditions for the existence of simple sorting functions—those defined by univariate real-valued functions—and prove that sets admitting such functions possess partial permutation and/or partial sign symmetry properties, among many other properties. Importantly, we demonstrate through examples that neither full symmetry nor the monotone projection property is needed for simple sorting functions to exist, and we establish the piecewise minimum-order property as a sufficient condition, along with other conditions, thereby broadening the class of problems that can be solved via sorting function based sparse projection algorithms.