Doubly Majorized Algorithm for Sparsity-Inducing Optimization Problems with Regularizer-Compatible Constraints

We consider a class of sparsity-inducing optimization problems whose constraint set is regularizer-compatible, in the sense that, the constraint set becomes easy-to-project-onto after a coordinate transformation induced by the sparsity-inducing regularizer. Our model is general enough to cover, as special cases, the ordered LASSO model in Tibshirani and Suo (Technometrics 58:415–423, 2016) and its variants with some commonly used nonconvex sparsity-inducing regularizers. The presence of both the sparsity-inducing regularizer and the constraint set poses challenges on the design of efficient algorithms. In this paper, by exploiting absolute-value symmetry and other properties in the sparsity-inducing regularizer, we propose a new algorithm, called the doubly majorized algorithm (DMA), for this class of problems. The DMA makes use of projections onto the constraint set after the coordinate transformation in each iteration, and hence can be performed efficiently. Without invoking any commonly used constraint qualification conditions such as those based on horizon subdifferentials, we show that any accumulation point of the sequence generated by DMA is a so-called ψ_opt -stationary point, a new notion of stationarity we define as inspired by the notion of L-stationarity in Beck and Eldar (SIAM J Optim 23:1480–1509, 2013) and Beck and Hallak (Math Oper Res 41:196–223, 2016). We also show that any global minimizer of our model has to be a ψ_opt -stationary point, again without imposing any constraint qualification conditions. Finally, we illustrate numerically the performance of DMA on solving variants of ordered LASSO with nonconvex regularizers.