Unconstrained nonlinear programming: problem with the proof of the Global Convergence Theorem

Hi,

i'am studying methods for unconstrained nonlinear programming. The book
of reference is that of Luenberger "Linear and
Nonlinear Programming". I have a problem with the proof of the theorem
of Global Convergence. I present some of the
concept that are necessary to understand the theorem. I hope that
someone out there can clarify to me the proof!!! :)

Def1
The book first define an "algorithm" A as a mapping defined on a set X
that assign to every point of X a subset of X.

Def2
Than it follows the definition of "descent function": let G be a subset
of X and A an algorithm on X. A continuous real-valued
function Z on X is said to be a "descent function" for G and A if it
satisfies
i) if x is not in G and y is in A(x) then Z(y) < Z(x)
ii) if x is in G and y is in A(x) then Z(y) <= Z(x).

G is called informally the solution set. The basic idea of the descent
function is that for points outside the solution set, a single
step of the algorithm yields a decrease in the value of Z.

Def3
A point-to-set mapping A from X to Y is said to be closed at x of X if
the assumptions
i) x_k -> x, x_k in X
ii) y_k -> y, y_k in A(x_k)

imply

iii) y in A(x).

The global convergence theorem says the following.


GCT Theorem

Let A be an algorithm on X, and suppose that , given x_0, the sequence
{x_k} k=0 -> inf is generated satisfying

x_k+1 is in A(x_k).

Let a solution set G (subset of X) be given, and suppose
i) all points x_k are contained in a compact set S subset of X
ii)there is a continuous function Z on X such that
a) if x is not in G then Z(y) < Z(x) for all y in A(x)
b) if x is in G then Z(y) <= Z(x) for all y in A(x)

iii) the mapping A is closed a points outside G.

Then the limit of any convergent subsequence of {x_k} is a solution.

Proof.

Suppose the convergent subsequence {x_k}, k in a subset K of N
converges to the limit x (note:we are using a subsequence
of the original sequence x_k; since S is compact there is a subsequence
of the original sequence that converges).
Since Z is continuous, it follows that for k in K, Z(x_k) -> Z(x). This
means that Z is convergent to the respect of the subsequence,
and we shall show that it is convergent with respect to the entire
sequence. By the monotonicity of Z on the sequence {x_k} we
have Z(x_k) - Z(x) >= 0 for all k. By the convergence of Z on the
subsequence, there is, for a given e > 0, an element of K, say h,
such that Z(x_k) - Z(x) < e for all k > h, with k in K.
Thus for all k > h

Z(x_k) - Z(x) = Z(x_k) - Z(x_h) + Z(x_h) - Z(x) < e,

which shows that Z(x_k) -> Z(x).

To complete the proof it is only necessary to show that x is a
solution. Suppose x is not a solution. Consider the subsequence {x_k+1}
with
k+1 in K. (note: the text write {x_k+1} K, where K is a subscript of
{x_k+1}...i don't know what he want to say here...). Since all members
of
this sequence are contained in a compact set, there is a set L, subset
of K such that {x_k+1} L converges to some limit x' (note:who says
that there is a x' different from x?). We thus have x_k->x, k in L, and
x_k+1 in A(x_k) with x_k+1 -> x', k in K (note:this is really
incomprensible
to me...). Thus since A is closed at x it follows that x' is in A(x).
But from above, Z(x') = Z(x) wich contradicts the fact that Z is a
descent function.

qed.


The first part shows that if a subsequence of the original sequence x_k
converges to x, than Z converges with respect to the original
sequence also to x. The line

Z(x_k) - Z(x) = Z(x_k) - Z(x_h) + Z(x_h) - Z(x) < e,

is not clear to me. I can say that Z(x_k) - Z(x_h) <= 0 because k > h
and Z is monotone. But i know that Z(x_h) - Z(x) is >= 0. And i can't
say
that Z(x_h) - Z(x) < e because we have assumed that *only* for k > h
(and not >= h) we have that Z(x_k) - Z(x) < e.


The second part is totally unclear to me.

Help me please!!!
i

.

Relevant Pages