Optimization Online


Semi-Smooth Second-order Type Methods for Composite Convex Programs

Xiantao Xiao(xtxiao***at***dlut.edu.cn)
Yongfeng Li(1200010733***at***pku.edu.cn)
Zaiwen Wen(wenzw***at***pku.edu.cn)
Liwei Zhang(lwzhang***at***dlut.edu.cn)

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.

Download: [PDF]

Entry Submitted: 03/25/2016
Entry Accepted: 03/25/2016
Entry Last Modified: 03/25/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society