Approximations and Solution Estimates in Optimization

Abstract

Approximation is central to many optimization problems and the supporting theory pro- vides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing nite- and in nite-dimensional constrained minimization prob- lems as instances of extended real-valued lower semicontinuous functions de ned on a general metric space. Since the Attouch-Wets distance between such functions quanti es epi-convergence, we are able to obtain estimates of optimal solutions and optimal values through estimates of that distance. In par- ticular, we show that near-optimal and near-feasible solutions are effectively Lipschitz continuous with modulus one in this distance. We construct a general class of approximations of extended real-valued lower semicontinuous functions that can be made arbitrarily accurate and that involve only a nite number of parameters under additional assumptions on the underlying metric space.