TU Darmstadt / ULB / TUbiblio

Quantitative Analysis of Iterative Algorithms in Fixed Point Theory and Convex Optimization

Körnlein, Daniel (2016)
Quantitative Analysis of Iterative Algorithms in Fixed Point Theory and Convex Optimization.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Abstract

The ongoing program of `proof mining' aims to extract new, quantitative information in the form of bounds and rates from prima facie noneffective proofs in mathematics. In doing so, proof mining and the thesis at hand draws a bridge between mathematics and logic, prompting a lively interaction between mathematical practice and logical theory. This thesis applies proof mining paradigms to several convergence results in fixed point theory and nonlinear optimization, resulting in new complexity information in the form of rates of convergence or rates of metastability.

A first -- yet from the proof mining perspective trivial -- example is Banach's famous fixed point theorem; The theorem itself asserts that any contraction mapping on a complete metric space possesses a unique fixed point, and that this fixed point may be approximated by means of the Picard iteration. The proof, on the other hand, exhibits the well known rate of convergence, which can be read off immediately from it. Moreover, the rate is uniform in the mapping, the underlying metric space and the starting point in that it only depends on a Lipschitz constant for the mapping in question and an upper bound on its initial displacement. In other words, for given contraction constant $q$ and positive real number $b$, the rate of convergence is valid for the class of all metric spaces, all mappings on this metric space with contraction constant $q$ and all starting points that are displaced by the operator by a distance of at most $b$.

The reason that Banach's fixed point theorem admits such a uniform rate of convergence and that its proof divulges the rate so easily has two reasons: It is constructive and convergence to the limit point is monotone. In general, however, neither is the case. It is precisely in these cases that proof mining, or rather the general logical theorems and tools behind the name, come into play.

Under vastly general conditions on the proof that admit non-constructive reasoning in the form of ideal principles and classical logic, so-called metatheorems guarantee the existence of uniform complexity information. For instance, a large part of classical analysis is covered by those metatheorems. Furthermore, the complexity information is not only guaranteed to exist, but can be extracted from the proof at hand.

The original proof is moreover transformed into a new proof of the new statement which exhibits the additional complexity information. The new proof then exhibits no trace of its proof-theoretic manipulation and is carried out without reference to any mathematical logic. This has the further advantage that the complexity bound is not only valid, but its proof is easily accessible to the experts of the respective mathematical field and can be published in the corresponding journals.

Item Type: Ph.D. Thesis
Erschienen: 2016
Creators: Körnlein, Daniel
Type of entry: Primary publication
Title: Quantitative Analysis of Iterative Algorithms in Fixed Point Theory and Convex Optimization
Language: English
Referees: Kohlenbach, Prof. Dr. Ulrich ; Lopez Acedo, Prof. Dr. Genaro ; Streicher, Prof. Dr. Thomas
Date: 2016
Place of Publication: Darmstadt
Refereed: 12 April 2016
URL / URN: http://tuprints.ulb.tu-darmstadt.de/5485
Abstract:

The ongoing program of `proof mining' aims to extract new, quantitative information in the form of bounds and rates from prima facie noneffective proofs in mathematics. In doing so, proof mining and the thesis at hand draws a bridge between mathematics and logic, prompting a lively interaction between mathematical practice and logical theory. This thesis applies proof mining paradigms to several convergence results in fixed point theory and nonlinear optimization, resulting in new complexity information in the form of rates of convergence or rates of metastability.

A first -- yet from the proof mining perspective trivial -- example is Banach's famous fixed point theorem; The theorem itself asserts that any contraction mapping on a complete metric space possesses a unique fixed point, and that this fixed point may be approximated by means of the Picard iteration. The proof, on the other hand, exhibits the well known rate of convergence, which can be read off immediately from it. Moreover, the rate is uniform in the mapping, the underlying metric space and the starting point in that it only depends on a Lipschitz constant for the mapping in question and an upper bound on its initial displacement. In other words, for given contraction constant $q$ and positive real number $b$, the rate of convergence is valid for the class of all metric spaces, all mappings on this metric space with contraction constant $q$ and all starting points that are displaced by the operator by a distance of at most $b$.

The reason that Banach's fixed point theorem admits such a uniform rate of convergence and that its proof divulges the rate so easily has two reasons: It is constructive and convergence to the limit point is monotone. In general, however, neither is the case. It is precisely in these cases that proof mining, or rather the general logical theorems and tools behind the name, come into play.

Under vastly general conditions on the proof that admit non-constructive reasoning in the form of ideal principles and classical logic, so-called metatheorems guarantee the existence of uniform complexity information. For instance, a large part of classical analysis is covered by those metatheorems. Furthermore, the complexity information is not only guaranteed to exist, but can be extracted from the proof at hand.

The original proof is moreover transformed into a new proof of the new statement which exhibits the additional complexity information. The new proof then exhibits no trace of its proof-theoretic manipulation and is carried out without reference to any mathematical logic. This has the further advantage that the complexity bound is not only valid, but its proof is easily accessible to the experts of the respective mathematical field and can be published in the corresponding journals.

Alternative Abstract:
Alternative abstract Language

The ongoing program of `proof mining' aims to extract new, quantitative information in the form of bounds and rates from prima facie noneffective proofs in mathematics. In doing so, proof mining and the thesis at hand draws a bridge between mathematics and logic, prompting a lively interaction between mathematical practice and logical theory. This thesis applies proof mining paradigms to several convergence results in fixed point theory and nonlinear optimization, resulting in new complexity information in the form of rates of convergence or rates of metastability.

A first -- yet from the proof mining perspective trivial -- example is Banach's famous fixed point theorem; The theorem itself asserts that any contraction mapping on a complete metric space possesses a unique fixed point, and that this fixed point may be approximated by means of the Picard iteration. The proof, on the other hand, exhibits the well known rate of convergence, which can be read off immediately from it. Moreover, the rate is uniform in the mapping, the underlying metric space and the starting point in that it only depends on a Lipschitz constant for the mapping in question and an upper bound on its initial displacement. In other words, for given contraction constant $q$ and positive real number $b$, the rate of convergence is valid for the class of all metric spaces, all mappings on this metric space with contraction constant $q$ and all starting points that are displaced by the operator by a distance of at most $b$.

The reason that Banach's fixed point theorem admits such a uniform rate of convergence and that its proof divulges the rate so easily has two reasons: It is constructive and convergence to the limit point is monotone. In general, however, neither is the case. It is precisely in these cases that proof mining, or rather the general logical theorems and tools behind the name, come into play.

Under vastly general conditions on the proof that admit non-constructive reasoning in the form of ideal principles and classical logic, so-called metatheorems guarantee the existence of uniform complexity information. For instance, a large part of classical analysis is covered by those metatheorems. Furthermore, the complexity information is not only guaranteed to exist, but can be extracted from the proof at hand.

The original proof is moreover transformed into a new proof of the new statement which exhibits the additional complexity information. The new proof then exhibits no trace of its proof-theoretic manipulation and is carried out without reference to any mathematical logic. This has the further advantage that the complexity bound is not only valid, but its proof is easily accessible to the experts of the respective mathematical field and can be published in the corresponding journals.

English
Uncontrolled Keywords: proof mining, proof theory, fixed point theory
URN: urn:nbn:de:tuda-tuprints-54859
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics > Logic
04 Department of Mathematics
Date Deposited: 29 May 2016 19:55
Last Modified: 29 May 2016 19:55
PPN:
Referees: Kohlenbach, Prof. Dr. Ulrich ; Lopez Acedo, Prof. Dr. Genaro ; Streicher, Prof. Dr. Thomas
Refereed / Verteidigung / mdl. Prüfung: 12 April 2016
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details