.Minimization problems with nonLipschitz, nonconvex regularization terms have wide applications in image restoration, signal reconstruction and variable selection. On ?2?p (0 < p < 1) regularized minimization, we show that_nding a global optimal solution is strongly NPhard. On the other hand, we present lower bounds of nonzero entries in every local optimal solution without assumptions on the data matrix. Such lower bounds can be used to classify zero and nonzero entries in local optimal solutions and select regularization parameters for desirable sparsity of solutions. We propose a smoothing quadratic regularization algorithm for unconstrained problems and a firstorder interior point algorithm for box constrained problems and show the worstcase iteration complexity for finding an escaled firstorder stationary point is O(e^{2}). Moreover, we develop a smoothing trust region Newton method and a secondorder interior point algorithm for finding an esecondorder stationary point. Although the two secondorder algorithms cost more computational time than that of the firstorder algorithms in each iteration, the worstcase iteration complexity for finding an e(scaled) secondorder stationary point is reduced to O(e^{2/3}). Examples are presented to illustrate the theory and algorithms.
