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


Peter Spellucci wrote:
In article <1152210270.825818.173270@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
kingpin@xxxxxxxxxxx writes:
>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).
>

this is indeed something strange writing, although correct:
we know that the whole sequence is contained in a compact subset of X and
Z is continuous on X, hence it is bounded from below on this compact subset
and by assumption on the construction of {x_k} k=0,1,2,3,...
Z(x_k) monotonically decreasing. But a monotonically decreasing sequence
which is bounded from below is convergent. hence
Z(x_k) converges monotonically to some value V.
(this says nothing about the convergence of the sequence {x_k}.
but of course, for any convergent subsequence of the total sequence
you must have lim_{k in K} Z(x_k) =V



>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...).

he means indeed the successor of x_k for k in K:
say K={3,7,16,89, }
then he means x_4, x_8, x_17, ...


> 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?).
you forgot that A is a point to set mapping and that the solution set can
even be a continuum . no regularity assumptions have been made so far
beyong closedness of A and the continuity of Z


>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...).
since the whole sequence is compact, also this new subsequence is compact
and hence has a convergent subsequence


>Thus since A is closed at x it follows that x' is in A(x).
since x_{k+1} = A(x_k), k=1,2,3,...

this follows directly from the definition of closedness


>But from above, Z(x') = Z(x) wich contradicts the fact that Z is a
>descent function.
>
>qed.


now, if you assume that x is not in G, we must have Z(x') < Z(x)=V .
again by the assumptions on the properties of Z


hth
peter

>
>
>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!!!
>
as an example for a problem with a solution set, think about
this

f(x1,x2)= 0 if x1^2+x2^2 <=1
= (x1^2+x2^2-1) if x1^2+x2^2>1

x1_k = (1+1/2^k)*cos(k)
x2_k = (1+1/2^k)*sin(k)

f(x)=Z(x).
G={x: f(x)=0}

hth
peter

Hi peter,
thank you for your reply. I will read your post later...know i am busy!
:)

.

Relevant Pages