In this paper, we propose a smoothing sequential quadratic programming (SSQP) algorithm for solving a class of nonsmooth nonconvex, perhaps even non-Lipschitz minimization problems, which has wide applications in statistics and sparse reconstruction. At each step, the SSQP algorithm solves a strongly convex quadratic minimization problem with a diagonal Hessian matrix, which has a simple closed-form solution. The SSQP algorithm is easy to implement and has almost no time cost to solve the convex quadratic minimization subproblems. We show that the worst-case complexity of reaching an $\varepsilon$ scaled stationary point is $O(\varepsilon^{-2})$. Moreover, if the objective function is locally Lipschitz, the SSQP algorithm with a slightly modified updating scheme can obtain an $\varepsilon$ Clarke stationary point at most $O(\varepsilon^{-3})$ steps.
Citation
Department of Applied Mathematics, The Hong Kong Polytechnic University, February, 2012