Theory and algorithmic applications of the proximal mapping and Moreau envelope

The Moreau envelope and the proximal mapping have been objects of great interest for optimizers since their conception more than half a century ago. They provide us with many desirable properties; for instance, the Moreau envelope of a convex function is smooth (differentiable) while the function may not be, and the envelope maintains the same minimum value and the same set of minimizers as the function. This is a great advantage to have when the objective is to minimize the function, because standard Calculus methods can then be applied to minimize the smooth envelope. From a computational standpoint, the proximal mapping has given rise to many efficient minimization algorithms, such as the proximal point method and proximal bundle methods. Derivative-free optimization methods continue to grow in importance and popularity. The term ‘derivative-free’ refers to the fact that for the function to be minimized, (sub)gradient information is either unavailable or inconvenient to use, thus necessitating an algorithm that does not require subgradients. Such algorithms rely on constructs such as the simplex gradient to obtain good-quality approximations of subgradients and use the approximations in derivative-free versions of the proximal routines. The present work is divided into three major parts. Part I provides a history of the Moreau envelope, with the goal of illustrating its usefulness and some of its successes over the past few decades. Part II contains new theoretical results that involve the Moreau envelope and the proximal mapping on many topics, including prox-boundedness, convex functions with unique and/or strong minimizers, Baire category and epiconvergence. Part III is the algorithmic section, where a proximal bundle method is converted to derivative-free format. Using this result, a particular minimization algorithm for convex finite-max functions called the VU-algorithm is presented and also converted to derivative-free. The new method is proved convergent and numerical results are included.