Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Circumscribed ellipsoid algorithm for fixed-point problems


Authors: C. Boonyasiriwat, K. Sikorski and C. Tsay
Journal: Math. Comp. 80 (2011), 1703-1723
MSC (2010): Primary 47H10, 65H10; Secondary 65Y20, 68Q25
Published electronically: November 30, 2010
MathSciNet review: 2785475
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new implementation of the almost optimal Circumscribed Ellipsoid (CE) Algorithm for approximating fixed points of nonexpanding functions, as well as of functions that may be globally expanding, however, are nonexpanding/contracting in the direction of fixed points. Our algorithm is based only on function values, i.e., it does not require computing derivatives of any order. We utilize the absolute and residual termination criteria with respect to the second norm. The numerical results confirm that the CE algorithm is much more efficient than the simple iteration algorithm whenever the Lipschitz constant is close to 1. We also compare it with the Newton-Raphson method. In some tests the Newton-Raphson method is more efficient than the CE method, especially when the problem size is large. However, the CE algorithm is an excellent method for low dimensional functions with discontinuities and/or low regularity. Our implementation can be downloaded from http://www.cs.utah.edu/$ \sim$sikorski/cea.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 47H10, 65H10, 65Y20, 68Q25

Retrieve articles in all journals with MSC (2010): 47H10, 65H10, 65Y20, 68Q25


Additional Information

C. Boonyasiriwat
Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
Email: chaiwoot@yahoo.com

K. Sikorski
Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
Email: sikorski@cs.utah.edu

C. Tsay
Affiliation: Computer Science and Information Management, Providence University 200 Chung-chi Rd., Shalu Taichung 43301, Taiwan
Email: cwtsay@pu.edu.tw

DOI: https://doi.org/10.1090/S0025-5718-2010-02443-3
Received by editor(s): October 3, 2008
Received by editor(s) in revised form: April 23, 2010
Published electronically: November 30, 2010
Dedicated: We dedicate this paper to the memory of Leonid Khachiyan, collaborator and friend, who introduced the circumscribed ellipsoid algorithm as the first way of solving linear programming problems in polynomial time.
Article copyright: © Copyright 2010 American Mathematical Society