Semi-Smooth Second-order Type Methods for Composite Convex Programs
Abstract: The goal of this paper is to study approaches to bridge the gap between first-order and second-order type methods for composite convex programs. Our key observations are: i) Many well-known operator splitting methods, such as forward-backward splitting (FBS) and Douglas-Rachford splitting (DRS), actually define a possibly semi-smooth and monotone fixed-point mapping; ii) The optimal solutions of the composite convex program and the solutions of the system of nonlinear equations derived from the fixed-point mapping are equivalent. Solving the system of nonlinear equations rediscovers a paradigm on developing second-order methods. Although these fixed-point mappings may not be differentiable, they are often semi-smooth and its generalized Jacobian matrix is positive semidefinite due to monotonicity. By combining a regularization approach and a known hyperplane projection technique, we propose an adaptive semi-smooth Newton method and establish its convergence to global optimality. A semi-smooth Levenberg-Marquardt (LM) method in terms of handling the nonlinear least squares formulation is further presented. In practice, the second-order methods can be activated until the first-order type methods reach a good neighborhood of the global optimal solution. Preliminary numerical results on Lasso regression, logistic regression, basis pursuit, linear programming and quadratic programming demonstrate that our second-order type algorithms are able to achieve quadratic or superlinear convergence as long as the fixed-point residual of the initial point is small enough.
Keywords: composite convex programs, operator splitting methods, proximal mapping, semi-smoothness, Newton method, Levenberg-Marquardt method
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Citation: Manuscript, submitted for publication.
Entry Submitted: 03/25/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|