Approximations of semicontinuous functions with applications to stochastic optimization and statistical estimation
- PDF / 446,351 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 185 Views
Series A
Approximations of semicontinuous functions with applications to stochastic optimization and statistical estimation Johannes O. Royset1 Received: 26 June 2018 / Accepted: 27 June 2019 © This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2019
Abstract Upper semicontinuous (usc) functions arise in the analysis of maximization problems, distributionally robust optimization, and function identification, which includes many problems of nonparametric statistics. We establish that every usc function is the limit of a hypo-converging sequence of piecewise affine functions of the difference-of-max type and illustrate resulting algorithmic possibilities in the context of approximate solution of infinite-dimensional optimization problems. In an effort to quantify the ease with which classes of usc functions can be approximated by finite collections, we provide upper and lower bounds on covering numbers for bounded sets of usc functions under the Attouch-Wets distance. The result is applied in the context of stochastic optimization problems defined over spaces of usc functions. We establish confidence regions for optimal solutions based on sample average approximations and examine the accompanying rates of convergence. Examples from nonparametric statistics illustrate the results. Keywords Hypo-convergence · Attouch-Wets distance · Approximation theory · Solution stability · Stochastic optimization · Epi-splines · Rate of convergence Mathematics Subject Classification 90C15 Stochastic programming · 62G07 Density estimation · 62G08 Nonparametric regression · 62G15 Tolerance and confidence regions
1 Introduction Extended real-valued upper-semicontinuous (usc) functions on Rn are fundamental in the study of finite-dimensional constrained maximization problems as essentially
B 1
Johannes O. Royset [email protected] Operations Research Department, Naval Postgraduate School, Monterey, USA
123
J. O. Royset
all such problems can be represented by usc functions. They arise in probability theory with distribution and càdlàg functions also being usc. Emerging applications of usc functions in infinite-dimensional problems include nonparametric statistical Mestimation [38], distributionally robust optimization [36], and more generally function identification [35]. In these applications, optimization problems are formulated over spaces of usc functions. Regardless of the setting, it becomes important to have means to approximate usc functions as well as an understanding of the difficulty with such an undertaking. This article provides three main results in these directions: (i) We establish that every usc function is the limit of a hypo-converging sequence of meshfree piecewise affine functions of the difference-of-max type. Thus, as a corollary, the difference-of-convex (dc) functions are hypo-dense in spaces of usc functions. With the advances in computational treatment of dc functions (see for example [8]), this leads to numerous algorithmic possibilities, w
Data Loading...
