A First Course in Optimization Theory

We begin our study of optimization with the fundamental question of existence: under what conditions on the objective function f and the constraint set D are we guaranteed that solutions will always exist in optimization problems of the form max {f(x) | x ∈ D) or min {f(x) | x ∈ D}? Equivalently, under what conditions on f and D is it the case that the set of attainable values f(D) contains its supremum and/or infimum?

Trivial answers to the existence question are, of course, always available: for instance, f is guaranteed to attain a maximum and a minimum on D if D is a finite set. On the other hand, our primary purpose in studying the existence issue is from the standpoint of applications: we would like to avoid, to the maximum extent possible, the need to verify existence on a case-by-case basis. In particular, when dealing with parametric families of optimization problems, we would like to be in a position to describe restrictions on parameter values under which solutions always exist. All of this is possible only if the identified set of conditions possesses a considerable degree of generality.

The centerpiece of this chapter, the Weierstrass Theorem, describes just such a set of conditions. The statement of the theorem, and a discussion of its conditions, is the subject of Section 3.1. The use of the Weierstrass Theorem in applications is examined in Section 3.2. The chapter concludes with the proof of the Weierstrass Theorem in Section 3.3.