Proximal quasi-Newton methods for nondifferentiable convex optimization

Xiaojun Chen, Masao Fukushima

Research output: Journal article publicationJournal articleAcademic researchpeer-review

43 Citations (Scopus)

Abstract

This author's work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan This paper proposes an implementable proximal quasi-Newton method for minimizing a non-differentiable convex function f in ℛn. The method is based on Rockafellar's proximal point algorithm and a cutting-plane technique. At each step, we use an approximate proximal point pa(xk) of xkto define a νk∈ ∂εkf(pa(xk)) with εk≤ α∥νk∥, where α is a constant. The method monitors the reduction in the value of ∥νk∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥νk∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance of the method.
Original languageEnglish
Pages (from-to)313-334
Number of pages22
JournalMathematical Programming, Series B
Volume85
Issue number2
DOIs
Publication statusPublished - 1 Jan 1999
Externally publishedYes

Keywords

  • Bundle methods
  • Cutting-plane method
  • Nondifferentiable convex optimization
  • Proximal point
  • Quasi-newton method

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this