A Finite Algorithm for Solving Infinite Dimensional Optimization Problems

Abstract

We consider the general optimization problem ( P ) of selecting a continuous function x over a σ-compact Hausdorff space T to a metric space A , from a feasible region X of such functions, so as to minimize a functional c on X . We require that X consist of a closed equicontinuous family of functions lying in the product (over T ) of compact subsets Y t of A . (An important special case is the optimal control problem of finding a continuous time control function x that minimizes its associated discounted cost c ( x ) over the infinite horizon.) Relative to the uniform-on-compacta topology on the function space C ( T , A ) of continuous functions from T to A , the feasible region X is compact. Thus optimal solutions x * to ( P ) exist under the assumption that c is continuous. We wish to approximate such an x * by optimal solutions to a net { P i }, i ∈ I , of approximating problems of the form min x ∈ X i c i ( x ) for each i ∈ I , where (1) the net of sets { X i } I converges to X in the sense of Kuratowski and (2) the net { c i } I of functions converges to c uniformly on X . We show that for large i , any optimal solution x * i to the approximating problem ( P i ) arbitrarily well approximates some optimal solution x * to ( P ). It follows that if ( P ) is well-posed, i.e., lim sup X i * is a singleton { x * }, then any net { x i * } I of ( P i )-optimal solutions converges in C ( T , A ) to x * . For this case, we construct a finite algorithm with the following property: given any prespecified error δ and any compact subset Q of T , our algorithm computes an i in I and an associated x i * in X i * which is within δ of x * on Q . We illustrate the theory and algorithm with a problem in continuous time production control over an infinite horizon.