FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
Unconstrained nonlinear programming: problem with the proof of the Global Convergence Theorem
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
lucas
science forum beginner


Joined: 03 Feb 2005
Posts: 7

PostPosted: Thu Jul 06, 2006 6:24 pm    Post subject: Unconstrained nonlinear programming: problem with the proof of the Global Convergence Theorem Reply with 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 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!!!
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

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

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



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^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
Back to top
lucas
science forum beginner


Joined: 03 Feb 2005
Posts: 7

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

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 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!
Smile
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Mon Jul 16, 2018 7:46 pm | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts help on problem brb003 Math 0 Mon Aug 28, 2006 3:31 am
No new posts fraction problem mikerule Research 0 Thu Aug 24, 2006 5:10 am
No new posts Mod computer problem William Elliot Math 4 Fri Jul 21, 2006 12:07 pm
No new posts Divine apparitions in the tethered goat problem? jpalmour@gmail.com Math 6 Thu Jul 20, 2006 8:26 pm
No new posts possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0192s ][ Queries: 16 (0.0044s) ][ GZIP on - Debug on ]