Körnlein, Daniel (2016):
Quantitative Analysis of Iterative Algorithms in Fixed Point Theory and Convex Optimization.
Darmstadt, Technische Universität Darmstadt, [OnlineEdition: http://tuprints.ulb.tudarmstadt.de/5485],
[Ph.D. Thesis]
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 nonconstructive reasoning in the form of ideal principles and classical logic, socalled 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 prooftheoretic 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  
Title:  Quantitative Analysis of Iterative Algorithms in Fixed Point Theory and Convex Optimization  
Language:  English  
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 nonconstructive reasoning in the form of ideal principles and classical logic, socalled 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 prooftheoretic 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. 

Place of Publication:  Darmstadt  
Uncontrolled Keywords:  proof mining, proof theory, fixed point theory  
Divisions:  04 Department of Mathematics > Logic 04 Department of Mathematics 

Date Deposited:  29 May 2016 19:55  
Official URL:  http://tuprints.ulb.tudarmstadt.de/5485  
URN:  urn:nbn:de:tudatuprints54859  
Referees:  Kohlenbach, Prof. Dr. Ulrich and Lopez Acedo, Prof. Dr. Genaro and Streicher, Prof. Dr. Thomas  
Refereed / Verteidigung / mdl. Prüfung:  12 April 2016  
Alternative Abstract: 


Export:  
Suche nach Titel in:  TUfind oder in Google 
Send an inquiry 
Options (only for editors)
View Item 