Efficient Hybrid Algorithms for Finding Zeros of Convex Functions

✍ Scribed by Florian A. Potra

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 533 KB
• Volume: 10
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1994.1009

✦ Synopsis

We consider two hybrid algorithms for finding an (\varepsilon)-approximation of a root of a convex real function that is twice differentiable and satisfies a certain growth condition on the intervial ([0, R]). The first algorithm combines a binary search procedure with Newton's method. The binary search produces an interval contained in the region of quadratic convergence of Newton's method. The computational cost of the binary search, as well as the computational cost of Newton's method, is of order (O(\log \log (R / \varepsilon))). The second algorithm combines a binary search with the secant method in a similar fashion. This results in a lower overall computational cost when the cost of evaluating the derivative is more than 44042 of the cost of evaluating the function. Our results generalize some recent results of Ye. 1994 Academic Press, Inc.