1
$\begingroup$

I need to provide computational complexity for the algorithms in my work. One of the algorithms I have used is Golden Section method for line search. I took a look at "Nonlinear Programming" book by Bertsekas, but it did not mention the computation complexity. I have found from a paper which also has used Golden Section method, that the computation complexity is O(log(1/epsilon)), but I want to find a book or an appropriate reference for that, to cite in my work. Do you know any book or like that which has provided this?

Thanks in advance.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ See Luenberger, D. G. "Linear and nonlinear programming." p.200: books.google.com.br/books?id=QY9BjisUT1gC&pg=PA200 $\endgroup$
    – Tadashi
    Commented Jan 20, 2015 at 18:27
  • $\begingroup$ Thanks for your comment, but how is it possible to show that the computation complexity is O(log(1/epsilon))? $\endgroup$
    – Cror2014
    Commented Jan 20, 2015 at 19:02
  • 1
    $\begingroup$ The computational complexity here is not referring to arithmetic complexity but rather oracle complexity, so that the golden section method, which converges to an $\epsilon$-accurate solution at a linear rate (also known as geometric / exponential convergence in numerical literature), will make $O(\log (1 / \epsilon) )$ calls to the oracle (to compute the value of $f(x)$) --- thus @Shamisen's pointer is sufficient. $\endgroup$
    – Suvrit
    Commented Jan 20, 2015 at 19:17
  • $\begingroup$ Thanks for your comment. Could you please let me know of any reference which shows/proves this? $\endgroup$
    – Cror2014
    Commented Jan 20, 2015 at 19:20
  • $\begingroup$ Can you give me the link to the paper that you have read $\endgroup$
    – Tuong Nguyen Minh
    Commented Dec 2, 2020 at 11:14

1 Answer 1

Reset to default
0
$\begingroup$

See E. Bertolazzi's Lecture notes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer, but how is it possible to show that the computation complexity is O(log(1/epsilon))? $\endgroup$
    – Cror2014
    Commented Jan 20, 2015 at 19:03
  • $\begingroup$ The proof is in the notes. $\endgroup$
    – Igor Rivin
    Commented Jan 20, 2015 at 20:35
  • $\begingroup$ You're right. I was making a mistake in proving it. $\endgroup$
    – Cror2014
    Commented Jan 20, 2015 at 21:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .