Computing Proximal Points on Nonconvex Functions

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.


to appear: Journal of Mathematical Programming



View Computing Proximal Points on Nonconvex Functions