Optimization: A Theory of Necessary Conditions

by Lucien W. Neustadt

Overview

This book presents a comprehensive treatment of necessary conditions for general optimization problems. The presentation is carried out in the context of a general theory for extremal problems in a topological vector space setting.

Following a brief summary of the required background, generalized Lagrange multiplier rules are derived for optimization problems with equality and generalized "inequality" constraints. The treatment stresses the importance of the choice of the underlying set over which the optimization is to be performed, the delicate balance between differentiability-continuity requirements on the constraint functionals, and the manner in which the underlying set is approximated by a convex set. The generalized multiplier rules are used to derive abstract maximum principles for classes of optimization problems defined in terms of operator equations in a Banach space. It is shown that special cases include the usual maximum principles for general optimal control problems described in terms of diverse systems such as ordinary differential equations, functional differential equations, Volterra integral equations, and difference equations. Careful distinction is made throughout the analysis between "local" and "global" maximum principles.

Originally published in 1977.

The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

Product Details

ISBN-13:	9780691616834
Publisher:	Princeton University Press
Publication date:	03/08/2015
Series:	Princeton Legacy Library , #1374
Pages:	440
Product dimensions:	6.00(w) x 9.10(h) x 1.00(d)

Read an Excerpt

Optimization

A Theory of Necessary Conditions

---

By Lucien W. Neustadt

PRINCETON UNIVERSITY PRESS

Copyright © 1976 Princeton University Press
All rights reserved.
ISBN: 978-0-691-08141-0

---

CHAPTER 1

Mathematical Preliminaries

In this chapter we shall present some mathematical background material which will be necessary in order to understand the remainder of this book. For the most part, we shall confine ourselves to stating definitions and to theorem statements. The proofs of many of the theorems are immediate. References will be given for those proofs which are less obvious but which are widely available in the literature. (In this regard, the reference numbers refer to books listed at the end of this chapter.) Proofs will be given for those lemmas and theorems which either are novel or are not widely known.

The material in this chapter is, of course, sketchy at best, and in many cases definitions and theorems are not presented in their full generality. Indeed, in those cases where full generality does not provide any additional insight and is not required in the remainder of this book, we shall confine ourselves to restrictive definitions and theorems.

Since linear topological spaces form the framework of much of what we have to say, most of this chapter deals with such spaces and with background material necessary to understand these spaces. The last section of this chapter, which contains the major part of the novel material in this chapter, is devoted to a study of a wide variety of differentials.

For the sake of completeness, we have included some quite elementary material, such as the properties of finite-dimensional Euclidean spaces. However, the reader is expected to be familiar with the fundamentals of analysis on the real line. In addition, in subsequent chapters — as well as in Section 6 of this chapter — we shall make use of a number of concepts and theorems from the theory of measure and integration on the real line (and, on a few occasions, on real finite-dimensional spaces). Because this material is so widely and easily accessible in many books, including, e.g., [4] and [7], we shall dispense with presenting any background material on it ourselves.

1. Linear Vector Spaces

A group is a nonempty collection Y of elements together with an operation called addition which assigns to each ordered pair (y1, y2) of elements from Y a new element y3 of Y — which will be written as y1 + y2 = y3 — subject to the following restrictions:

(i) y1 + (y2 + y3) = (y1 + y2) + y3 for all y1, y2, y3 in Y (the associative law);

(ii) there is in Y a unique 0 (which we shall call the identity) such that 0 + y = y + 0 = y for all y [member of] Y;

(iii) for every y [member of] Y there exists a unique element, denoted by (-y), such that y + (-y) = (-y) + y = 0.

If addition in Y obeys the commutative law, i.e., if y1 + y2 = y2 + y1 for all y1, y2 [member of] Y, then the group Y will be said to be Abelian.

1 A linear vector space is an Abelian Y group together with an operation called scalar multiplication which assigns to each pair α, y, where α is a real number and y [member of] Y, a new vector y1 [member of] Y — which will be written as y1 = αy — subject to the following restrictions:

(i) α(y1 + y2) = αy1 + αy2 for all real α and y1, y2 [member of] Y (a distributive law);

(ii) (α + β)y = αy + βy for all real α, β and y [member of] Y (a distributive law);

(iii) α(βy) = (αβ)y for all real α, β and y [member of] Y (an associative law);

(iv) 1y = y for all y [member of] Y.

What we have referred to as a linear vector space is often referred to in the literature as a real linear vector space, because linear vector spaces other than the kind that we have introduced may be defined. Since we shall not deal with these other spaces, we shall dispense with the adjective "real."

2 Although the symbol 0 denotes both the identity in a linear vector space (the word origin is often used in place of identity) and the number zero, there should be no confusion about this in the sequel, since it will always be clear from the context what 0 stands for, even when we discuss two different vector spaces.

We shall adopt the usual convention of writing (y1 – y2) for [y1 + (-y2)].

It is easy to see that, in any linear vector space Y, for all y [member of] Y 0y = 0 and - 1y = -y that α0 = 0 for all real α, and that the following "cancellation" laws hold:

(i) y1 + y2 = y1 + y3 implies that y2 = y3;

(ii) αy1 = αy2 and α ≠ 0 imply that y1 = y2;

(iii) αy = βy and y ≠ 0 imply that α = β.

3 The real numbers, where addition and scalar multiplication are defined in the obvious way, clearly form a linear vector space, which will be denoted by R or by R1. The set of all n-tuples of real numbers, where n is an integer greater than 1, with addition defined by the rule ([xi]1, ..., [xi]n) + (η1, ..., ηn) = ([xi]1 + η1, ..., [xi]n + ηn) and scalar multiplication by α([xi]1, ..., [xi]n) = (α[xi]1, ..., α[xi]n), also make up a linear vector space which will be denoted by Rn. If [xi] = ([xi]1, ..., [xi]n) [member of] Rn, then ([xi]1, ..., [xi]n) will sometimes be called the coordinates or components of [xi].

4 Two linear vector spaces Y' and Y" will be said to be isomorphic if there is a one-to-one correspondence between the elements of Y' and Y", denoted by <->, such that if y'1<->y"1 and y'2 [member of] y"2, then αy'1 + βy'2<-> αy"1 + βy"2 for all real numbers α, β.

5 If Y1 ..., Ym are linear vector spaces, the direct product (or Cartesian product) of Y1, ..., Ym, written as Y1 × Y2 × ... × Ym, is the linear vector space of all m-tuples (y1, ..., ym) where yi [member of] Yi for i = 1, ..., m, with addition defined by the rule (y1, ..., ym) + (y'1, ..., y'm) = (y1 + y'1, ..., ym + y'm) and scalar multiplication by α(y1, ..., ym) = (αy1, ..., αym). The space Y × ... × Y (m times) will simply be denoted by Ym. (It is clear that our notation Rn introduced above is consistent with this convention.) If Ai is a nonempty subset of Yi for each i, then the direct product of A1, Am, written as A1 × A2 × ... × Am, is the set {(y1, ..., ym): yi [member of] Ai for each i} in Y1, × ... × Ym. The set A × ... × A (m times) in Ym will be denoted by Am.

In the remainder of this section, Y, Y1 ..., Ym will denote linear vector spaces.

If A and B are nonempty subsets of Y, y0 [member of] <Y, and α and β are real numbers, then we define the subsets αA, A + B, and y0 + A of Y as follows:

6 αA = {αy: y [member of] A}

7 A + B = {y1 + y2: y1 [member of] A, y2 [member of] B},

8 y0 + A = {y0 + y: y [member of] A}.

The sets A – B, y – A, and A – y are defined in an obviously analogous manner. Note that 1A = A and that 0 + A = A, but that, in general, A + A ≠ 2A. Further, α(A + B) = αA + αB, α(βA) = (αβ)A, (α + β)A = αA + βA, and y0 + (y1 + A) = (y0 + y1) + A for all real α, β, nonempty subsets A and B of Y, and elements y0, y1 [member of] Y.

9 A nonempty subset A of Y will be called a linear manifold if αy1 + βy2 [member of] A whenever y1, y2 [member of] A and α and β are any real numbers. Note that A [subset] Y is a linear manifold in Y if and only if A is itself a linear vector space (or a linear subspace of Y).

10 Any set of the form y0 + A, where y0 [member of] Y and A is a linear manifold in Y, will be called a flat (or a linear variety) in Y.

11 A nonempty set A [subset] Y will be said to be convex if λy1 + μy2 [member of] A whenever y1, y2 [member of] A, λ ≥ 0, μ ≥ and λ + μ = 1. It is easy to see that A is convex if and only if [summation]mi = 1 λiyi [member of] A]IT whenever y1, ..., ym [member of] A, [summation]λi = 1, and λi ≥ 0 for each i, where m is an arbitrary positive integer.

12 A nonempty set A [subset] Y will be said to be a cone if αA [subset] A for all α > 0.

13 A set A [subset] Y which is both convex and a cone will be said to be a convex cone. It is easy to see that A is a convex cone if and only if αA + βA [subset] A for all α > 0 and β > 0.

14 A cone (or convex cone) A in Y will be said to be pointed if 0 [member of] A.

15 Note that every linear manifold is a pointed convex cone as well as a flat, and that every flat is convex. In particular, the set {0} (consisting only of the origin in Y) is a linear manifold and pointed convex cone. It is also easily verified that the intersection of any number of linear manifolds (respectively, flats, convex sets, cones, convex cones, or pointed cones) is either empty or a linear manifold (respectively, a flat, a convex set, a cone, a convex cone, or a pointed cone).

16 Similarly, if Ai is a linear manifold (respectively, flat, convex set, cone, convex cone, pointed cone) in Yi for i = 1, ..., m, then A1 × ... × Am is a linear manifold (respectively, flat, convex set, cone, convex cone, pointed cone) in Y1 × ... × Ym.

17 Further, if A and B are linear manifolds (respectively, flats, convex sets, cones, convex cones, pointed cones) in then αA + βB is also a linear manifold (respectively, flat, convex set, cone, convex cone, pointed cone) in Y for all real α, β. Finally, if A is a convex set (respectively, a flat) in Y and y0 [member of] Y then y0 + A is also a convex set (respectively, a flat) Y.

18 The set of all negative numbers, which we shall denote by R- is clearly a convex cone in R, as is the set of all positive numbers, which we shall denote by R+. The set of all nonpositive numbers, which we shall denote by [bar.R]-, and the set of all nonnegative numbers, which we shall denote by [bar.R]+, are evidently pointed convex cones in R.

Let us denote by Rn- and [bar.R]n- the following sets in Rn:

19 Rn- = {([xi]1, ..., [xi]n): [xi]i< 0 for each i = 1, ..., n},

20 [bar.R]n- = {([xi]1, ..., [xi]n): [xi]i ≤ 0 for each i = 1, ..., n}.

21 Then it is easily seen that Rn-, which we shall call the negative orthant in Rn, and [bar.R]n-, which we shall call the nonpositive orthant in Rn, are convex cones, with the latter pointed. The positive orthant Rn+ and the nonnegative orthant [bar.R]n+ are similarly defined (and are also convex cones).

22 A finite collection {y1, ..., ym} of vectors in Y will be said to be linearly dependent if there are real numbers α1, ..., αm, not all zero, such that α1y1 + ... + αmym = 0. A finite subset of Y will be said to be linearly independent if it is not linearly dependent. Vectors y1, ..., ym in Y will be said to be in general position if the relations [summation]mi = 1 αiyi = 0 and [summation]mi = 1 αi = 0 imply that αi = 0 for all i = 1, ... m. It is easily seen that y1, ..., ym are in general position if and only if the vectors (y2 – y1), ..., (ym – y1) are linearly independent.

(Continues...)

---

Excerpted from Optimization by Lucien W. Neustadt. Copyright © 1976 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---

Table of Contents

• Frontmatter, pg. i
• CONTENTS, pg. vii
• PREFACE, pg. ix
• SUMMARY OF NOTATION, pg. xiii
• CHAPTER I. Mathematical Preliminaries, pg. 1
• CHAPTER II. A Basic Optimization Problem in Simplified Form, pg. 63
• CHAPTER III. A General Multiplier Rule, pg. 96
• CHAPTER IV. Optimization with Operator Equation Restrictions, pg. 144
• CHAPTER V. Optimal Control Problems with Ordinary Differential Equation Constraints, pg. 212
• CHAPTER VI. Optimal Control Problems with Parameters and Related Problems, pg. 263
• CHAPTER VII. Miscellaneous Optimal Control Problems, pg. 315
• APPENDIX. Volterra-Type Operators, pg. 361
• NOTES AND HISTORICAL COMMENTS, pg. 384
• REFERENCES, pg. 413
• SUBJECT INDEX, pg. 422