A gradient descent based algorithm for ℓp minimization

Shan Jiang, Shu-Cherng Fang, Tiantian Nie and Wenxun Xing

European Journal of Operational Research, 2020, vol. 283, issue 1, 47-56

Abstract: In this paper, we study the linearly constrained ℓp minimization problem with p ∈ (0, 1). Unlike those known works in the literature that propose solving relaxed ϵ-KKT conditions, we introduce a scaled KKT condition without involving any relaxation of the optimality conditions. A gradient-descent-based algorithm that works only on the positive entries of variables is then proposed to find solutions satisfying the scaled KKT condition without invoking the nondifferentiability issue. The convergence proof and complexity analysis of the proposed algorithm are provided. Computational experiments support that the proposed algorithm is capable of achieving much better sparse recovery in reasonable computational time compared to state-of-the-art interior-point based algorithms.

Keywords: Global optimization; Nonsmooth optimization; Nonconvex optimization; Gradient descent algorithm; KKT condition (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719309634
Full text for ScienceDirect subscribers only

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:eee:ejores:v:283:y:2020:i:1:p:47-56

DOI: 10.1016/j.ejor.2019.11.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().