| Sparsity (or parsimonious) optimization is widely used in a range of fields, such as compressed sensing, image and signal recovery, statistical variable selection, machine learning, portfolio and risk management and so on. It mainly examines the trade-off between optimality and the number independent variables to optimize over. In this paper, we study the nonconvex regularized sparsity optimization, which can effectively achieve much more sparsity than the traditionally used convex regularized sparsity optimization. We establish convergence properties for both the optimal function value and the optimal solution sets when the nonconvex regularization term converges to the zero-norm (rho0), which is the exact representation of sparsity. We prove a partial equivalence between the constrained nonconvex sparsity problem and the unconstraint sparsity problem with the nonconvex penalty. The algorithm we develop to solve the nonconvex regularized sparsity optimization problem is the iteratively re-weighted convex programming (IRCP). It is a very general iterative re-weighting scheme, far more than the popular re-weighted L1 or L2 algorithm. The convergence theorem of the IRCP algorithm is provided. We also study a special example of the nonconvex regularized sparsity optimization, which is Bridge regression. Some of its properties and statistical characteristics are provided. Note that the above properties and the algorithm are established for a generalized nonconvex regularized sparsity optimization. The primary objective function f is not limited to be differentiable, and it may have extended real values. The nonconvex regularization terms includes a wide class of candidates, which is not restricted to be the ℓq norm. We report the numerical results of applying the nonconvex sparsity optimization with IRCP algorithm to the classic signal recovery problems and a statistical variable selection problem.;In addition, we also study the general unconstrained nonconvex nonsmooth optimization problems. Gradient sampling (GS) algorithm was first introduced by Burke, Lewis and Overton [55]. Aiming to reduce the total number of evaluations of the gradient and the function, we propose several different modifications to the GS algorithm. The proof of convergence for an augmented GS algorithm is given. The performance of all augmented GS algorithms is compared with the original GS algorithms by testing three classic examples. In particular, we adjust the GS algorithm to the minmax optimization problem with much fewer gradients sampled. The corresponding convergence theorem of the adjusted GS algorithm for this problem is provided. Although we know that the GS algorithm may be applied to non-Lipschitz functions, it has not been theoretically proved. The objective function is restricted to be at least locally-Lipschitz [55]. In this paper, we extend the convergence theorem to directionally Lipschitzian functions. |
