Epi-convergent Smoothing with Applications to Convex Composite Functions

James V. Burke, Tim HoheiselSIAM J. Optim 2013 · DOI

TL;DR

This paper introduces a generalized framework for "epi-smoothing" functions, which are smooth approximations of non-smooth functions. This framework is then applied to a broad class of "convex composite functions," including those arising in general constrained optimization, providing a unified approach to analyzing and solving these problems. The key contribution is establishing "gradient consistency" for these smoothed approximations, ensuring that stationary points of the smooth approximations converge to stationary points of the original non-smooth problem.

What Problem Does This Paper Address?

Solving optimization problems, especially those involving non-smooth or composite functions, is a significant challenge in many fields, from machine learning to operations research. Traditional methods often struggle with the "sharp edges" and discontinuities introduced by non-smoothness. A common strategy is to replace the non-smooth function with a sequence of smooth approximations, hoping that the solutions to these approximations will converge to a solution of the original problem.

However, ensuring that these smooth approximations truly capture the behavior of the original non-smooth function, particularly concerning optimality conditions (like gradients), is not straightforward. This paper addresses this by developing a rigorous mathematical framework, "epi-convergence," to analyze the convergence of these smoothing techniques. Specifically, it aims to extend existing smoothing methods for convex functions to a more general class of "convex composite functions" and to guarantee that these smoothed versions maintain desirable properties, such as gradient consistency, which is crucial for reliable optimization algorithms.

Methods

The core of the paper's methodology lies in the concept of epi-convergence. This is a powerful tool from variational analysis that describes the convergence of the epigraphs (the set of points above the graph) of a sequence of functions. The authors define epi-smoothing functions as a sequence of continuously differentiable functions that epi-converge to the original non-smooth function as a smoothing parameter approaches zero.

They establish an elementary calculus for epi-smoothing functions, allowing them to combine and compose these smoothed functions. A key technique is infimal convolution, which is used to construct smoothing functions for convex functions. The paper then extends these ideas to convex composite functions, which are functions of the form $f(x) = g(H(x))$, where $g$ is a non-smooth convex function and $H$ is a smooth mapping. They leverage Moreau envelopes and proximal mappings as specific examples of smoothing techniques.

Crucially, the paper connects these epi-smoothing properties to gradient consistency, a condition that ensures the gradients of the smoothed functions accurately reflect the subdifferential (generalized gradient) of the original non-smooth function. This is achieved through careful analysis of limiting subdifferentials and normal cones.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and general classes of functions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Epi-convergence as a unifying framework: The paper demonstrates that epi-convergence provides a robust mathematical foundation for analyzing various smoothing techniques, unifying disparate approaches under a single theoretical umbrella.
  • Calculus for epi-smoothing: The development of a calculus for epi-smoothing functions simplifies the construction and analysis of smoothed approximations for complex functions.
  • Generalization to convex composite functions: The paper successfully extends existing smoothing results from convex functions to the broader and more practically relevant class of convex composite functions, including those arising in general constrained optimization.
  • Gradient consistency is preserved: A central finding is that under appropriate conditions, the proposed epi-smoothing approach preserves gradient consistency, meaning that stationary points of the smoothed problems are indeed related to stationary points of the original non-smooth problem. This is vital for the theoretical guarantees of optimization algorithms.
  • Moreau envelopes and EPLQ functions: The paper highlights how Moreau envelopes and Extended Piecewise Linear-Quadratic (EPLQ) functions fit naturally into the epi-smoothing framework, demonstrating its applicability to well-known and important function classes.

Key Results

  • The paper establishes conditions under which infimal convolutions and Moreau envelopes of convex functions act as epi-smoothing functions.
  • It provides a framework for constructing epi-smoothing functions for convex composite functions $f(x) = g(H(x))$, showing how the smoothing properties of $g$ can be transferred to $f$.
  • For constrained optimization problems of the form $\min \phi(x)$ subject to $h(x) \in C$, the paper shows that a specific smoothing function based on the distance function to the constraint set $C$ is an epi-smoothing function.
  • Crucially, it proves that for problems satisfying a basic constraint qualification, sequences of approximate stationary points of the smoothed problems converge to Karush-Kuhn-Tucker (KKT) points of the original non-smooth problem. This holds even for infeasible cluster points.

Limitations and Future Work

  • Assumptions on the smoothing function: While the framework is general, specific results often rely on assumptions about the properties of the underlying smoothing functions (e.g., 1-coercivity of the kernel function $w$ in infimal convolution).
  • Complexity of implementation: While the theory is powerful, the practical implementation of these smoothing techniques might still involve careful tuning of parameters and choices of smoothing functions.
  • Future Work: The authors suggest that their results can be used to develop powerful algorithms for solving optimization problems that utilize epi-smoothing functions. They also hint at further applications and extensions of the theory, particularly in the context of generalized differentiation and variational analysis. The paper's focus on theoretical guarantees for convergence and optimality conditions lays the groundwork for developing more robust and efficient optimization solvers.

Summary updated

BibTeX
@article{burke2013epi,
  author = {James V. Burke and Tim Hoheisel},
  title = {{Epi-convergent Smoothing with Applications to Convex Composite Functions}},
  journal = {SIAM J. Optim},
  year = {2013},
  doi = {10.1137/120889812},
}
Figure