Approximations and solution estimates in optimization

作者：Royset Johannes O^*

来源：Mathematical Programming, 2018, 170(2): 479-506.

DOI：10.1007/s10107-017-1165-0

• Epi-convergence
• Attouch-Wets distance
• Epi-splines
• Solution stability
• Approximation theory
• Near-optimality
• Near-feasibility
• Rate of convergence

Approximation is central to many optimization problems and the supporting theory provides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing finite- and infinite-dimensional constrained minimization problems as instances of extended real-valued lower semicontinuous functions defined on a general metric space. Since the Attouch-Wets distance between such functions quantifies epi-convergence, we are able to obtain estimates of optimal solutions and optimal values through bounds of that distance. In particular, we show that near-optimal and near-feasible solutions are effectively Lipschitz continuous with modulus one in this distance. Under additional assumptions on the underlying metric space, we construct approximating functions involving only a finite number of parameters that still are close to an arbitrary extended real-valued lower semicontinuous functions.

• 出版日期2018-8