Spring 2016 Version
A TEXT FOR NONLINEAR PROGRAMMING
Thomas W. Reiland
Statistics Department
North Carolina State University
Raleigh, NC 27695-8203
Office: (919) 515-1939
Email:
Table of Contents
Chapter I: Optimality Conditions
§ 1.1 Differentiability
§ 1.2. Unconstrained Optimization
§ 1.3 Equality Constrained Optimization
§ 1.3.1 Interpretation of Lagrange Multipliers
§ 1.3.2 Second order Conditions – Equality Constraints
§ 1.3.3 The General Case
§ 1.4 Inequality Constrained Optimization
§ 1.5 Constraint Qualifications (CQ)
§ 1.6 Second-order Optimality Conditions
§ 1.7 Constraint Qualifications and Relationships Among Constraint Qualifications
Chapter II: Convexity
§ 2.1 Convex Sets
§ 2.2 Convex Functions
§ 2.3 Subgradients and differentiable convex functions
§ 1.4 Inequality Constrained Optimization
Generic Problem: Minimize , , f is continuously differentiable
Definition 1.4.1 Let be nonempty and let (closure of X ). The set of feasible directions of X at , denoted by is described by :
At this point, the reader is encouraged to review the definitions (1.1.5 & 1.1.6) for local minimum and global minimum points.
Consider such that . At a local minimum , these d’s must have an empty intersection with . Refer to the figure below.
Theorem 1.13 If is a local minimum of subject to , then , where .
Proof: Suppose there exists . Then there exists such that . Also, there exists such that .
Let . Then and if .#
This contradicts that is a local minimum. QED.
Consider Problem (P): Min ,
s.t.
f, gi’s, hj’s have continuous 1st partial derivatives
Define as the feasible region.
Revised definitions for local/global minimum points:
Local Minimum: is a local minimum of Problem (P) if there exists such that .
Global Minimum: is a global minimum of Problem (P) if .
Definition 1.4.2 A nonempty set is called a cone if implies that . If, in addition, C is convex, the C is called a convex cone.
Note: A set is convex if, for , , .
Example 1-26: Refer to the corresponding figures below.
(1) such that , together with is a convex cone (not closed).
(2) Any linear subspace L of is a convex cone.
(3)Given a collection , then all the nonnegative linear combinations
form a convex cone.
e.g. (3a)
e.g. (3b)
(4)This is a cone but it is not convex.
Lemma 1.14 A cone is convex if and only if
Proof: If C is convex and , then .
Suppose and , then
and since the sum of two vectors in C is again in C.
C is convex.
Remark: Every point x in a neighborhood of can be written as where if and only if ( since ).
Definition 1.4.3 The cone of feasible directions at , denoted , is a follows:
actually is a cone but not necessarily a convex cone and is important in many algorithms. For now, it holds our interest because if is a local minimum and , then for sufficiently small θ. Our goal is to characterize in terms of the constraint functions gi and hj.
Definition 1.4.4 is the linearizing cone of the feasible region evaluated at .
Where is the indicator function of the active inequality constraints.
Define
Remark: is a closed convex cone. Suppose . Then , and .
Lemma 1.15
Proof: Suppose for some , where ; in other words, suppose there exists a but the .
Then where as . If θ is small enough, then .
Since , we have , which contradicts .
Therefore, .
Similarly, we can show .
Remark: Since is closed, in fact we have . QED.
Lemma 1.16 If , then there exists a point sufficiently close to such that .
Proof:
for θ sufficiently small. QED.
Example 1-27: Min
s.t. (1)
(2)
(3)
is feasible with
Evaluating the multiple cases for leads to the final result below which is easily verified graphically using the figure above. The reader is encouraged to verify the result analytically as an exercise.
Note that .
Lemma 1.17 Farkas’ Lemma: Let A be an matrix; let . Then exactly one of the following two systems has a solution.
System 1: and for some
System 2: for some
Remark: The following is an equivalent statement:
satisfying if and only if there exists such that
Example 1-28: Geometric Interpretation of Lemma 1.17
Let m = 4, n = 2. Define ai = rows of A, i = 1,…,4
System 2 has a solution if c lies in the convex cone generated by the rows of A.
System 1 has a solution if the closed convex cone has a nonempty intersection with open half-space .
Definition 1.4.5 Define the Lagrangian associated with Problem (P) as
Theorem 1.18 Suppose that . Then if and only if there exist such that:
(i)
(Complementary slackness)(ii)
(iii)
These conditions are natural candidates to become the desired extension of the necessary conditions for equality constraints. They can become necessary conditions for Problem (P) if we can guarantee that at , a local solution to (P). But is a geometric optimality condition; we would prefer algebraic optimality conditions.
Proof: since
if and only if for every z satisfying
(1)
(2)
we have
(3)
(2) is equivalent to
(4)
(5)
From Lemma 1.17, (3) holds for all z satisfying (1), (4), (5) if and only if there exist such that
Let be the rows of A and in reference to Lemma 1.17.
Let for , and conclude that if and only if (i) – (iii) hold. QED.
Example 1-27 Continued: We found and .
e.g.
So there are no that satisfy (i) – (iii) even though is the optimal solution.
Example 1-28: Min
s.t.
Let . .
e.g.
No exist that satisfy (i) – (iii) at .
Let;
The graph below illustrates this scenario (not including the line ).
; so there exist such that (i) – (iii) are satisfied.
In the graph below, note that is optimal and that and .
Recall that we’ve said (i) – (iii) can become necessary conditions for a local optimal point to Problem (P) if we can guarantee at the local optimal point . It is possible to derive “weak” necessary conditions for optimality without requiring at the solution by introducing a multiplier for the objective function.
Definition 1.4.6 Define the Weak Langrangian associated with Problem (P) as the following:
Lemma 1.19 Theory of the Alternative:
Let be a matrix. Then either there exist such that
(1)
Or there exist where and such that
(2)
But never both.
Example 1-29: The figure below illustrates Lemma 1.19 depicting aias the rows of the matrix A with m = 3 and n = 2.
Proof of Lemma 1.19:
Suppose there exist x and u such that (1) and (2) are satisfied; the following must be true:
and #
Suppose now there does not exist x satisfying (1). This means that for any we cannot find a negative number w satisfying the following:
Letting where and invoking Farka’s Lemma (1.17), we conclude that there exist such that
Therefore, u solves (2). QED.
Theorem 1.20 Fritz-John Conditions
Suppose that f, gi, i = 1,…,m, hj, j = 1,…,p have continuous first partial derivatives on an open set containing X. If is a solution to Problem (P), then there exists and such that the following hold:
(iv)
(v)
(vi)
Proof: (only for ≥ constraints; proof for equality constraints is similar)
Modified Problem: min
s.t.
Must proof existence of a to show the following three conditions:
(iv)’
(v)’
(vi)’
Case 1: if , then . Choose .
Then (iv)’ – (vi)’ hold
Case 2: Suppose . Then for every satisfying
(1)
Then we cannot have the following
(2)
This is true since if there exist z satisfying (1), then there exists such that if satisfies (i.e. x is feasible). Also, since (2) holds, there exists such that for .
Let , then for , , and contradicting that is a local minimum. Thus the system (1) and (2) has no solution.
By Lemma 1.19 there exists a , such that
.
Letting for , we get
and . QED.
Example 1-30: Min
s.t.
At satisfies the Fritz-John conditions.
Example 1-30 illustrates the weaknesses of the Fritz-John conditions. Substituting in , conditions (iv) – (vi) are satisfied at (1,0) for any differentiable objective function whether it has a local minimum at that point or not.
Remark: Problem (P) includes both inequality ( ≥ ) and equality ( = ) constraints because equality-inequality problems can be converted to problems having only one type of constraint but this increases the number of variables or the number of constraints (which can weaken the results).
If we rewrite each equality ( = ) constraint in Problem (P)
Then choose , then (iv) – (vi) are satisfied for every feasible x.
1