Search   Memberlist   Usergroups
 Page 1 of 1 [3 Posts]
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 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.

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

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [3 Posts]
 The time now is Thu Feb 21, 2019 7:20 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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