Author 
Message 
lucas science forum beginner
Joined: 03 Feb 2005
Posts: 7

Posted: Thu Jul 06, 2006 6:24 pm Post subject:
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 realvalued
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 pointtoset 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!!! 

Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Mon Jul 10, 2006 3:45 pm Post subject:
Re: Unconstrained nonlinear programming: problem with the proof of the Global Convergence Theorem



In article <1152210270.825818.173270@75g2000cwc.googlegroups.com>,
kingpin@freemail.it writes:
Quote:  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 realvalued
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 pointtoset 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
Quote:  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, ...
Quote:  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
Quote:  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
Quote:  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
Quote:  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
Quote: 
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^21) 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 

Back to top 


lucas science forum beginner
Joined: 03 Feb 2005
Posts: 7

Posted: Tue Jul 11, 2006 1:56 pm Post subject:
Re: Unconstrained nonlinear programming: problem with the proof of the Global Convergence Theorem



Peter Spellucci wrote:
Quote:  In article <1152210270.825818.173270@75g2000cwc.googlegroups.com>,
kingpin@freemail.it 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 realvalued
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 pointtoset 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^21) 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!


Back to top 


Google


Back to top 



The time now is Thu Feb 21, 2019 7:20 am  All times are GMT

