Set-Convergence and Its Application: A Tutorial
- PDF / 1,112,782 Bytes
- 26 Pages / 439.642 x 666.49 pts Page_size
- 85 Downloads / 251 Views
Set-Convergence and Its Application: A Tutorial Johannes O. Royset1 Received: 21 February 2020 / Accepted: 22 September 2020 / © This is a U.S. government work and not under copyright protection in the U.S.; foreign copyright protection may apply 2020
Abstract Optimization problems, generalized equations, and a multitude of other variational problems invariably lead to the analysis of sets and set-valued mappings as well as their approximations. We review the central concept of set-convergence and explain its role in defining a notion of proximity between sets, especially for epigraphs of functions and graphs of set-valued mappings. The development leads to an approximation theory for optimization problems and generalized equations with profound consequences for the construction of algorithms. We also introduce the role of set-convergence in variational geometry and subdifferentiability with applications to optimality conditions. Examples illustrate the importance of set-convergence in stability analysis, error analysis, construction of algorithms, statistical estimation, and probability theory. Keywords Set-convergence · Epi-convergence · Graphical convergence · Weak convergence · Stability · Approximation theory · Variational geometry · Subdifferentiability · Truncated Hausdorff distance Mathematics Subject Classification (2010) 90-02 · 49-02 · 49J53
1 Introduction In the study of optimization problems, we quickly encounter a plethora of sets that might cause concerns for the classically trained: Sets of solutions are rarely singletons, local properties aren’t characterized by a single gradient vector but sets of subgradients, and the accuracy of function approximations is determined by the distance between certain sets. More general problems such as variational inequalities and generalized equations are even defined in terms of set-valued mappings. The mathematics of sets is therefore central to most analysis of optimization and variational problems beyond the elementary cases. In particular, a notion of convergence of sets becomes necessary, for example, to clarify what it means for a sequence of solution sets or a sequence of subgradient sets to converge as well as for many other concepts. Johannes O. Royset
[email protected] 1
Operations Research Department, Naval Postgraduate School, Monterey, CA, USA
J.O. Royset
In 1902, Painlev´e defined set-convergence in the sense we have it today, with Hausdorff and Kuratowski supporting its dissemination by including the topic in their books in 1927 and 1933, respectively1 . A set can be viewed as a point in a space of sets on which a topology and other mathematical structure can be defined. For the majority of the 20th century, setconvergence was studied from this point of view culminating with Beer’s monograph [10]. The growing number of variational problems in statistics, medicine, economics, business, engineering, and the sciences now drives a renewed interest in set-convergence from a more applied angle. In this article, we summarize key properties of set-c
Data Loading...
