Optimization Online


Computing Proximal Points on Nonconvex Functions

Warren L Hare (whare***at***cecm.sfu.ca)
Claudia Sagastizabal (sagastiz***at***impa.br)

Abstract: The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. As such, inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. A first step towards implementable methods would be to effectively approximate nonconvex proximal points. This paper presents a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are lower-C^2. To support the effectiveness of the approach, encouraging preliminary numerical testing is reported.

Keywords: Nonconvex Optimization, Nonsmooth Optimization, Proximal point, Prox-regular, lower-C^2

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Convex and Nonsmooth Optimization (Generalized Convexity/Monoticity )

Citation: to appear: Journal of Mathematical Programming

Download: [PDF]

Entry Submitted: 06/26/2005
Entry Accepted: 06/27/2005
Entry Last Modified: 10/04/2006

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 Programming Society