Identifying structure of nonsmooth convex functions by the bundle technique

Aris Daniilidis, Claudia Sagastizábal, Mikhail Solodov

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)

Abstract

We consider the problem of minimizing nonsmooth convex functions, defined piecewise by a finite number of functions each of which is either convex quadratic or twice continuously differentiable with positive definite Hessian on the set of interest. This is a particular case of functions with primal-dual gradient structure, a notion closely related to the so-called vu space decomposition: At a given point, nonsmoothness is locally restricted to the directions of the subspace v, while along the subspace u the behavior of the function is twice differentiable. Constructive identification of the two subspaces is important, because it opens the way to devising fast algorithms for nonsmooth optimization (by following iteratively the manifold of smoothness on which superlinear u-Newton steps can be computed). In this work we show that, for the class of functions in consideration, the information needed for this identification can be obtained from the output of a standard bundle method for computing proximal points, provided a minimizer satisfies the nondegeneracy and strong transversality conditions. © 2009 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)820-840
JournalSIAM Journal on Optimization
Volume20
DOIs
Publication statusPublished - 26 Nov 2009

Keywords

  • Bundle method
  • Nonsmooth convex optimization
  • Partial smoothness
  • Primal-dual gradient structure
  • Proximal point
  • VU-decomposition

Fingerprint Dive into the research topics of 'Identifying structure of nonsmooth convex functions by the bundle technique'. Together they form a unique fingerprint.

Cite this