NON LINEAR PROGRAMMING
G.N KAMAU
chp_notes.pdf
Chapter 4
Optimization Manifesto: Our Mission and Our Unified Approach
Distribution of this material is restricted.
It is for the use of students currently
enrolled in CAAM 560.
In this chapter we carefully construct a set of fundamental principles that will guide our entire optimization theory development. Our approach has been motivated by the belief, acquired and nurtured over years of teaching optimization theory, that the various optimization theorems and tools are not just an ad hoc collection of mathematical statements, but instead they follow systematically and directly from a basic set of fundamental principles. Our motivation for taking this approach is the desire to bring cohesiveness to the development and the presentation of optimization theory. This in turn will facilitate and promote appreciation, understanding, and retention.
Now, of course, in standard mathematical text book style, we could present only the final destination of our Chapter 4 journey, the fundamental principles, leaving the student to wonder where they come from. However, we have chosen not to do this, motivated by our conviction that the student em- barking on research will benefit from experiencing the lengthy journey, with its detours and uncertainties, to the fundamental principle destinations.
Our unified approach begins with the careful identification of a basic constrained optimization problem called our prototypical problem. Next we
55
56 [Draft – distribution restricted to CAAM 560 students]
conjecture and prove results about this problem related to notions we intro- duce and refer to as necessity, su�ciency, and existence conditions. These results we call prototypical results. Then the development becomes inter- esting and challenging in that we turn to an ill-defined, but not uncommon, mathematical activity. It is standard for the mathematician to make a state- ment and then establish its validity with a mathematical proof. Then certain creativity sets in. Questions are asked: Did I prove more than I stated? Does this proof lead me to conjecture and prove a more general result? This tech- nique is used to obtain fundamental principles for necessity, su�ciency, and existence for more general problems from extensive reflection on the state- ments and proofs of these prototypical results. In turn, in the remainder of the text, we apply these fundamental principles to particular classes of prob- lems in order to obtain the appropriate theory for these classes of problems. Hence by our unified approach we mean the construction of theory for vari- ous constrained optimization problem classes from a handful of fundamental principles, and the derivation of these principles.
We strongly recommend that the reader not familiar with the material on di↵erentiation contained in Appendix E, visit that appendix before attempt- ing to digest the material in the current chapter.
4.1 Categories of Optimization Theory Ac- tivity
Consider the standard optimization problem described in (1.2), i.e.,
min x2S
f(x) (4.1)
where S is a subset of a vector space X and f : S ! IR. By a solution of problem (4.1) we mean either a global solution or a local solution when the environment supports this latter notion.
A comprehensive look at the vast body of optimization theory literature leads us to consider the following five basic categories of optimization theory activity.
• First-Order Necessity If x⇤ is a solution of problem (4.1), then what can we say about f 0(x⇤)?
[Draft – distribution restricted to CAAM 560 students] 57
• Second-Order Necessity If x⇤ is a solution of problem (4.1), then what can we say about f 00(x⇤)?
• First-Order Su�ciency What conditions on f 0(x⇤) imply that x⇤
solves problem (4.1)?
• Second-Order Su�ciency What conditions on f 00(x⇤) imply that x⇤
solves problem (4.1)?
• Existence
What conditions on f and S guarantee that problem (4.1)
has at least one solution?
The details of the environment required in each application is a part of the question that is to be answered.
The descriptors existence and su�ciency play similar roles. Tradition- ally su�ciency is used when we are considering conditions at a point that guarantee that the given point is a minimizer of the function under consid- eration, while existence is used when we are considering conditions related to a function and a set which guarantee that the given set contains at least one minimizer of the given function.
4.2 Some Comments on Necessity and Su�- ciency
We elaborate on some basics concerning necessity and su�ciency conditions. Suppose that we have a necessity condition of the generic form:
If x⇤ is a solution of the optimization problem under considera- tion, then Property P holds on set A.
It is clear that we arrive at a new necessity condition by replacing the set A with a subset of A. We expect this new necessity condition to be weaker, in the sense that it is easier to satisfy and therefore enlarges the class of potential minimizers. Hence as a general rule, we would like to make the set A as large as possible.
Consider a su�ciency statement of the form:
58 [Draft – distribution restricted to CAAM 560 students]
If Property P holds on set B, then x⇤ is a solution of the opti- mization problem under consideration.
By asking Property P to hold on a superset of B, a set containing B, we have a new su�ciency condition. This new condition is weaker in the sense that it will be harder to satisfy; indeed, there may not be points that satisfy the condition — even though our problem has solutions.
As a general rule, we want the set A in necessity conditions to be as large as possible, and we want the set B in su�ciency conditions to be as small as possible.
If a given necessity condition of the type described above can be demon- strated to also be a su�ciency condition, or a su�ciency condition when attention is restricted to a meaningful subclass of problems, then we can say with confidence that our choice of the set A where Property P must hold is an e↵ective choice and is not restrictively small. This is exactly the case for the variational inequality necessity condition derived in Chapter 7.
While we stress the danger of falling into the trap of using necessity as su�ciency we add the following useful observations. If it is known, by any means, that the optimization problem at hand has a solution and the neces- sary conditions have a unique solution, then it follows that the solution to the necessary conditions is the unique solution to the optimization problem. Moreover, whenever it can be ascertained that necessary conditions have at most one solution, then it follows that the optimization problem has at most one solution.
4.3 Our UnifiedApproach
The mission of this text now becomes to build theory (mathematical tools) representing each of the five areas of optimization theory activity described in §4.1 for various broad classes of optimization problems.
Our unified approach consists of the following sequence of steps. For each of the five optimization theory categories
1. Construct a prototypical problem.
2. Propose a prototypical result for this problem.
3. Provide a proof of the prototypical result.
[Draft – distribution restricted to CAAM 560 students] 59
4. Abstract from the prototypical result, and its proof as needed, a fun- damental principle, or principles.
5. Obtain application theorems as specific instances of the fundamental principles applied to a particular problem class.
6. Evaluate the application theorems. If they are not useful, then return to step 3 and try a di↵erent proof. If this leads nowhere, then return to step 2 and try a di↵erent prototypical result. If this also leads nowhere then return to step 1 and try a di↵erent prototypical problem.
A flow chart representation of our six step process for constructing appli- cation theory is given in Figure 4.1. This flow chart presentation highlights the various branch points in the process.
Figure 4.1: Our six-step approach to application theory.
60 [Draft – distribution restricted to CAAM 560 students]
Granted, step 6 is rather loosely defined , but it is an important ingredient in our unified approach. Moreover, in the interest of concise presentation we give only a representative demonstration of its use in the constructions that follow, and mention that some of its uses were behind the scenes. Indeed, we are presenting those that worked, the others are respectfully and appre- ciatively forgotten. However, in the following section where we develop our existence theory we illustrate step 6 by first presenting an approach which is quite direct, but does not lead to satisfactory theory.
The fundamental principles that we will abstract from the proofs of pro- totypical results are quite general and of great importance. However, they are a means towards an end and may not be immediately applicable to prob- lems that arise in practice. Hence, the application theorems that we derive from these principles will be our main challenge. Because the principles are so general, the derivation of specific application theorems will often be quite involved. The remaining sections of this chapter develop our fundamental principles. Application theorems will be derived throughout the remainder of the text.
4.4 Fundamental Principle for Existence
We begin with the construction of existence theory, because for this case our unified approach is relatively clean and straightforward. As such it well illustrates our approach and prepares the reader for the more challenging tasks that lie ahead.
There are few existence results from which to abstract a prototypical problem and prototypical result. The following is standard.
Proposition 4.4.1 (Prototypical Result for Existence). Let S be a closed and bounded subset of Euclidean space, IRn, and assume that f : S ! IR is continuous on S. Then f has at least one global minimizer in S.
For the purposes of illustrating our approach, we first give a proof of our prototypical result that does not lead to an e↵ective fundamental principle for existence.
Proof. 1 It is well-known that in Euclidean space, IRn, the continuous image of a
closed and bounded set is a closed and bounded set. Hence f(S) = {f(x) :
[Draft – distribution restricted to CAAM 560 students] 61
x 2 S} is closed and bounded, and therefore inf f(S) is a finite limit point of S. Since closed sets contain their limit points, there exists x⇤ 2 S such that f(x⇤) = inf
x2S f(S), i.e., x⇤ is a global minimizer. ⌅
Observe that the key ingredient in Proof 1 is the fact that f(S) is closed and bounded. It is known that in an infinite-dimensional normed linear space, the continuous image of a closed and bounded set is not necessarily closed and bounded. However, it is also known that the continuous image of a compact set (see Definition C.3.20) is closed and bounded (indeed compact). In IRn closed and bounded and compact are equivalent. This leads us to the fundamental principle that a continuous function has at least one minimizer in every compact subset of a normed linear space. The di�culty with this principle is that compact sets are quite rare in infinite-dimensional normed linear spaces. For example, in a normed linear space of infinite dimension, no set with an interior point can be compact because the closed unit ball is never compact. Thus this first proof of our prototypical result does not lead to a useful fundamental principle.
One hint that we might not obtain a useful fundamental principle with this approach is that we also carry over the existence of a maximizer. It seems intuitive to us that in order to get an e↵ective result for minimizers, we will have to give up maximizers. Hence we attempt a second proof.
Proof. 2 Let f⇤ = inf
s2S f(s). It does not matter if f⇤ = �1. By the properties
of infimum we can construct a sequence {xk} ⇢ S such that f(xk) ! f ⇤.
Because S is compact, see Proposition C.4.2, we can extract a convergent subsequence of {xk}, which we also call {xk}. Define x
⇤ 2 S by xk ! x
⇤. By the continuity of f and the definition of f⇤ we have
f(x⇤) = lim k
f(xk) = f ⇤ f(x). (4.2)
Hence, x⇤ is a global minimizer of f in S. ⌅ We must now look closely at this proof and determine exactly what we
used from the notions of continuity and compactness; and see if less restrictive notions will carry the proof. In our proof from compactness we used the fact that every sequence in S contains a subsequence which converges to a point in S. This notion is known and is often referred to as sequential compactness. In IRn, indeed in a normed linear space, sequential compactness is known to
62 [Draft – distribution restricted to CAAM 560 students]
be equivalent to our definition of compactness (every open cover contains a finite subcover). See Proposition C.4.2 of Appendix C. However, in the generality of topological linear spaces, see Appendix D, it is known that sequential compactness is a more general notion than is our defined notion of compactness. Hence sequential compactness will be our replacement for compactness in the general principle for existence that we are seeking.
We now turn to a similar discussion concerning the use of continuity in the proof of the prototypical result for existence. There we used continuity of f on S to conclude that for {xk} ⇢ S,
xk ! x ⇤
) f(xk) ! f(x ⇤). (4.3)
This is one of the three equivalent notions of continuity described in Proposition C.4.3 of Appendix C. Statement (4.3) means given " > 0 9 K >
0 such that 8 k � K
|f(xk) � f(x ⇤)| < ". (4.4)
We can write (4.4) as
�" < f(xk) � f(x ⇤) < ", (4.5)
or
�" + f(x⇤) < f(xk) < " + f(x ⇤), (4.6)
or
(i) � " + f(x⇤) < f(xk) and (ii) f(xk) < " + f(x ⇤). (4.7)
Now, since the choice of " > 0 can be arbitrary (4.7) leads to
(i) f(x⇤) lim k
inf f(xk) and (ii) lim k
sup f(xk) f(x ⇤). (4.8)
In the literature the notion (i) of (4.8) is called lower semicontinuity of f at x⇤ and (ii) of (4.8) is called upper semicontinuity of f at x⇤. Since we always have that the infimum of a set of real numbers is less than or equal to the supremum of this set we can write (4.8) as
f(x⇤) lim k
inf f(xk) lim k
sup f(xk) f(x ⇤). (4.9)
[Draft – distribution restricted to CAAM 560 students] 63
It follows that f is continuous at x⇤ if and only if f is both upper and lower semicontinuous at x⇤. Our search has led us to two less restrictive notions which are closely related to continuity. Our anticipated excitement materializes when we observe that it is exactly lower semicontinuity that is needed for our proof of the prototypical result. To add to this we observe that it is exactly upper semicontinuity that is needed for the proof if the prototypical result were stated in terms of maximizers instead of minimizers. This is quite satisfying, so we now collect our discoveries and state them in a formal manner which will include a useful general principle for existence.
Consider a real vector space X endowed with a notion of convergence. While the notion of convergence will invariably be convergence in a topolog- ical linear space, certain ease will be facilitated if we focus directly on the notion of convergence.
Definition 4.4.2. Consider a vector space X endowed with a notion of convergence. Let S be a subset of X.
(i) We say that S is sequentially compact (with respect to the given notion of convergence) if every sequence in S has a subsequence converging to a point in S.
(ii) Consider f : S ⇢ X ! IR and x 2 S. We say that f is lower, respec- tively upper, semicontinuous at x (with respect to the given notion of convergence) if {xk} ⇢ S and xk ! x implies that
f(x) lim k
inf f(xk),
respectively
lim k
sup f(xk) f(x).
We say that f is lower, respectively upper, semicontinuous in S when it is lower, respectively upper, semicontinuous at each point in S.
We are now ready to state our fundamental principle for existence.
Theorem 4.4.3 (Fundamental Principle for Existence). Consider a vector space X endowed with a notion of convergence. Let S be a sequentially compact subset of X, and let f : S ! IR be lower semicontinuous in S. Then f has at least one global minimizer in S.
64 [Draft – distribution restricted to CAAM 560 students]
Proof. In accordance with our stated objective the proof of this general principle is the same as the proof of our prototypical result; we merely replace compactness with sequential compactness and replace (4.2) with
f(x⇤) lim k
inf f(xk) = f ⇤ f(x). (4.10)
⌅
We now illustrate our new found understanding with an example.
Example 4.4.4. Consider f : [�1, 1] ! IR defined by
f(x) =
8
>
<
>
:
�x for x 2 [�1, 0)
d for x = 0
2 � x for x 2 (0, 1]
(4.11)
The graph of f is pictured in Figure 4.2
-1 1 1 2 d
Figure 4.2: Lower and upper semicontinuity
Clearly the domain of f is the closed and bounded interval [�1, 1]. We next observe that there is no choice of d that makes f continuous. So we can not conclude that f has a minimizer (or a maximizer) from Proposition 4.4.1, our prototypical result for existence, for any choice of d. The choice d 0 is the only choice of d that leads to lower semicontinuity, and it is the only
[Draft – distribution restricted to CAAM 560 students] 65
choice of d which allows for a minimizer. Furthermore, the choice d � 2 is the only choice of d that leads to upper semicontinuity, and it is the only choice of d which allows for a maximizer. Hence, we can not have both a minimizer and a maximizer. For this example our fundamental principle is sharp in that lower semicontinuity is not only su�cient, but it is also necessary for the existence of a minimizer.
The notion of convergence that we choose in our fundamental principle will dictate a balance between lower semicontinuity and sequential compact- ness. For example, in a normed linear space, norm convergence will give a rich class of lower semicontinuous (indeed continuous) functions, but a poor class of sequentially compact sets. This notion of convergence is too strong. An appropriate notion of convergence must achieve a balance between lower semicontinuous functions and sequentially compact sets. This balance will be established in Chapter 9, where we give an important application of our fundamental principle for existence.
4.5 Choice of Prototypical Problem for Ne- cessity and Su�ciency Theory
The obvious choice for a prototypical problem is
minimize f(x). x 2 IR
(4.12)
The following three standard results addressing problem (4.12) are staples of elementary calculus:
• First-order necessity.
If x⇤ minimizes f, then f 0(x⇤) = 0.
• Second-order necessity.
If x⇤ minimizes f, then f 00(x⇤) � 0.
• Second-order su�ciency.
If x⇤ is such that f 0(x⇤) = 0 and f 00(x⇤) > 0, then x⇤ is a strict local minimizer of f.
66 [Draft – distribution restricted to CAAM 560 students]
For many reasons problem (4.12) is deficient in guiding us towards useful fundamental principles for problem (4.1). Indeed it suggests nothing in the way of first-order su�ciency.
A moments reflection leads us to the understanding that problem (4.1) in general represents constrained problems and problem (4.12) is unconstrained. Hence a successful prototypical problem must be constrained and have its so- lution on the boundary of the constraint set. We therefore o↵er the following candidate.
Prototypical Problem Given ⌧ > 0 and f : [0, ⌧) ! IR consider the optimization problem
minimize f(x) (4.13)
subject to x 2 [0, ⌧)
with solution x⇤ = 0. Some thought leads us to propose the following prototypical results for
problem (4.13).
• First-Order Necessity
f 0+(0) � 0.
Figures 4.3, 4.4, and 4.5 depict examples of this situation.
• Second-Order Necessity
If f 0+(0) = 0, then f 00 +(0) � 0. (4.14)
This situation is depicted in Figure 4.3 and Figure 4.5. Figure 4.4 shows that in second-order necessity the condition that f 0+(0) = 0 can not be removed.
• First-Order Su�ciency (for a strict local minimizer)
f 0+(0) > 0.
This situation is depicted in Figure 4.4.
[Draft – distribution restricted to CAAM 560 students] 67
0 t Figure 4.3: First and second-order necessity.
0 t Figure 4.4: First-order su�ciency.
0 t Figure 4.5: Second-order su�ciency.
• Second-Order Su�ciency (for a strict local minimizer)
f 0+(0) = 0 and f 00 +(0) > 0. (4.15)
This situation is depicted in Figure 4.5.
Simple examples can be constructed to show that our prototypical necessity conditions are not su�ciency conditions and our su�ciency conditions are not necessity conditions.
68 [Draft – distribution restricted to CAAM 560 students]
4.6 Explorations in Search of Fundamental Principles for First-Order Necessity
In this section we introduce needed preliminary notions concerning feasible arcs and tangent cones and illustrate how we can use prototypical results to derive fundamental principles for first-order necessity. In the following sec- tion we will do the same for fundamental principles for first-order su�ciency and in §4.12 and §4.13, we extend our exploratory analysis to fundamental principles for both second-order necessity and second-order su�ciency. These sections are intended to be motivational in nature and promote understand- ing and appreciation for the derivation of fundamental principles, their roles and their assumptions. With these objectives in mind, we have chosen a style of presentation that is rather wordy and informal when compared with the standard terse mathematical style of presentation. However, we maintain complete mathematical rigor.
A proof of our prototypical result for first-order necessity follows.
Proposition 4.6.1. If 0 minimizes f : [0, ⌧) ! IR, then necessarily f 0+(0) � 0 whenever this forward variation exists.
Proof. We have
f(t) � f(0) � 0 for t small and positive. (4.16)
Hence
f 0+(0) = lim t#0
f(t) � f(0)
t � 0. (4.17)
⌅
Taking our lead from this prototypical result and its proof we put forth that a guiding theme in optimization is
If x⇤ minimizes f in S, then the forward directional variation of f at x⇤ must be nonnegative in tangential directions.
[Draft – distribution restricted to CAAM 560 students] 69
In an intuitive sense, tangential directions of S at x⇤ are directions that are tangents of feasible curves emanating from x⇤. Hence, if the forward directional variation is negative, then f would decrease initially along our feasible curve and x⇤ could not be a minimizer of f in S. Our task now is to give formal definition to our intuitive notion of tangential directions and to our theme as a fundamental principle for first-order necessity.
The key component in our development is adapting the prototypical result and its proof to a more general setting. When we do this we work in what we call exploratory mode. For example, we may use each step of the proof of the prototypical result to guide us as to what assumptions or additional structures are needed for the step to remain valid in the more general setting.
Our prototypical results suggest the following:
Rule of Thumb.
In a given application we should strive to develop necessity the- ory for a local minimizer and su�ciency theory for a strict local minimizer that are only an equal sign apart.
We will keep this rule of thumb in the foreground of all of our developments. The notion of cone will enter into our discussions; hence we begin with
its definition.
Definition 4.6.2. Consider a subset C of the vector space X.
(i) The set C is said to be a cone in X if
↵x 2 C 8 ↵ � 0 and 8 x 2 C.
(ii) The set
cone(B) = {↵b 2 X : ↵ � 0 and b 2 B}
is called the cone spanned by B or the conical hull of B.
See Figure 4.6.
Example 4.6.3. Consider IRn. Then
• Any subspace is a cone.
70 [Draft – distribution restricted to CAAM 560 students]
Figure 4.6: Cone spanned by B.
• The positive (nonnegative) orthant is a cone.
• The unit ball (closed or open) is not a cone and the cone that it spans is all of IRn.
• The cone spanned by any set containing the origin as an interior point is all of IRn.
Definition 4.6.4. Consider a subset S of the vector space X and an x 2 S.
(i) The vector z 2 X is said to be a feasible direction for S at x if there exists ⌧ > 0 so that
A(t) = x + tz 2 S for t 2 [0, ⌧).
Moreover, in this case, the arc A(t) is called a feasible linear arc ema- nating from x with tangent z.
[Draft – distribution restricted to CAAM 560 students] 71
Figure 4.7: Points in a feasibility region.
(ii) We employ the notation Tl(S, x) for the cone of tangents of feasible linear arcs emanating from x. Finally, members of Tl(S, x) are called linear tangents of S at x.
Since the cone of tangents of feasible linear arcs emanating from x is exactly the cone of feasible directions for S at x, the terminology used merely reflects the point of view taken in the application under consideration.
Example 4.6.5. Consider IR2. Let S be the nonnegative orthant, i.e.,
S = {(x1, x2) : x1 � 0, x2 � 0}.
Points in S come in four di↵erent flavors: p1 = (0, 0) T , p2 = (↵, 0)
T , p3 = (0, ↵)
T and p4 = (↵, ↵) T , for ↵ > 0. See Figure 4.6.
Then, it follows directly that
• Tl(S, p1) = S,
• Tl(S, p2) = {(x1, x2) : x2 � 0},
• Tl(S, p3) = {(x1, x2) : x1 � 0},
• Tl(S, p4) = IR 2.
72 [Draft – distribution restricted to CAAM 560 students]
In the interest of deriving a fundamental principle for first-order necessity we ask: If in problem (4.1) x⇤ minimizes f over S, then does it necessarily follow that
f 0+(x ⇤)(z) � 0 8 z 2 Tl(S, x
⇤). (4.18)
We attempt a proof along the lines of the proof of Proposition 4.6.1. Consider z 2 Tl(S, x
⇤) and its qualifying ⌧ > 0. Define � : [0, ⌧) ! IR by
�(t) = f(x⇤ + tz) (4.19)
Now, since t = 0 minimizes � on [0, ⌧) we have from our prototypical result Proposition 4.6.1, that
�0+(0) � 0. (4.20)
Moreover, �0+(0) = f 0 +(x
⇤)(z); hence (4.18) holds and we have derived the following proposition.
Proposition 4.6.6. If in problem (4.1) x⇤ minimizes f over S, then neces- sarily
f 0+(x ⇤)(z) � 0 8 z 2 Tl(S, x
⇤),
provided that f has a forward directional variation at x⇤.
So Tl(S, x ⇤) serves as a candidate for our notion of tangential directions
for S at x and (4.18) serves as a candidate for our fundamental principle of first-order necessity. However, it is important to point out that while the use of Tl(S, x
⇤) in (4.18) has a major strength, it also has a major weakness. The weakness is that it is too limited in many applications. Its great strength is that it can be utilized in the full generality of vector spaces.
In order to address the deficiency of (4.18) as a fundamental principle for first-order necessity we consider more flexibility, at the price of less generality, by turning to feasible nonlinear arcs. Towards this end, we begin, as before, with pertinent definitions.
Definition 4.6.7. Consider a subset S of the vector space X and an x 2 S.
(i) By a feasible curvilinear arc emanating from x we mean an arc A : [0, ⌧) ! X for some ⌧ > 0 with the properties that
(a) A(0) = x
[Draft – distribution restricted to CAAM 560 students] 73
(b) A(t) 2 S for t 2 [0, ⌧).
In addition let X be a topological linear space. Consider a continuous feasible curvilinear arc A emanating from x 2 S.
(ii) Whenever A0+(0) exists we call it the tangent of A at 0 and say that A is smooth. The collection of tangents of smooth continuous feasible curvilinear arcs emanating from x is called the curvilinear tangent cone for S at x and is denoted by Tc(S, x). Members of Tc(S, x) are called curvilinear tangents of S at x.
It is immediate that
Tl(S, x) ⇢ Tc(S, x). (4.21)
A look at Figure 4.8 should convince the reader that in general we have strict set containment in (4.21). Specifically, let S be the closed unit disk and consider as our smooth feasible curvilinear are emanating from the point (0, 1)T the part of the boundary of our unit circle that is in the first quadrant, i.e., A(t) = (t,
p
1 � t2)T for t 2 [0, 1). Then the vector A0+(0) = (1, 0) T is
contained in Tc(S, (0, 1) T ), but it is not contained in Tl(S, (0, 1)
T ).
Figure 4.8: A curvilinear tangent that is not a linear tangent.
We now justify the use of the terminology cone in the naming of Tl(S, x) and Tc(S, x).
74 [Draft – distribution restricted to CAAM 560 students]
Proposition 4.6.8. The entities Tl(s, x) and Tc(S, x) as given in Definition 4.6.2 and 4.6.7 are indeed cones.
Proof. We prove the result for Tc(S, x). The proof for Tl(S, x) follows from the same idea, but is actually more direct and is left as a chapter exercise.
Consider z 2 Tc(S, x) and ↵ > 0. Then z = A 0 +(0) for some A : [0, ⌧] ! S
and some ⌧ > 0. Let A↵(t) = A(↵t) for t 2 [0, ⌧ ↵ ). Observe that A↵(0) =
A(0) = x. Moreover, because of the positive homogeneity of the forward directional variation (A↵)
0 +(0) = ↵A
0 +(0) = ↵z. Hence ↵z 2 Tc(S, x). ⌅
An overarching fundamental principle for first-order necessity is clearly the following essential restatement of our prototypical result.
Consider problem (4.1), a point x⇤ 2 S, and an arc A : [0, ⌧) ! S emanating from x⇤. If x⇤ is a minimizer of f in S and � : [0, ⌧) ! IR is defined by
�(t) = f(A(t)), (4.22)
then necessarily
�0+(0) � 0 (4.23)
whenever this forward directional variation exists. Utilization of this overarching principle challenges us to introduce more
structure in problem (4.1) so that (4.23) will reduce to more useful forms in terms of so-called cones of tangential directions. Observe that (4.18) is an example of such activity.
Analogous to the situation surrounding (4.18) it is appropriate to ask: if in problem (4.1) x⇤ minimizes f over S, and X is a topological linear space, then does it necessarily follow that
f 0+(x ⇤)(z) � 0 8 z 2 Tc(S, x
⇤)? (4.24)
We attempt a proof along the lines of the proof of our prototypical result, Proposition 4.6.1. As before, consider z 2 Tc(S, x
⇤) and its qualifying smooth arc A with domain [0, ⌧). Define � : [0, ⌧) ! IR by
�(t) = f(A(t)).
It follows that 0 minimizes �; hence, from our prototypical result
�0+(0) � 0.
[Draft – distribution restricted to CAAM 560 students] 75
Our demonstration is complete once we show that
�0+(0) = f 0 +(x
⇤)A0+(0). (4.25)
The chain rule, Proposition E.6.1 of Appendix E, gives exactly (4.25) but requires f to be Fréchet di↵erentiable at x⇤. This in turn requires normed linear space structure on X. However, it is satisfying that no additional di↵erential structure need be imposed on the arc A beyond that it is smooth. This investigation has led us to the following.
Proposition 4.6.9. Consider problem (4.1) where X is a normed linear space and f is Fréchet di↵erentiable at x⇤ 2 S. If x⇤ locally minimizes f in S, then necessarily
f 0+(x ⇤)(z) � 0 8 z 2 Tc(S, x
⇤).
It follows that Tc(S, x) also serves as a candidate for our notion of tangen- tial directions for S at x and (4.25) serves as a candidate for our fundamental principle for first-order necessity. In a normed linear space condition (4.25) is stronger than condition (4.20) due to (4.21), Figure 4.8, and the comments made in §4.2 concerning necessity conditions.
At this juncture it would be premature to state our fundamental principles for first-order necessity since our investigation of first-order su�ciency will influence their final statement. Hence, we first explore the more challenging notion of fundamental principles for first-order su�ciency.
4.7 Explorations in Search of Fundamental Principles for First-Order Su�ciency
In deriving fundamental principles for necessity we have the following sit- uation working for us. If x⇤ is a minimizer of f in S, then we have that is a minimizer in a neighborhood of x⇤. So we have our desired behavior locally, i.e. it is a minimizer along lines and other curves emanating from x⇤. However, in deriving fundamental principles for su�ciency we are asking for optimal behavior at x⇤ along lines and curves emanating from x⇤ to translate into optimal behavior in a neighborhood of x⇤. This direction seems to be excessively demanding. As an illustration of this point consider f : IR2 ! IR
76 [Draft – distribution restricted to CAAM 560 students]
defined as follows:
f(x) =
(
(y � x2)(y � 3x2) for x2 < y < 3x2
0 otherwise
Now, along any line passing through the origin the origin is a local minimizer. To see this consider such a line, say y = ax, and observe that for small x, we will not have x2 < ax < 3x2. Hence, near the origin g will be zero along this line; and the origin is a local minimizer along the lines. However, along the curve y = 2x2, f(x, y) = �x4, and the origin is actually a strict local maximizer. To make the origin a strict local minimizer along lines and work with a function which is continuously di↵erentiable, we could replace f with
f̂(x, y) = x10 + y10 � f(x, y)2.
This example2 shows us that in general the property of being a strict local minimizer along linear arcs is not su�cient for being a local minimizer.
In turn, we ask if Tc(S, x) discussed in §4.6, is rich enough to support su�ciency as might be conjectured by our prototypical result for first-order su�ciency presented in §4.6. Specifically, we pursue the question does
f 0+(x ⇤)(z) > 0 8 z 2 Tc(S, x
⇤) (4.26)
lead to the conclusion that x⇤ is a solution of problem (4.1)? In line with our unified approach we first turn to the construction of a detailed proof for our prototypical result for first-order su�ciency given in §4.5. There will be value in labeling the steps of the proof.
Proposition 4.7.1. Consider f : [0, ⌧) ! IR. Assume that f 0+(0) exists. If f 0+(0) > 0, then 0 is a strict local minimizer of f in [0, ⌧).
Proof. [(i)] Suppose that t = 0 is not a strict local minimizer of f in [0, ⌧).
[(ii)] Then there exists a sequence xk 2 (0, ⌧) converging to 0 and such that
f(xk) f(0).
2This example is due to Richard Byrd.
[Draft – distribution restricted to CAAM 560 students] 77
[(iii)] Since xk is positive we can write
f(xk) � f(0)
xk 0 8 k. (4.27)
[(iv)] Hence
f 0+(0) = lim k
f(xk) � f(0)
xk 0. (4.28)
This is the contrapositive statement of the desired result and gives us the proposition.
⌅ We now attempt to adapt the proof of Proposition 4.7.1 to the more
general situation described by (4.26). We work in exploratory mode, i.e., we want the attempted proof to guide us towards assumptions and struc- tures that are needed for a successful fundamental principle for first-order su�ciency.
Towards this end consider problem (4.1) where X is a topological linear space and assume (4.26). We carefully consider analogs of steps (i) - (iv) in the proof of Proposition 4.7.1. Based on Proposition 4.6.9 we expect to require normed linear space structure on X and Fréchet di↵erentiability of f at x⇤. Indeed a quick look at step (iii) below tells us that normed linear space structure will be needed. So we asssume it up front.
(i) Suppose that x⇤ is not a strict local minimizer of f in S.
(ii) There exists a sequence xk 2 S converging to x ⇤ and such that f(xk)
f(x⇤).
(iii) Our analog of step (iii) is
f(xk) � f(x ⇤)
kxk � x⇤k 0 8 k. (4.29)
(iv) Expression (4.28) relates the limit of function di↵erences from (4.27) to a derivative. Hence, in our more general setting we first consider the expression
lim k
f 0(x⇤)
✓
xk � x ⇤)
kxk � x⇤k
◆
= lim k
✓
f(xk) � f(x ⇤)
kxk � x⇤k
◆
. (4.30)
78 [Draft – distribution restricted to CAAM 560 students]
A proof of (4.30) follows. Since f is Fréchet di↵erentiable at x⇤ we have that for given " > 0 there exists an integer K such that for all k � K it follows that
|f(xk) � f(x ⇤) � f 0(x⇤)(xk � x
⇤)| "kxk � x ⇤ k. (4.31)
We rewrite (4.31) as
f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
� " f(xk) � f(x
⇤)
kxk � x⇤k
f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
+ ". (4.32)
First taking limit inferior in (4.32) and then recalling that " > 0 was arbitrary leads to
lim k
inf
✓
f(xk) � f(x ⇤)
k(xk � x⇤)k
◆
= lim k
inf f 0(x⇤)
✓
xk � x ⇤
k(xk � x⇤)k
◆
. (4.33)
Passing to a subsequence as needed, we have that (4.30) follows from (4.33). We are working towards an analog of (4.28). Towards this end realize that
if X = IRn, then the bounded sequence n
xk�x⇤ kxk�x⇤k
o
will have limit points.
Hence, turning to a subsequence, if necessary, we have that there exists h 2 IRn with khk = 1 and such that
(xk � x ⇤)
kxk � x⇤k ! h. (4.34)
Now putting together (4.29), (4.30), and (4.34) we have
f 0(x⇤)(h) = lim k
(f(xk) � f(x ⇤))
kxk � x⇤k 0, (4.35)
our general setting counterpart to (4.28). This demonstrates that if x⇤ is not a strict local minimizer of f in S, then (4.35) holds for at least one h of the form (4.34). The contrapositive statement is that if f 0(x⇤)(h) > 0 for all similarly situated h, then x⇤ is a strict local minimizer of f in S.
We postpone a formal statement of our newly derived su�ciency principle until after we introduce several definitions that we will use in the statement and discuss various properties and relationships of the various notions.
[Draft – distribution restricted to CAAM 560 students] 79
Definition 4.7.2. Consider a subset S of a normed linear space X and a vector x⇤ 2 S. Then
(a) A vector h 2 X is called a unit sequential tangent of S at x⇤ if there exists a sequence {xk 6= x
⇤ } ⇢ S converging to x⇤ and
h = lim k
(xk � x ⇤)
kxk � x⇤k . (4.36)
The collection of such h is called the sphere of sequential tangents to S at x⇤ and is denoted by Tsp(S, x
⇤).
(b) The cone spanned by Tsp(S, x ⇤) is called the cone of sequential tangents
to S at x⇤ and is denoted by Ts(S, x ⇤).
In the literature the cone of sequential tangents is invariably defined di- rectly in a rather nonintuitive manner and not defined as the cone generated by the sphere of sequential tangents, It is also called the contingent cone or the Bouligand cone. Appreciate that a quantity of the form f 0+(x
⇤)(z) is positive (or nonnegative) for all sequential tangents z if and only if it is positive (or nonnegative) for all unit sequential tangents z. This follows from the positive homogeneity of the forward directional variation. Hence the two notions will lead to equivalent principles.
For the sake of completeness we now demonstrate the equivalence of the two notions of sequential tangents alluded to above.
Proposition 4.7.3. Consider a subset S of a normed linear space X and a vector x⇤ 2 S. Then the following three statements are equivalent.
(i) h 2 X is a sequential tangent to S at x⇤. (ii)
h = lim k
xk � x ⇤
�k (4.37)
for some {xk 6= x ⇤ } ⇢ S converging to x⇤ and some {�k > 0} ⇢ IR
converging to 0.
80 [Draft – distribution restricted to CAAM 560 students]
(iii) h can be written in the form
h = khk lim k
✓
(xk � x ⇤)
kxk � x⇤k
◆
for some {xk 6= x ⇤ } ⇢ S converging to x⇤.
Proof. [(i) ) (ii)] Since h 2 Ts(S, x ⇤) for some ↵ > 0 we can write
h = ↵ lim k
(xk � x ⇤)
kxk � x⇤k = lim
k
(xk � x ⇤)
�k (4.38)
where �k = kxk�x⇤k
↵ .
[(ii) ) (iii)] From (4.37) we first observe that khk = limk kxk�x⇤k
�k ; hence we
can write
h = lim k
✓
(xk � x ⇤)
kxk � x⇤k
kxk � x ⇤ k
�k
◆
= khk lim k
(xk � x ⇤)
kxk � x⇤k .
[(iii) ) (i)] This follows directly from the definition of the cone of sequential tangents. ⌅
It is fairly straightforward that
Tc(S, x ⇤) ⇢ Ts(S, x
⇤). (4.39)
To see this consider z 2 Tc(S, x ⇤) with qualifying arc A : [0, ⌧) ! S. If we let
xk = A( ⌧ k ), then xk ! x
⇤ = A(0). Here we used the fact that A is continuous from the right at 0. Also
(xk � x ⇤)
⌧ k
= (A(⌧
k ) � A(0))
⌧ k
! A0+(0) = z.
Hence, z 2 Ts(S, x ⇤). Our next task is to show that in general the contain-
ment described in (4.39) is strict as was the case in (4.21).
[Draft – distribution restricted to CAAM 560 students] 81
Example 4.7.4. Let X = IR and
S = {0} [
⇢
1
k : k = 1, 2, . . .
�
.
Consider {xk = 1 k } converging to 0. Then z = 1 is a spherical sequential
tangent, but there are no nonzero feasible smooth arcs emanating from 0.
We now give a formal statement of the fundamental principles for first- order necessity and first-order su�ciency that resulted from our exploratory activity. For convenience and compatibility with the existing literature we use the cone and not the sphere of sequential tangents in our statements.
Proposition 4.7.5. Consider problem (4.1) where X = IRn and f is Fréchet di↵erentiable at x⇤ 2 S.
(i) If x⇤ is a local minimizer of f in S, then necessarily
f 0(x⇤)(z) � 0 8 z 2 Ts(S, x ⇤). (4.40)
(ii) Satisfaction of the condition
f 0(x⇤)(z) > 0 8 z 2 Ts(S, x ⇤)
is su�cient for x⇤ to be a strict local minimizer of f in S.
It is certainly worth mentioning that our exploratory analysis leaves us with the strong belief that the cone of curvilinear tangents, Tc(S, x
⇤) is not su�ciently rich to support su�ciency, and in general this is true.
4.8 Beyond Sequential Tangents
We reflect on Proposition 4.7.5 and the fundamental principles it describes. Clearly Ts(S, x
⇤), as a generalization of Tc(S, x ⇤), is a remarkable concept.
The fit between IRn and Ts(S, x ⇤) is beautiful and is essentially perfect. In-
deed, our rule of thumb criterion that fundamental principles for necessity and su�ciency should be only an equal sign apart holds in this situation.
However, our exploratory journey is still not over. An important objective of ours is fundamental principles for optimization problems posed in infinite dimensional spaces, and not just in IRn, indeed. In this context the cone
82 [Draft – distribution restricted to CAAM 560 students]
of sequential tangents is of little value. The rub is that a given bounded
sequence e.g., n
xk�x⇤ kxk�x⇤k
o
may not have any convergent subsequences; hence
access to Ts(S, x ⇤) is precluded.
With an eye towards providing an infinite dimensional setting for Propo- sition 4.7.5, notice that for z 2 Tsp(S, x
⇤) we can write
z = lim k
✓
xk � x ⇤
kxk � x⇤k
◆
(4.41)
for some {xk 6= x ⇤ } ⇢ S converging to x⇤. Moreover if f 0(x⇤) is a Fréchet
derivative, then
f 0(x⇤)(z) = f 0(x⇤) lim k
✓
xk � x ⇤
kxk � x⇤k
◆
(4.42)
= lim k
f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
(4.43)
= lim k
inf f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
(4.44)
Now, suppose we are given {xk 6= x ⇤ } ⇢ S converging to x⇤ and we consider
⇢
xk � x ⇤
kxk � x⇤k
�
. (4.45)
For this sequence the quantity appearing in (4.44) is well-defined in the full generality of normed linear spaces. However, the quantity appearing in (4.42) is well-defined only if (4.41) holds. Moreover, we can guarantee this for (4.45), or a subsequence, if and only if X is finite dimensional. Hence we have discovered a notion that applies in infinite-dimensional X and coincides with the standard notion when X is finite dimensional. This gives us the mechanism for pursuing our objective of giving Proposition 4.7.5, and future propositions that we will develop, infinite-dimensional settings.
In contrast to the approaches that use linear tangents, curvilinear tan- gents, or sequential tangents, we call the approach that rejects the use of tangents and uses only normalized di↵erence sequences (4.45), and quan- tities like those in (4.44), the limitless sequence approach or the limitless sequence framework.
[Draft – distribution restricted to CAAM 560 students] 83
4.9 Fundamental Principles for First-Order Necessity
In this section we give a formal statement of the material on necessity that was discussed in the previous section. Our concern is problem (4.1) where we are interested in minimizing a function f defined on a subset S of a vector space X. Unless otherwise stated we assume no additional structure on X, S, or f. As in the previous section, minimizer means global or local when the environment supports this latter notion.
We assume a familiarity with the quantities: a feasible curvilinear arc A emanating from x⇤ (Definition 4.6.7), Tl(S, x
⇤) the cone of tangents of feasible linear arcs emanating from x⇤ (Definition 4.6.4), Tc(S, x
⇤) the cone of tangents of feasible curvilinear arcs emanating from x⇤ (Definition 4.6.7) and Ts(S, x
⇤) the cone of sequential tangents to S at x⇤ (Definition 4.7.2).
Theorem 4.9.1 (Fundamental Principles for First-Order Necessity). Con- sider problem (4.1). If x⇤ minimizes f over S ⇢ X, then necessarily the following conditions must hold
(i) �0+(0) � 0 whenever this forward directional variation exists where �(t) = f(A(t)) and A : [0, ⌧) ! S is a feasible arc emanating from x⇤,
(ii) f 0+(x ⇤)(z) � 0 8 z 2 Tl(S, x
⇤), whenever f has a forward directional variation at x⇤.
(iii) limk inf f 0(x⇤)
⇣
xk�x⇤ kxk�x⇤k
⌘
� 0
whenever X is a normed linear space, f is Fréchet di↵erentiable at x⇤, and {xk 6= x
⇤ } ⇢ S is a feasible sequence converging to x⇤.
(iv) Moreover, if we choose X to be IRn in (iii), then conditions (iii) is equivalent to the condition
f 0(x⇤)(z) � 0 8 z 2 Ts(S, x ⇤).
whenever f is Fréchet di↵erentiable at x⇤.
84 [Draft – distribution restricted to CAAM 560 students]
Proof. [(i)] In the discussion surrounding (4.22) and (4.23) we argue that (i) is essentially a restatement of our prototypical result established in Proposi- tion 4.6.1.
[(ii)] This is Proposition 4.6.6.
[(iii)] Suppose the inequality in (iii) does not hold. Then from (4.33) there exists arbitrarily large values of k such that
f(xk) < f(x ⇤).
However, xk ! x ⇤; so this contradicts the fact that x⇤ is a local minimizer.
[(iii)] ) (iv)] Consider z = Ts(S, x ⇤). By part (iii) of Proposition 4.7.3 we
have
z = kzk lim k
✓
xk � x ⇤
kxk � x⇤k
◆
(4.46)
hence (iii) ) (iv).
[(iv) ) (iii)] Suppose the there exists {xk 6= x ⇤ } ⇢ S converging to x⇤ with
the property that
lim k
inf f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
< 0. (4.47)
By choosing a subsequence of {xk}, and renaming it {xk}, we can replace lim inf in (4.47) with lim. Since we are in IRn where the unit sphere is compact we can choose a thinner subsequence of {xk}, and again rename it {xk}, with
the property that for some z 2 Ts(S, x ⇤) we have z = limk
⇣
xk�x⇤ kxk�x⇤k
⌘
. Finally,
since the Fréchet derivative is a continuous linear form we have from (4.47)
f 0(x⇤)(z) < 0. (4.48)
These steps are nicely depicted by viewing equations (4.42)-(4.44) in reverse order. Since (4.48) contradicts (iv), our supposition can not hold. Hence (iv) ) (iii). This proves our theorem. ⌅
[Draft – distribution restricted to CAAM 560 students] 85
Corollary 4.9.2. Consider problem (4.1) and x⇤ 2 S. Assume
(a) X is a normed linear space, and
(b) f is Fréchet di↵erentiable at x⇤.
If x⇤ minimizes f over S ⇢ X, then necessarily the following conditions must hold (i) f 0(x⇤)(z) � 0 8 z 2 Ts(S, x
⇤), and
(ii) f 0(x⇤)(z) � 0 8 z 2 Tc(S, x ⇤).
Proof. [(i)] We essentially proved this in the proof that (iii) ! (iv) in the proof of Theorem 4.9.1.
[(ii)] This result follows from part (i) of the corollary appealing to the con- tainment relationship (4.39). ⌅
Concerning conditions (i)-(ii) of Theorem 4.9.1, we ask the reader to observe that if �(t) = f(A(t)), then � is defined from an interval of reals to the reals. Hence, we can talk about the standard di↵erentiability properties of � even though the underlying space in our optimization problem is only a vector space and may have no topological structure. In our applications we would like to write �0(0) = f 0(x)A0(0), the so-called chain rule. However, in our general setting A0(0) is not a meaningful quantity since A : [0, ⌧) ! S where S ⇢ X and we don’t require the vector space X to have topological structure. Moreover, even when X does have topological structure, we saw (see (4.25)) that the use of the chain rule required Fréchet di↵erentiability of f; this in turn required normed linear space structure. Therefore, it is most important to observe that if the feasible arc has the form A(t) = x+tz, then �(t) = f(x + tz) and �0(0) = f 0(x)(z), the directional variation of f at x in the direction z. Hence there is considerable advantage to working with linear feasible arcs whenever possible. This point will be reinforced in §?? and §4.12 where we derive fundamental principles for second-order necessity, in Chapter 9 where we derive the variational inequality, and in Chapter 11 where we derive various general multiplier rules.
Immediately after developing our fundamental principles for first-order necessity, second-order necessity, and second-order su�ciency we will illus-
86 [Draft – distribution restricted to CAAM 560 students]
trate them by applying them to two rather simple, but important, problems. The first is the minimization of a function f over all of IRn, the so-called un- constrained optimization problem in IRn. The second is perhaps the second most simple problem and consists of minimizing a function f over a subspace S of IRn. By necessity our examples are simple, since our application theory is yet to be developed. Indeed, this is the task of the remainder of the text.
Example 4.9.3. Our task is to see what first-order necessity brings to un- constrained optimization in IRn.Toward this end consider problem (4.1) with S = X = IRn. Assume that f : IRn ! IR is directionally di↵erentiable (see Definition E.2.1) at a minimizer x⇤. Clearly Tl(S, x
⇤) = IRn. Our fundamen- tal principle for first-order necessity, (ii) of Theorem 4.9.1, tells us that
f 0(x⇤)(z) � 0 8 z 2 IRn. (4.49)
Since (4.49) must also hold for �z, it follows that
f 0(x⇤)(z) = 0 8 z 2 IRn. (4.50)
From Example E.2.15, we see that the gradient represents the derivative so we can write
f 0(x⇤)(z) = hrf(x⇤), zi = 0 8 z 2 IRn.
It follows that the gradient vector must vanish. Hence, a first-order necessity condition for x⇤ to minimize f : IRn ! IR is whenever f is directionally di↵erentiable at x⇤, then (necessarily)
rf(x⇤) = 0.
Example 4.9.4. We investigate first-order necessity for the constrained problem where x⇤ minimizes f over a subspace S of IRn. Clearly,
Tl(S, x ⇤) = S.
Assuming that f is directionally di↵erentiable at x⇤, (ii) of Theorem 4.9.1 tells us that
f 0(x⇤)(z) � 0 8 z 2 S;
[Draft – distribution restricted to CAAM 560 students] 87
As before, since z 2 S ) �z 2 S, we have
f 0(x⇤)(z) = 0 8 z 2 S.
And therefore,
hrf(x⇤), zi = 0 8 z 2 S.
Hence, a first-order necessity condition for x⇤ to minimize f : IRn ! IR over a subspace S is whenever f is directionally di↵erentiable at x⇤, then (neces- sarily) the gradient of f at x⇤ is contained in the orthogonal complement of S i.e,
rf(x⇤) 2 S?.
4.10 Fundamental Principles for First-Order Su�ciency
We move directly to the formal statement of the fundamental principles for first-order su�ciency that we were led to by our exploratory analysis in §4.7, §4.8 and §4.9. Be aware that our proof of the following theorem is essentially the proof adapted from the proof of Proposition 4.7.1, our prototypical result for first-order su�ciency. Recall Definition 4.7.2 for Ts(S, x
⇤), the cone of sequential tangents to S at x⇤.
Theorem 4.10.1 (Fundamental Principles for First-Order Su�ciency). Con- sider problem (4.1) and x⇤ 2 S. Assume
(a) X is a normed linear space.
(b) f is Fréchet di↵erentiable at x⇤.
Then,
(i) Satisfaction of the condition
lim k
inf f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
> 0 (4.51)
for all sequences {xk 6= x ⇤ } ⇢ S converging to x⇤ is su�cient for x⇤ to
be a strict local minimizer of f in S.
88 [Draft – distribution restricted to CAAM 560 students]
Moreover, if X = IRn, then statement (i) is equivalent to the statement
(ii) Satisfaction of the condition
f 0(x⇤)(z) > 0 8 z 2 Ts(S, x ⇤) (4.52)
is su�cient for x⇤ to be a strict local minimizer of f in S.
Proof. [(i)] Let condition (4.51) hold. Suppose that x⇤ is not a strict local minimizer of f in S. Then we can construct {xk 6= x
⇤ } ⇢ S converging to x⇤
and satisfying
f(xk) f(x ⇤).
It follows that
lim k
inf
✓
f(xk) � f(x ⇤)
kxk � x⇤k
◆
0. (4.53)
However, from (4.33) we see that (4.53) contradicts (4.51). Hence, our sup- position is not valid and we have established part (i).
[(i) , (ii)] An argument quite similar to one used to show that in Rn (iii) and (iv) in Theorem 4.9.1 are equivalent, can be used to show that in the case that X = Rn (i) and (ii) of this theorem are equivalent. ⌅
When we compare (iii) of Theorem 4.9.1 with (4.51) and (i) of Corol- lary 4.9.2 with (4.52) we are pleased to see that our rule of thumb for our theory holds; necessity and su�ciency are only an equal sign apart.
Example 4.10.2. Consider the problem of minimizing f(x1, x2) = x1 + x2 over the nonnegative orthant S = {(x1, x2) 2 IR
2 : x1 � 0, x2 � 0}. It is quite obvious that the origin is uniquely a strict global minimizer. However, it will be educational to see how much information we can gather from our local theory in this direction. To begin with
f 0(0)(z) = z1 + z2 for z 2 IR 2.
Next, observe that for any choice of norm Ts(S, 0) ⇢ S. If we choose as norm the `1 norm, k(x1, x2)k = |x1| + |x2|, then
f 0(0)
✓
z
kzk
◆
= 1 for z 6= 0 contained in Ts(S, 0).
[Draft – distribution restricted to CAAM 560 students] 89
So (ii) of Theorem 4.10.1 holds and the origin is a strict local minimizer of f in S. We immediately ask if our necessity theory, Theorem 4.9.1, gives us any additional information. It tells us that at a minimizer x⇤ we must have
f 0(x⇤)(z) = z1 + z2 � 0 for all z 2 Tl(S, 0). (4.54)
Example 4.6.5 shows that points in S come in four distinct flavors. These flavors are represented by points p1, p2, p3, p4 described in Example 4.6.5 along with the tangent cones they produce. The necessary condition (4.54) for the four cases becomes
z1 + z2 � 0 for all (z1, z2) satisfying
p1 : z1 � 0 and z2 � 0
p2 : z2 � 0
p3 : z1 � 0
p4 : z 2 IR 2.
Hence, the only point that can be a minimizer is p1, the origin. Our local theory has told us that the origin is a minimizer and there are no others. It has not told us that the origin is a global minimizer. The theory that tells us this is the so-called variational inequality developed in Chapter 7.
4.11 The Need for an Auxiliary Objective Func- tion
As we reflect on statements (4.14) and (4.15), our prototypical results for second-order necessity and second-order su�ciency, serious reservations as to their usefulness immediately arise. We know that in unconstrained op- timization, say 0 is a minimizer of f in (�1, 1) and f 0(0) exists, that necessarily f 0(0) = 0. Now, consider our constrained prototypical problem (4.13) as depicted in Figure 4.4. Proposition 4.6.1, our prototypical result for first-order necessity, tells us that necessarily f 0+(0) � 0 . The assumption that f 0+(0) = 0 is excessively demanding. Indeed, if we consider all problems of the form of problem (4.13), then we expect f 0+(0) to be uniformly dis- tributed in the interval [0, 1); hence the probability of having f 0+(0) = 0 is zero. This implies that expecting the derivative of the function of a randomly
90 [Draft – distribution restricted to CAAM 560 students]
selected constrained optimization problem to vanish at a minimizer is com- pletely unrealistic. Moreover, the proof of our prototypical results suggest no direct way to circumvent the need for a zero derivative. Hence, It seems then that the only way to e↵ectively use our prototypical results to build useful theory for more general settings is: given a particular constrained optimiza- tion problem, consider the construction of an auxiliary objective function for this problem which retains much of the information of the given objective function and has the added property that its derivative vanishes at the min- imizer in question. Towards this end, our understanding at this point tells us that given problem (4.1) with objective function f we must search for an auxiliary function F with the properties that when x⇤ minimizes f over S, then x⇤ minimizes F over S and F 0(x⇤) = 0 in order to build necessity theory in terms of F , and when x⇤ 2 S minimizes F over S and F 0(x⇤) = 0, then x⇤ minimizes f over S in order to build su�ciency theory in terms of F .
Hence, looking forward to the generality of problem (4.1) , we have moti- vated the following desirable properties that an e↵ective auxiliary objective function F : S ! IR should posses when dealing with theory for minimiza- tion problems. Given x⇤ 2 S consider F : S ! IR satisfying the following properties
(i) F has the same di↵erentiation properties as f at x⇤,
(ii) F(x⇤) = ↵f(x⇤) for some ↵ > 0,
(iii) F 0(x⇤) = 0,
(iv) F(x) � ↵f(x) 8 x 2 S for necessity theory
(v) F(x) ↵f(x) 8 x 2 S for su�ciency theory
Observe that if (iv) holds and f has a minimizer at x⇤, then F has a minimizer at x⇤ and since F 0(x⇤) = 0 our principle for second-order necessity, to yet be derived from our prototypical result, can be stated in terms of F 00(x⇤). On the other hand, if (v) holds and F has a minimizer at x⇤, then f has a minimizer at x⇤, so our su�ciency theory can be stated in terms of F 00(x⇤) and the existence of the minimizer for f will follow from the existence for F . In summary then we have discovered that auxiliary functions satisfying conditions (v) promote su�ciency theory, while auxiliary functions satisfying condition (iv) promote necessity theory.
[Draft – distribution restricted to CAAM 560 students] 91
Of course, asking for both (iv) and (v) to hold is equivalent to asking that F(x) = f(x) in S. While this may be possible in simple cases, see Example 4.12.5 in the next section, in general such a requirement would be excessively demanding. But the situation is actually worse; requirement (iv) in general, is incompatible with minimization theory. To see this consider the situation depicted in Figure 4.3. Observe that if f 0+(0) > 0 , then it is not possible to construct an auxiliary function F : [0, ⌧) ! IR satisfying F 0(0) = 0, F(0) = ↵f(0), and F(x) � ↵f(x) for x near 0 for any ↵ > 0.
However, all is not completely lost in the use of auxiliary functions in the construction of necessity theory for minimization problems. While we should not expect to have F(x) � ↵f(x) throughout the feasibility region, it could well happen that this inequality holds along a particular feasible arc A : [0, ⌧) ! S emanating from x⇤, i.e., F(A(t)) � ↵f(A(t)) 8 t 2 [0, ⌧) or along a feasible sequence {xk} ⇢ S converging to x
⇤, i.e., F(xk) � ↵f(xk) 8 k. This will allow us to prove a somewhat limited form of necessity theory. However, we quickly add that this limited form of necessity theory serves us reasonably well in the construction of second-order necessity theory for nonlinear programming presented in Chapter 12. When we arrive there re- member that the clever use of feasible arcs displayed is e↵ectively dealing with the shortfall in the use of auxiliary functions for deriving second-order necessity conditions for minimization problems that we are currently dis- cussing.
We formally define our notion of auxiliary function.
Definition 4.11.1 (Local Support Function). Consider f : S ⇢ X ! IR and x⇤ 2 S. Assume
(a) X is a topological, linear space, and
(b) f has at least a directional variation at x⇤.
We call F : S ! IR a local lower support function for f at x⇤ if
(i) F has the same di↵erentiability properties as f,
(ii) F(x⇤) = ↵f(x⇤) for some ↵ > 0,
(iii) F 0(x⇤) = 0, and
(iv) F(x) ↵f(x) for all x contained in S intersect a neighborhood of x⇤.
92 [Draft – distribution restricted to CAAM 560 students]
If instead F satisfies (i)-(iii) and (iv) with the inequality reversed we call F a local upper support function for f at x⇤. Furthermore, if in place of (iv) we have
(iv)0 F(A(t)) ↵f(A(t))
for a given smooth feasible arc A emanating from x⇤, or
(iv)00 F(xk) ↵f(xk)
for a given feasible sequence {xk} converging to x ⇤, we say that F is a lower
support function for f at x⇤ along the arc A, or along the sequence {xk}, respectively. As above if the inequality in (iv)0 or (iv)00 is reversed we replace the qualifier lower with the qualifier upper.
We now give a formal reminder of the main features of support functions.
(i) If x⇤ is a local minimizer of f in a subset S, then x⇤ is a local minimizer of any local upper support function F for f at x⇤ in the given subset of S. Hence necessity theory can be stated in terms of the support function F .
(ii) If x⇤ is a local minimizer of a local lower support function F for f at x⇤
in a subset S, then x⇤ is a local minimizer of f at x⇤ in the given subset of S. Hence su�ciency theory can be stated in terms of the support function F .
Proof. The proofs are straightforward. ⌅ We end this section with the following motivation for support functions.
Remark 4.11.2. Our approach to deriving first-order necessary conditions for the nonlinear programming problem (1.5) will be to use our first-order necessity principles given in Theorem 4.9.1 and Corollary 4.9.2 to construct an upper support function F for the objective function f using so-called Euler-Lagrange multiplier theory. Hence the essential part of the first-order conditions will have the form
(a) F 0(x⇤) = 0,
(a) hi(x ⇤) = 0, and
(c) gi(x ⇤) � 0.
[Draft – distribution restricted to CAAM 560 students] 93
4.12 Fundamental Principles for Second-Order Necessity
We begin by proving our prototypical result. Let f be defined on [0, ⌧). When we say that f is di↵erentiable on [0, ⌧),
we mean that f is di↵erentiable on (0, ⌧) and f 0+(0) exists. In this case, we define
f 00+(0) = lim t#0
f 0(t) � f 0+(0)
t .
Proposition 4.12.1 (Prototypical Result for Second-Order Necessity). Con- sider f : [0, ⌧) ! IR such that 0 is a minimizer of f in [0, ⌧). Assume that f is di↵erentiable on [0, ⌧). If f 0+(0) = 0, then f
00 +(0) � 0 whenever f
00 +(0)
exists.
Proof. Choose a sequence {sk} such that sk 2 (0, ⌧) and sk ! 0. By the mean-value theorem, there exists tk 2 (0, sk) satisfying
f(sk) � f(0)
sk = f 0(tk).
Because 0 is a minimizer, it follows that f 0(tk) � 0, and therefore that
f 00(0) = lim k
f 0(tk) � f 0 +(0)
tk = lim
k
f 0(tk)
tk � 0.
⌅
While this prototypical result for second-order necessity and its proof point us in the right direction towards fundamental principles for second- order necessity, they not take us very far and this forces a certain amount of creativity on our part. Moreover, key understanding gained from Proposi- tion 4.12.1, our prototypical result for second-order necessity, and the discus- sion from Section 4.11 on support functions tells us that in deriving funda- mental principles for second-order necessity we must either make the restric- tive assumption that the first derivative is zero at a minimizer or turn to the use of a support function. However, in this use of support functions for min- imization we must turn to the notion of an upper support function instead of the more natural notion, for minimization, of a lower support function.
94 [Draft – distribution restricted to CAAM 560 students]
Theorem 4.12.2 (Fundamental Principle for Second-order Neces- sity). Consider problem (4.1) with solution x⇤.
(i) Given A : [0, ⌧) ! S, a feasible arc emanating from x⇤, define � : [0, ⌧) ! R by
�(t) = f(A(t)).
Assume
(a) X is a vector space.
(b) � is di↵erentiable on [0, ⌧) and �00+ exists.
If
�0+(0) = 0,
then (necessarily) ,
�00+(0) � 0.
(ii) Assume
(a) X is a normed linear space.
(b) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative at x⇤.
Then, for each sequence {xk 6= x ⇤ } ⇢ S converging to x⇤ and for each
F which is an upper support function for f at x⇤ along the sequence {xk} we (necessarily) have
lim k
inf F 00(x⇤)( xk � x
⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) � 0. (4.55)
(iii) If X = Rn, then statement (ii) is equivalent to the statement: For each z 2 Ts(S, x
⇤) and for each F which is an upper support func- tion for f at x⇤ along the sequence {xk}, the defining sequence for z, we (necessarily) have
F 00(x⇤)(z, z) � 0.
Proof. [(i)] The proof of our prototypical result, Proposition 4.11.1, can be used to establish this result.
[Draft – distribution restricted to CAAM 560 students] 95
[(ii)] Turning to proposition E.8.10 in Appendix E, we have for a given ✏ > 0 there exists K > 0 such that for all k � K
|F(xk) � F(x ⇤) � F 0(x⇤)(xk � x
⇤) � 1
2 F 00(x⇤)(xk � x
⇤ k � x
⇤)| ✏||xk � x ⇤ ||
2.
(4.56) Observing that F(x⇤) = ↵f(x⇤), and F 0(x⇤) = 0 reduces (4.56) to
1
2 F 00(x⇤)(
xk � x ⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) � ✏
F(xk) � ↵f(x ⇤)
||xk � x⇤||2 (4.57)
1
2 F 00(x⇤)(
xk � x ⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) + ✏
Now, (4.55) follows from (4.57) by observing that F(xk) � ↵f(xk) � ↵f(x ⇤),
taking the limit inferior in k, and then recalling that ✏ > 0 was arbitrary.
[(iii)] Again, the argument used in the proof that in Rn part (iii) of Theorem 4.9.1 is equivalent to part (iv) can be used to prove that in Rn (ii) is equivalent to (iii)
⌅
Corollary 4.12.3. Consider problem 4.1 with solution x⇤.
(i) Assume
(a) X is a vector space, and
(b) f has a directional variation at all points in X and has a second directional variation at x⇤.
Consider z 2 Tl(S, x ⇤).
If f 0(x⇤)(z) = 0,
then (necessarily) f 00(x⇤)(z, z) � 0.
(ii) Assume
(a) X is a normed linear space
(b) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative at x⇤, and
96 [Draft – distribution restricted to CAAM 560 students]
(c) A : [0, ⌧) ! S is a feasible arc emanating from x⇤ that has a directional variation in an interval (0, ✏) for some ✏ ⌧, has a forward (right-sided) directional variation at 0, and has a forward (right-sided) second directional variation at 0.
Then, for each F which is an upper support function for f at x⇤ along the arc A we (necessarily) have
F 00(x⇤)(A0+(0), A 0 +(0)) � 0.
Proof. [(i)] For the given z 2 Tl(S ⇤, x⇤) consider
�(t) = f(x⇤ + tz).
We have �0(t) = f 0(x⇤ + tz)(z),
and �00(0) = f 00(x⇤)(z, z).
The result now follow from part (i) of the theorem. [(ii)] For the given arc A consider
�(t) = F(A(t)).
We have �0(t) = F 0(A(t))(A0(t)),
and �00(0) = F 00(A(0))(A0+(0), A
0 +(0)) + F
0(A(0))(A00+(0)).
Since F is a support function we know that F 0(A(0)) = 0. Hence, our desired result now follow from part (i) of the theorem replacing f with F and observing that x⇤ also minimizes F along the arc A, since F is an upper support function. ⌅
We now give two examples that demonstrate the use of Theorem 4.12.2
Example 4.12.4. We return to the unconstrained minimization of f : IRn ! IR as discussed in Example 4.9.3. Let x⇤ be a minimizer of f and assume that f is directionally di↵erentiable in a neighborhood of x⇤ and has a sec- ond directional derivative at x⇤. In passing we note that in IRn directional
[Draft – distribution restricted to CAAM 560 students] 97
di↵erentiability is equivalent to Gâteaux di↵erentiability since all linear op- erators are bounded in IRn. For z 2 IRn consider the feasible linear arc A : [0, ⌧) ! IRn defined by A(t) = x⇤ + tz and also consider
�(t) = f(A(t)) for t 2 [0, ⌧).
Then from Proposition E.8.8
�0+(0) = hrf(x ⇤), zi
and
�00+(0) = hr 2f(x⇤)z, zi
where rf(x⇤) is the gradient vector of f at x⇤ and r2f(x⇤) is the Hessian matrix of f at x⇤. From Example 4.9.3, �0+(0) = 0; hence from (i) of The- orem 4.12.2 �00+(0) � 0. It follows that second-order necessary conditions for unconstrained minimization, i.e., for x⇤ to minimize f : IRn ! IR are whenever f is directionally di↵erentiable in a neighborhood of x⇤ and has a second directional derivative at x⇤, then (necessarily)
(i) rf(x⇤) = 0, the gradient vector of f at x⇤ vanishes.
(ii) r2f(x⇤), the Hessian matrix of f at x⇤ is positive semi-definite on IRn.
Example 4.12.5. We return to the minimization of f : IRn ! IR over a subspace S of IRn as discussed in Example 4.9.4. Let x⇤ be a minimizer of f in S. Assume that f is directionally di↵erentiable in a neighborhood of x⇤
and has a second directional derivative at x⇤. From first-order necessity, see Example 4.9.4, we know that
rf(x⇤) 2 S?. (4.58)
This gives us a lead into the construction of a support function. We can write (4.58) as
rf(x⇤) = ↵⇤1a1 + · · · + ↵ ⇤ mam (4.59)
where {a1, . . . , am} is a basis for S ? and ↵⇤i 2 IR. Some reflection on (4.59)
leads us to consider
F(x) = f(x) � ↵⇤1ha1, xi � · · · � ↵ ⇤ mham, xi (4.60)
98 [Draft – distribution restricted to CAAM 560 students]
as our support function, since then we will have F 0(x⇤) = 0. Clearly F and f have the same di↵erentiability properties. Moreover, F(x) = f(x) for x 2 S. Hence F is both a lower support function and an upper support function for f at x⇤.
For z 2 S the linear arc A(t) = x⇤ + tz is feasible for all t. Hence, from part (ii) of Theorem 4.12.2 we have
F 00(x⇤)(z, z) � 0.
However, in this case F 00(x⇤) = f 00(x⇤). So our second-order necessity condi- tions for the problem of minimizing f over S are whenever f is directionally di↵erentiable in a neighborhood of x⇤ and has a second directional derivative at x⇤, then (necessarily)
(i) rf(x⇤) 2 S?, the gradient vector of f at x⇤ is contained in the orthog- onal complement of S.
(ii) r2f(x⇤), the Hessian matrix of f at x⇤, is positive semi-definite on the subspace S.
Observe that in the generality of Example 4.12.4 and Example 4.12.5 r
2f(x⇤) need not be symmetric, see Remark E.8.9. If we require Fréchet di↵erentiability, then the Hessian matrix will be symmetric.
The knowledgeable reader may say that the support function (4.60) is merely the standard Lagrangian function introduced in Chapter 10. While we agree that they are the same we maintain that the construction here has a significantly di↵erent flavor. We did not introduce functional equality constraints.
4.13 Fundamental Principles for Second-Order Su�ciency
As usual we begin with the proof of our prototypical result for second-order su�ciency
Proposition 4.13.1 ((Prototypical Result for Su�ciency)). Consider f : [0, ⌧) ! R and assume that f is di↵erentiable on [0, ⌧) and f 00+(0) exists. If
f 0+(0) = 0 and f 00 +(0) > 0,
then 0 is a strict local minimizer of f in [0, ⌧).
[Draft – distribution restricted to CAAM 560 students] 99
Proof. Suppose that 0 is not a strict local minimizer of f in [0, ⌧). Then, there exists {xk} ⇢ (0, ⌧) converging to 0 and such that f(xk) f(0). For a given ✏ > 0 there exists K > 0 such that for all k � K (4.56) holds with t replaced by xk. By construction f(xk) � f(0) 0; so (4.56) reduces to
1
2 f 00+(0) � ✏ 0
But ✏ > 0 was arbitrary; hence
f 00+(0) 0.
This contradicts our hypothesis; so our supposition can not hold, and 0 is a strict local minimizer of f in [0, ⌧). ⌅
Theorem 4.13.2 (Fundamental Principles for Second-Order Su�- ciency). Consider f : S ⇢ X ! R and x⇤ 2 S. Assume
(a) X is a normed linear space.
(b) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative at x⇤.
(i) The conditions that for each sequence {xk 6= x ⇤ } ⇢ S converging to x⇤
we have
(c)
f 0(x⇤) (xk � x ⇤) � 0, and (4.61)
(d) if this sequence satisfies
lim k
f 0(x⇤)( xk � x
⇤
||xk � x⇤|| ) = 0, (4.62)
then, it follows that
lim k
inf f 00(x⇤)( xk � x
⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) > 0, (4.63)
are su�cient for x⇤ to be a strict local minimizer of f in S.
100 [Draft – distribution restricted to CAAM 560 students]
(ii) If X = Rn, then statment (i) is equivalent to the statement: The condition that for each nonzero z 2 Ts(S, x
⇤) we have
(c) f 0(x⇤)(xk � x ⇤) � 0,
where {xk} is the defining sequence for z, and
(d) if z satisfies f 0(x⇤)(z) = 0, (4.64)
then it follows that f 00(x⇤)(z, z) > 0, (4.65)
are su�cient for x⇤ to be a strict local minimizer of f in S.
(iii) The condition that for each {xk 6= x ⇤ } ⇢ S converging to x⇤ there exists
a lower support function F with the property that if
lim k
f 0(x⇤)( xk � x
⇤
||xk � x⇤|| ) = 0, (4.66)
then it follows that
lim k
inf F 00(x⇤)( xk � x
⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) > 0 (4.67)
is su�cient for x⇤ to be a strict local minimizer of f in S.
(iv) Moreover, If X = Rn, then statement (iii) is equivalent to the state- ment: The condition that for each nonzero z 2 Ts(S, x
⇤) there exists a lower support function F with the property that if
f 0(x⇤)(z) = 0, (4.68)
then it follows that F 00(x⇤)(z, z) > 0, (4.69)
is su�cient for x⇤ to be a strict local minimizer of f in S.
Proof. [(i)] Suppose that x⇤ is not a strict local minimizer. Then there exists {xk 6= x
⇤ } ⇢ S converging to x⇤ and satisfying
f(xk) f(x ⇤). (4.70)
[Draft – distribution restricted to CAAM 560 students] 101
Since f is Fréchet di↵erentiable at x⇤, we can appeal to (4.33) and (4.70) to obtain
lim k
inf f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
0. (4.71)
Hence a subsequence, which we again call {xk}, satisfies (4.62). So (4.63) must hold. Now, an argument similar to that we used to derive (4.55) from (4.56) can be used to derive
lim k
inf f 00(x⇤)( xk � x
⇤
||xk � x⇤|| ,
xk � x ⇤
||xk � x⇤|| ) 0 (4.72)
calling on inequalities (4.61) and (4.71). But (4.72) contradicts (4.63). So, we have established part (i) of the theorem.
[(ii)] The proof that in the case X = Rn (i) is equivalent to (ii) follows along the lines of an argument that has now become standard for us.
[(iii)] The proof here is much like the proof of [(i)]. To begin with suppose that x⇤ is not a strict local minimizer. Then there exists {xk 6= x
⇤ } ⇢ S
converging to x⇤ satisfying (4.70); Hence we also have (4.71). Now, by hypothesis we are guaranteed the existence of a lower support
function F for f at x⇤. Consider G(x) = ↵f(x) � F(x). Turning to the definition of the local support function F we see that G(x⇤) = 0 and G(x) � 0 for all x in S \ N where N is a neighborhood of x⇤. Hence x⇤ is a local minimizer of G in S. Moreover, F is Fréchet di↵erentiable at x⇤ since we are assuming f is and by definition F has the same di↵erentiability as f. So, our fundamental principle for first-order necessity (iii) of Theorem (4.9.1) tells us that
lim k
inf G0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
� 0 (4.73)
for our given sequence. Since F 0(x⇤) = 0, G0(x⇤) = ↵f 0(x⇤). Hence replacing G0(x⇤) with ↵f 0(x⇤) in (4.73) and combining it with (4.71) leads to
lim k
inf f 0(x⇤)
✓
xk � x ⇤
kxk � x⇤k
◆
= 0. (4.74)
Now, by replacing {xk} with an appropriate subsequence, which without loss of generality we also call {xk}, we have that (4.74) implies (4.66). Hence by hypothesis (4.67) holds.
102 [Draft – distribution restricted to CAAM 560 students]
As before, turning to the argument that we used to derive (4.55) from (4.57), considering expression (4.70) for this sequence, recalling that F(xk) f(xk) f(x
⇤), taking lim inf in k, and remembering that " > 0 was arbitrary gives
lim k
inf F 00(x⇤)
✓
xk � x ⇤
kxk � x⇤k ,
xk � x ⇤
kxk � x⇤k
◆
0. (4.75)
But (4.75) contradicts (4.67); hence our supposition can not hold and x⇤ is a strict local minimizer of f in S.
⌅
Corollary 4.13.3. Consider f : S ⇢ X ! R and x⇤ 2 S. Assume
(a) X is a normed linear space,
(b) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative at x⇤. The conditions that
(c) f 0(x⇤)(x � x⇤) � 0 8 x 2 S, and
(d) f 00(x⇤)(x � x⇤, x � x⇤) � c||x � x⇤||2 8 x 2 S and for some constant c > 0,
are su�cient for x⇤ to be a strict local minimizer of f in S.
Proof. This is a somewhat standard result in the optimization literature and the proof is quite direct. However, our objective is to test our theory by showing that this result follows directly from our theorem. Clearly conditions (c) and (d) of the corollary imply conditions (c) and (d) of part(i) of the theorem. ⌅
It is interesting that in the proof of part (iii) of the Theorem 4.13.2 we demonstrated that the existence of a local lower-support function f at x⇤
implies the first-order necessary condition (iii) of Theorem 4.9.1 at x⇤. This fact should not be construed as restrictive, since if the conclusion of the theorem holds, i.e., x⇤ is a minimizer, then the necessary condition must hold.
[Draft – distribution restricted to CAAM 560 students] 103
When we compare (ii) of Theorem 4.12.2 with (iii) of Theorem 4.13.2 we see that, our rule of thumb does not hold, i.e., necessity conditions and su�ciency conditions are not just an equal sign apart. If instead we did not introduce the support function F and stated our results in terms of the objective function f, then our rule of thumb would hold. However, this theory would be less useful. Hence our rule of thumb is just that - a rule of thumb.
There is a significant distinction between our necessity theory and our su�ciency theory. The latter requires the use of the Fréchet derivative, the former does not. Our explorations promoted the understanding that in con- trast to necessity theory, su�ciency theory could not be constructed by con- sidering only behavior along lines or arcs. It requires a somewhat more global and more uniform behavior. This plays out in the need for Fréchet di↵eren- tiation as opposed to directional di↵erentiation. See part (ii) of Proposition E.5.1 for an example of a uniformity property of the Fréchet derivative.
Example 4.13.4. We wish to see what our fundamental principle for second- order su�ciency, Theorem 4.13.2, gives with respect to unconstrained mini- mization in IRn. Consider f : IRn ! IR and x⇤ 2 IRn. Assume that f has a Fréchet derivative in a neighborhood of x⇤ and has a second Fréchet deriva- tive at x⇤. Our first-order necessary condition is that rf(x⇤) = 0. Hence, we let f serve as its own support function. This means that one of our as- sumptions must be rf(x⇤) = 0. This assumption is not restrictive since it must hold if su�ciency holds. It is clear that T`(IR
n, x⇤) = IRn; hence Ts(IR
n, x⇤) = IRn, since the latter tangent cone contains the former. We see from part (i) of Theorem 4.13.2 that x⇤ will be a strict local minimizer if
f 00(x⇤)(z, z) = hr2f(x⇤)z, zi > 0 for all z 6= 0.
Hence, su�ciency conditions for x⇤ to be a strict local minimizer of f : IRn ! IR are
(i) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative at x⇤,
(ii) rf(x⇤) = 0, and
(iii) r2f(x⇤), the Hessian matrix of f at x⇤, is positive definite.
104 [Draft – distribution restricted to CAAM 560 students]
Example 4.13.5. We return to the problem of minimizing f : IRn ! IR over a subspace S of IRn. Let x⇤ 2 S be the point under consideration. We assume the first-order necessary condition rf(x⇤) 2 S?, see Example 4.9.4, so that F as defined by (4.60) qualifies as a local lower support function.
We now show that Ts(S, x ⇤) ⇢ S. If z 2 Ts(S, x
⇤), then from part (iii) of Proposition 4.7.3 we know that z can be written
z = kzk lim k
✓
xk � x ⇤
kxk � x⇤k
◆
(4.76)
for some sequence {xk 6= x ⇤ } ⇢ S converging to x⇤. Since S is a finite-
dimensional subspace it is closed and the limit in (4.76) is contained in S; hence z 2 S and Ts(S, x
⇤) ⇢ S as was to be demonstrated. It follows that
f 0(x⇤)(z) = hrf(x⇤), zi = 0 for all z 2 Ts(S, x ⇤), (4.77)
since rf(x⇤) 2 S?. Part (iii) of Theorem 4.13.2 tells us that x⇤ will be a strict local minimizer of f in S if
F 00(x⇤)(z, z) = hr2f(x⇤)z, zi > 0 for all z 2 Ts(S, x ⇤). (4.78)
Hence, su�cient conditions for x⇤ 2 S to be a strict local minimizer of f in S are
(i) f is Fréchet di↵erentiable in a neighborhood of x⇤ and has a second Fréchet derivative a x⇤,
(ii) rf(x⇤) 2 S?, and
(iii) r2f(x⇤), the Hessian of f at x⇤, is positive definite on S.
We find it interesting that we used a local lower support function to facilitate the application; but were able to state the su�ciency conditions free of the support function. It is also worth noting that for both of our example problems, except for di↵erentiation requirements, necessity conditions and su�ciency conditions are only an equal sign apart.
Notice that in (iii) above the condition was stated in terms of S. But (4.78) shows that the condition need only hold on Ts(S, x
⇤), a smaller set; which would lead to a stronger result. This situation nicely foreshadows the role of constraint qualification in Chapters 10 and 11. The tangent cone is in general an illusive set with challenging validation of membership. So the conditions are stated in terms of a somewhat larger set; leading to weaker but more usable theory.
[Draft – distribution restricted to CAAM 560 students] 105
4.14 Concluding Remarks
In this chapter we identified a basic prototypical problem, conjectured basic prototypical results concerning this basic problem, and then used them and their proofs to discover fundamental principles for necessity, su�ciency, and existence for general constrained optimization problems. The challenge that remains is the application of these principles to various constrained optimiza- tion problem classes in an e↵ort to derive useful practical theories. In order to do this, a notion called multiplier rules will be needed for several impor- tant applications . We build these multiplier rules in Chapters 9-11. This subtask will be accomplished maintaining the flavor of the approach used in the present chapter by deriving a fundamental principle for the construction of multiplier rules from a set of basic ingredients. The construction of useful theory for various problem classes from a handful of fundamental principles, and implicitly the construction of these principles themselves , is what we call our unified approach. As such we consider the fundamental principles presented in this chapter and the fundamental principle for the construction of multiplier rules that will be derived in Chapter 10 the heart beat of the text, indeed the heart beat of continuous optimization.
It is said that the proof of the pudding is in the eating. Well, certainly the proof of our unified approach will be the quality of the applications that it can be used to generate. Towards this end we will derive all the standard results in terms of multiplier rules and necessity and su�ciency theory and more. Moreover, a noteworthy accomplishment for our unified approach is that using our limitless sequence generalization of the standard sequential tangent fundamental principle for second-order su�ciency we are able to extend the standard su�ciency theory for nonlinear programming in IRn , often called the McCormick theory, to infinite dimensional Hilbert space settings without any additional assumptions. To our knowledge this is a first and speaks well for our limitless sequence approach. These issues will be discussed in detail in Chapter 13 where we cover su�ciency theory for nonlinear programming.
In Chapter 1 we asked the reader to appreciate the fact that optimiza- tion theory leads us to a set of conditions that a solution of the optimization problem must satisfy. These conditions are the first-order necessary condi- tions and appear in the form of equations and inequalities . It is the role of su�ciency theory to aid us in determining if these conditions have a solu- tion and the role of computational optimization to tell us how to calculate
106 [Draft – distribution restricted to CAAM 560 students]
(approximate) such a solution. Hence a large part of optimization theory activity consists of using the first-order necessary conditions to reduce the optimization problem at hand to a more tractable problem that is (hopefully) amenable to further study and/or computational methods.
As we have seen, sequential tangents and curvilinear tangents play a fun- damental role in our necessity theory. Unfortunately, for a given optimization problem, the collection of these tangents will , in general, constitute an elu- sive set that will be essentially impossible to characterize or access e↵ectively. Hence in their present forms , our necessity conditions are practically use- less. Therefore, our challenge is to use the mathematical information that they contain to construct useful necessary conditions that can be stated free of sequential tangents , feasible arcs, their tangents and other derivatives. As the reader will see in Chapters 10-12 it is exactly the so-called constraint qualifications that free us from this disabling dependence, of course at a price.
Let us reflect on the roles of the linear tangent framework, the curvilinear tangent framework, the sequential tangent framework, and the limitless se- quence framework. The notion of the sequential tangent cone in IRn is most elegant . The power of the sequential tangent framework, over that of the curvilinear tangent framework, was precisely what was needed to build an e↵ective fundamental principle for su�ciency in IRn. Moreover, it leads to a stronger theory even in the case of necessity, since the sequential tangent cone contains the curvilinear tangent cone. Hence, many authors restrict their attention to the sequential tangent framework and consider no other frameworks. We will now present the case that for our purposes such a restriction would be shortsighted.
In a limited form the linear tangent framework is actually quite old and was used, somewhat implicitly, by Lagrange. From our point of view it is extremely important because it is the only framework that we have that can be used in the full generality of vector spaces. As the reader will see in our applications in various parts of the text , this linear tangent framework serves us quite well.
The curvilinear tangent framework also serves us quite well. Based on our experience we find it more intuitive and friendly than the sequential tangent framework. We feel that it lends itself to better understanding , conjecture, and tangent construction. For example , in multiplier theory in constraint qualification applications we are required to qualify a given vector as a se- quential or curvilinear tangent. The use of powerful mathematical tools, for example the implicit function theorem , the inverse function theorem, and
[Draft – distribution restricted to CAAM 560 students] 107
ordinary di↵erential equation theory for the initial value problem can often be used to construct a feasible arc with the required tangent. Of course in turn this curvilinear tangent is also a sequential tangent. But as is the case so often it was constructed first as the tangent of a feasible arc. This will be the case for all of our constraint qualification constructions. Finally, our derivations will demonstrate that the feasible arc framework is su�ciently general to allow us to derive all the known standard necessity theory and some that is not so well known. Hence, it would be naive of us to dispense with this framework.
We are of the considered opinion that the limitless sequence framework will be e↵ective in infinite dimensional settings where the sequential sequence framework is deficient. Indeed, as mentioned earlier we claim that it is this more general framework that allows us to solve the previously unsolved prob- lem of extending the McCormick su�ciency theory to infinite dimensions. However, as the reader will see , the application to extending the McCormick theory is quite challenging, and we expect that this will be the case in other new important applications.
Finally, the notion of a support function is known, but not well known. Most authors in deriving second-order theory for nonlinear programming merely use the Lagrangian function as a support (as we will also do) without defining a support function and the role that a support function plays or the need that it serves. Our presentation of support functions follows the ideas presented by Hestenes ([?, Hest:66]. Without the notion of a support function, it is not possible to establish our fundamental principles for second- order necessity and su�ciency in the full generality of problem (4.1). We found the derivation of these principles to be one of our more challenging tasks.
4.15 Exercises
1. Show by example that in §4.5 our necessity conditions are not su�- ciency conditions and vice versa.
2. Prove that T`(S, x ⇤) is a cone.
3. Find the general solution of the equation
T`(S, x ⇤) = S
108 [Draft – distribution restricted to CAAM 560 students]
where S is a subset of IR2 and x⇤ is a point in IR2.
4. Consider the IR2 arc A(t) = (t, p
t)T for all t 2 [0, 1). Show that this arc is not smooth. Now parameterize this arc so that it is smooth. Thus, smoothness is not independent of parameterization.
5. Show that the IR2 arc A(t) = (t, t2sin(1 t ))T for t 2 (0, 1) and A(0) =
(0, 0)T is smooth.
6. (Hestenes page 210). In IR2 define the function g(x1, x2) = x2 � x21sin(
1 x1 ) for x1 6= 0 and g(0, x2) = x2. Let S = {(x1, x2) 2 IR
2 : x2 0 and g(x1, x2) � 0}. Compute Tc(S, 0) and Ts(S, 0).
7. Consider the unconstrained minimization problem
min x2IRn
Q(x) = ↵ � hb, xi + 1
2 hAx, x, i
where ↵ 2 IR, b 2 IRn, and A 2 IRn⇥n and is symmetric.
(a) In terms of conditions on A and b interpret
(i) first-order necessity
(ii) first-order su�ciency
(iii) second-order necessity
(iv) second-order su�ciency
(b) In IR2 give examples where the problem has
(i) no solutions
(ii) a unique solution
(iii) an infinite number of solutions.
(c) Demonstrate that for this problem a local minimizer is a global minimizer.
(d) Demonstrate that for this problem necessity conditions become su�ciency conditions.
(e) Given part (d); what do we obtain from second-order su�ciency that we do not obtain from second-order necessity? Give reasons for your answer.
[Draft – distribution restricted to CAAM 560 students] 109
8. In the text we pointed out that in comparing expression (4.60) with (4.71) we see that our necessity theory and our su�ciency theory is not just an equal sign apart. In your opinion on which theory have we done a better job? Give good reasons for your reply.
9. Former class member Mark Abramson shared with us the following result that he found in a contemporary optimization book:
“Let S be a subset of IRn, f a twice continuously di↵eren- tiable function on S, and x⇤ a local minimizer of f in S. Then the Hessian of f at x⇤ is positive semidefinite with respect to feasible directions in the null space of the gradient of f at x⇤.”
In our notation we would write: A necessary condition for x⇤ to be a local miniminer of twice continu- ously di↵erentiable f in S, is that
hr
2f(x⇤)⌘, ⌘i � 0 8 ⌘ 2 T`(S, x ⇤) \ {⌘ : hrf(x⇤), ⌘i = 0}.
(a) A picky point here that you should appreciate from Appendix E is that the gradient of f at x⇤ is a vector not an operator; hence it does not have a null space. Please correct the math phrasing.
(b) Prove the result stated above.
(c) Can you prove the results with T`(S, x ⇤) replaced by Tc(S, x
⇤)? If not modify the statement so that you have a valid result.
(d) Can you prove the results with T`(S, x ⇤) replaced by TS(S, x
⇤)? If not what additional assumptions do you have to make to arrive at a valid result?
(e) State and prove your result from part (d) for infinite-dimensional spaces via the limitless sequence approach.
10. Mark was really interested in a su�ciency result along the lines of the necessity result stated in problem 9. Please state and prove such a result for Mark.
110 [Draft – distribution restricted to CAAM 560 students]
