Some Optimization book says that the steepest descent algorithm has linear rate of convergence, and writes (|x_{n+1}-L| = O(|x_n-L|)). I was wondering if the usage of big O notation here expands the meaning of linear rate of convergence?

From the perspective of real analysis, we have from Wikipedia about the big O notation

(f(x) = O(g(x))) if and only if there exists a positive real number (M) and a real number (x_0) such that (|f(x)| le ; M |g(x)| ext{ for all }x>x_0).

Also from Wikipedia about rates of convergence of a real sequence

Suppose that the sequence ({x_k}) converges to the number (L). We say that this sequence converges linearly to (L), if there exists a number (μ ∈ (0, 1)) such that (lim_{k o infty} frac{|x_{k+1}-L|}{|x_k-L|} = μ).

If the sequences converges, and

  • (μ = 0), then the sequence is said to converge superlinearly.
  • (μ = 1), then the sequence is said to converge sublinearly.

My understanding is that if ({x_n}) either linearly, superlinearly or sublinearly converges to (L), then (|x_{n+1}-L| = O(|x_n-L|)). This is based on their definitions and viewing ({ x_{n+1}-L }) and ({ x_n-L }) as functions of (n). Note that the part after "then" may not imply the part after "if", since (μ) may lie outside of ([0,1]) and ({x_n}) may not converge. For more detail, please see this thread.

So I suspect the big O notation used in the book mentioned at the beginning does not mean the same as linear rate of convergence, but expands the latter.

Or maybe the optimization community has different meanings for the same notations in this matter but I am not aware of it?

Thanks and regards!

asked 16 Feb '12, 20:36

Timo's gravatar image

Timo
5925
accept rate: 0%

edited 16 Feb '12, 22:27

Having seen @Brian's comment I'd better edit my answer.

(16 Feb '12, 20:55) Marco Luebbecke ♦

Thanks, Marco! Do you mean that the big O notation has different meaning in optimization community from pure mathematics? In real analysis, the big O notation does not imply convergence, and even when the sequence converges, the big O notation does not assume the rate μ to be in (0, 1), but allow it to be any positive number less than infinity. For how people doing pure mathematics use the big O notation, please see http://math.stackexchange.com/questions/109686/rate-of-convergence-of-a-sequence-in-mathbbr-and-big-o-notation. Thanks!

(16 Feb '12, 21:05) Timo

To your edit: Regarding "linear convergence implies sublinear convergence", according to Wikipedia (the third link and quote), linear convergence requires μ to be in (0, 1), and sublinear convergence requires μ to be in 1, so I think there is no overlapping between the two cases, and neither implies the other.

(16 Feb '12, 21:08) Timo
1

Many authors use the convention that if (mu < 1), the sequence converges linearly, and if (mu=0) the convergence is superlinear. With that definition, any sequence that convergences superlinearly also converges linearly.

It is certainly true that if the sequence converges linearly, then

[ |x_{n+1} - L| = O(|x_{n} - L|) ]

However, the converse is not true.

The particular quote you've linked to isn't an incorrect statement about this, since the author isn't making the converse statement.

(16 Feb '12, 22:37) Brian Borchers

@Brian: Thanks! (1) Regarding the quote from the book, I think it is imprecise in the sense that the big O notation can mean linear, superlinear and sublinear convergence as defined in Wiki. (2) As you mentioned that "many authors use the convention that if (mu < 1), the sequence converges linearly, and if (mu=0) the convergence is superlinear", I wonder if they are from some references? In Wiki, it cites numerical computation books as its references.

(16 Feb '12, 22:51) Timo

With respect to (1), you're missing my point. The author never made the converse that if (|x_{n+1} - L|=O(|x_n - L|)) then the convergence is linear. Rather, the author said that if the sequence is linearly convergent, then (|x_n+1 - L| = O(|x_n - L|)). This is a completely correct statement.

You seem to be having trouble recognizing that "If A then B" is a different statement than "If B then A" or perhaps you're misreading "If A then B" in the book as "If B then A." Is English your native language?

(16 Feb '12, 23:14) Brian Borchers

@Brian: No. I believe I didn't miss your point. I knew clearly what you said.

(16 Feb '12, 23:23) Timo
showing 5 of 7 show 2 more comments
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×5
×4

Asked: 16 Feb '12, 20:36

Seen: 4,084 times

Last updated: 17 Feb '12, 04:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.