No Cover Image

Journal article 526 views 29 downloads

Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees

Eike Neumann

Logical Methods in Computer Science, Volume: 11, Issue: 4

Swansea University Author: Eike Neumann

  • 60138_VoR.pdf

    PDF | Version of Record

    Copyright: E. Neumann. This work is licensed under the Creative Commons Attribution-NoDerivs License

    Download (487.88KB)

Check full text

DOI (Published version): 10.2168/lmcs-11(4:20)2015

Abstract

We study the computational difficulty of the problem of finding fixed points of nonexpansive mappings in uniformly convex Banach spaces. We show that the fixed point sets of computable nonexpansive self-maps of a nonempty, computably weakly closed, convex and bounded subset of a computable real Hilb...

Full description

Published in: Logical Methods in Computer Science
ISSN: 1860-5974
Published: Centre pour la Communication Scientifique Directe (CCSD) 2015
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa60138
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2022-06-07T12:06:59Z
last_indexed 2023-01-11T14:41:54Z
id cronfa60138
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-07-07T11:24:49.5419562</datestamp><bib-version>v2</bib-version><id>60138</id><entry>2022-06-07</entry><title>Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-07</date><deptcode>SCS</deptcode><abstract>We study the computational difficulty of the problem of finding fixed points of nonexpansive mappings in uniformly convex Banach spaces. We show that the fixed point sets of computable nonexpansive self-maps of a nonempty, computably weakly closed, convex and bounded subset of a computable real Hilbert space are precisely the nonempty, co-r.e. weakly closed, convex subsets of the domain. A uniform version of this result allows us to determine the Weihrauch degree of the Browder-Goehde-Kirk theorem in computable real Hilbert space: it is equivalent to a closed choice principle, which receives as input a closed, convex and bounded set via negative information in the weak topology and outputs a point in the set, represented in the strong topology. While in finite dimensional uniformly convex Banach spaces, computable nonexpansive mappings always have computable fixed points, on the unit ball in infinite-dimensional separable Hilbert space the Browder-Goehde-Kirk theorem becomes Weihrauch-equivalent to the limit operator, and on the Hilbert cube it is equivalent to Weak Koenig's Lemma. In particular, computable nonexpansive mappings may not have any computable fixed points in infinite dimension. We also study the computational difficulty of the problem of finding rates of convergence for a large class of fixed point iterations, which generalise both Halpern- and Mann-iterations, and prove that the problem of finding rates of convergence already on the unit interval is equivalent to the limit operator.</abstract><type>Journal Article</type><journal>Logical Methods in Computer Science</journal><volume>11</volume><journalNumber>4</journalNumber><paginationStart/><paginationEnd/><publisher>Centre pour la Communication Scientifique Directe (CCSD)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic>1860-5974</issnElectronic><keywords>Mathematics - Logic, Computer Science - Logic in Computer Science</keywords><publishedDay>29</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2015</publishedYear><publishedDate>2015-12-29</publishedDate><doi>10.2168/lmcs-11(4:20)2015</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2022-07-07T11:24:49.5419562</lastEdited><Created>2022-06-07T12:59:36.6110216</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Eike</firstname><surname>Neumann</surname><order>1</order></author></authors><documents><document><filename>60138__24472__e313b591b678422c8b855aabb4a91f2c.pdf</filename><originalFilename>60138_VoR.pdf</originalFilename><uploaded>2022-07-07T11:23:37.0894395</uploaded><type>Output</type><contentLength>499593</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>Copyright: E. Neumann. This work is licensed under the Creative Commons Attribution-NoDerivs License</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>http://creativecommons.org/licenses/by-nd/2.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2022-07-07T11:24:49.5419562 v2 60138 2022-06-07 Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-06-07 SCS We study the computational difficulty of the problem of finding fixed points of nonexpansive mappings in uniformly convex Banach spaces. We show that the fixed point sets of computable nonexpansive self-maps of a nonempty, computably weakly closed, convex and bounded subset of a computable real Hilbert space are precisely the nonempty, co-r.e. weakly closed, convex subsets of the domain. A uniform version of this result allows us to determine the Weihrauch degree of the Browder-Goehde-Kirk theorem in computable real Hilbert space: it is equivalent to a closed choice principle, which receives as input a closed, convex and bounded set via negative information in the weak topology and outputs a point in the set, represented in the strong topology. While in finite dimensional uniformly convex Banach spaces, computable nonexpansive mappings always have computable fixed points, on the unit ball in infinite-dimensional separable Hilbert space the Browder-Goehde-Kirk theorem becomes Weihrauch-equivalent to the limit operator, and on the Hilbert cube it is equivalent to Weak Koenig's Lemma. In particular, computable nonexpansive mappings may not have any computable fixed points in infinite dimension. We also study the computational difficulty of the problem of finding rates of convergence for a large class of fixed point iterations, which generalise both Halpern- and Mann-iterations, and prove that the problem of finding rates of convergence already on the unit interval is equivalent to the limit operator. Journal Article Logical Methods in Computer Science 11 4 Centre pour la Communication Scientifique Directe (CCSD) 1860-5974 Mathematics - Logic, Computer Science - Logic in Computer Science 29 12 2015 2015-12-29 10.2168/lmcs-11(4:20)2015 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2022-07-07T11:24:49.5419562 2022-06-07T12:59:36.6110216 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 1 60138__24472__e313b591b678422c8b855aabb4a91f2c.pdf 60138_VoR.pdf 2022-07-07T11:23:37.0894395 Output 499593 application/pdf Version of Record true Copyright: E. Neumann. This work is licensed under the Creative Commons Attribution-NoDerivs License true eng http://creativecommons.org/licenses/by-nd/2.0/
title Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
spellingShingle Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
Eike Neumann
title_short Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
title_full Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
title_fullStr Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
title_full_unstemmed Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
title_sort Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
author Eike Neumann
author2 Eike Neumann
format Journal article
container_title Logical Methods in Computer Science
container_volume 11
container_issue 4
publishDate 2015
institution Swansea University
issn 1860-5974
doi_str_mv 10.2168/lmcs-11(4:20)2015
publisher Centre pour la Communication Scientifique Directe (CCSD)
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description We study the computational difficulty of the problem of finding fixed points of nonexpansive mappings in uniformly convex Banach spaces. We show that the fixed point sets of computable nonexpansive self-maps of a nonempty, computably weakly closed, convex and bounded subset of a computable real Hilbert space are precisely the nonempty, co-r.e. weakly closed, convex subsets of the domain. A uniform version of this result allows us to determine the Weihrauch degree of the Browder-Goehde-Kirk theorem in computable real Hilbert space: it is equivalent to a closed choice principle, which receives as input a closed, convex and bounded set via negative information in the weak topology and outputs a point in the set, represented in the strong topology. While in finite dimensional uniformly convex Banach spaces, computable nonexpansive mappings always have computable fixed points, on the unit ball in infinite-dimensional separable Hilbert space the Browder-Goehde-Kirk theorem becomes Weihrauch-equivalent to the limit operator, and on the Hilbert cube it is equivalent to Weak Koenig's Lemma. In particular, computable nonexpansive mappings may not have any computable fixed points in infinite dimension. We also study the computational difficulty of the problem of finding rates of convergence for a large class of fixed point iterations, which generalise both Halpern- and Mann-iterations, and prove that the problem of finding rates of convergence already on the unit interval is equivalent to the limit operator.
published_date 2015-12-29T04:18:00Z
_version_ 1763754199142629376
score 11.013371

Similar Items