Below you can see all the talks held at the Proof Mining Seminar in the 2022-2023 season. For forthcoming talks, see the main page.
Wednesday, July 26, 2023
Pedro Pinto (TU Darmstadt)
The strange case of Dykstra’s algorithm
Abstract:
In this talk we discuss the proof mining treatment of the strong convergence of Dykstra’s algorithm.
Halpern’s iterative method is probably the most common approach to strongly approximate fixed points of nonexpansive maps. The canonical proof (pliable to many other results) establishing strong convergence of the iteration relies on a crucial use of sequential weak compactness. It is well-understood how a proof-theoretical approach allows for the elimination of the compactness arguments via bounded collection principles, thus allowing for simple quantitative data in the analysis of such proofs.
Here, we focus on a different iterative method. Generalizing the alternating projection method, Dykstra’s algorithm strongly approximates the optimal solution of the convex feasibility problem. Similarly to Halpern, the strong convergence of Dykstra’s method makes crucial uses of compactness principles substantiated by arithmetical comprehension. Yet, as the iterative schema has no connection with Halpern’s definition and the proof follows a completely different structure, it was not known whether the removal of the compactness arguments would be possible and thus, a priori, we were only guaranteed to obtain quantitative data defined by bar-recursive functionals. Strikingly, still here, it was possible to bypass the use of arithmetical comprehension and bar-recursive functionals. We will discuss the recent quantitative analysis of Dykstra’s convergence proof and explain how it was possible to avoid the compactness principles crucial in the original proof.
References:
[1] P. Pinto, On the finitary content of Dykstra’s cyclic projections algorithm. arXiv:2306.09791 [math.OC], 2023.
Wednesday, May 10, 2023
Horațiu Cheval (University of Bucharest)
The Tikhonov-Mann iteration for families of mappings
Abstract:
We present recent results from [4], in which we generalize the strongly convergent Krasnoselskii-Mann-type iteration defined by Boț and Meier in [1] for finding a common fixed point of a family of nonexpansive operators from Hilbert spaces to the abstract setting of W-hyperbolic spaces, and we compute effective rates of asymptotic regularity for it. This extends at the same time results on the Tikhonov-Mann iteration obtained recently with Ulrich Kohlenbach and Laurențiu Leuștean [2, 3] from single mappings to families of mappings.
References:
[1] R.I. Boț, and D. Meier. A strongly convergent Krasnosel’skii–Mann-type algorithm for finding a common fixed point of a countably infinite family of nonexpansive operators in Hilbert spaces. Journal of Computational and Applied Mathematics, 395:113589, 2021.
[2] H. Cheval, U. Kohlenbach, and L. Leuștean. On modified Halpern and Tikhonov-Mann iterations. Journal of Optimization Theory and Applications, 197:233–251, 2023.
[3] H. Cheval and L. Leuștean. Quadratic rates of asymptotic regularity for the Tikhonov-Mann iteration. Optimization Methods and Software, 37(6):2225–2240, 2022.
[4] H. Cheval. Rates of asymptotic regularity of the Tikhonov-Mann iteration for families of mappings. arXiv:2304.11366 [math.OC], 2023.
Wednesday, January 11, 2023
Nicholas Pischke (TU Darmstadt)
A proof-theoretic metatheorem for nonlinear semigroups generated by an accretive operator and applications
Abstract:
Already since the pioneering studies of Browder and Kato, a major tool in the study of nonlinear evolution equations has been the theory of nonlinear semigroups and their generators, with the latter in particular linking to the theory of accretive operators via nonlinear analogues of the Hille-Yosida theorem. One of the most important basic results in that context is the representation theorem due to Crandall and Liggett of the semigroup associated with the classical Cauchy problem for a given set-valued accretive operator over a Banach space. I discuss how proofs involving those semigroups can be treated in higher type arithmetic such that proof mining metatheorems are still available. This in particular requires a treatment of the dual formulation of the notion of accretivity together with other substantial extensions of the previous intensional framework for accretive operator theory. Lastly, I will illustrate the applicability of this metatheorem by presenting a particular case study for a result due to Simeon Reich on the asymptotic behavior of these semigroups.