Doubly majorized algorithm for sparsity-inducing optimization problems with regularizer-compatible constraints

Tianxiang Liu (), Ting Kei Pong () and Akiko Takeda ()
Additional contact information
Tianxiang Liu: Tokyo Institute of Technology
Ting Kei Pong: Hong Kong Polytechnic University
Akiko Takeda: University of Tokyo

Computational Optimization and Applications, 2023, vol. 86, issue 2, No 4, 553 pages

Abstract: Abstract 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 $$\psi _\textrm{opt}$$ ψ 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 $$\psi _\textrm{opt}$$ ψ 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.

Keywords: Constrained problem; Majorized algorithm; Ordered LASSO; Stationary point (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-023-00503-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:86:y:2023:i:2:d:10.1007_s10589-023-00503-1

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-023-00503-1

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().