Iterative reweighted methods for ℓ₁- ℓ_p minimization

In this paper, we focus on the ℓ₁- ℓ_p minimization problem with 0 < p< 1 , which is challenging due to the ℓ_p norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of ℓ₁- ℓ_p minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous ϵ-approximation to ℓ_p norm, we design several iterative reweighted ℓ₁ and ℓ₂ methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of ℓ₁- ℓ_p minimization. This result, in particular, applies to the iterative reweighted ℓ₁ methods based on the new Lipschitz continuous ϵ-approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter ϵ is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods.