Mathematical Logic Seminar

# The strange case of Dykstra’s algorithm

Videoconferência

Por Pedro Pinto (Technische Universität Darmstadt).

In this talk we discuss a 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] F. Ferreira, L. Leustean, P. Pinto, On the removal of weak compactness arguments in proof mining, Advances in Mathematics 354, 55pp, 2019.
• [2] U. Kohlenbach, P. Pinto, Fejér monotone sequences revisited, 2023 (preprint available at homepage https://www2.mathematik.tu-darmstadt.de/~pinto/).
• [3] P. Pinto, On the finitary content of Dykstra’s cyclic projections algorithm, 2023 (preprint available at homepage).

Transmissão via Zoom

16h00
CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional

Geometry and Physics Seminar, por Ángel González Prieto (Univ. Complutense, Madrid).

Seminário E3GLOBAL, por João Moreira da Silva (University of Cambridge).

Ações de formação com o objetivo de desenvolver conhecimentos que permitam aos interessados a apresentação de candidaturas a oportunidades de financiamento disponibilizadas pelos programas European Innovation Council (EIC), European Research Council (ERC) e Horizon Europe (HE).

Seminário Permanente de Filosofia das Ciências, por Silvia Di Marco (CFCUL).

Geometry and Physics Seminar, por Sean Lawton (George Mason Univ.).

Um projeto que torna acessível a um público alargado a investigação desenvolvida no Centro Interuniversitário da História da Ciência e da Tecnologia (CIUHCT).

Colóquio de Matemática, por Giulio Ruzza (Universidade de Lisboa).

Seminário do Laboratório de Instrumentação e Física Experimental de Partículas, por Rui Santos (ISEL / CFTC-UL / LIP).

Envio de propostas até 20 de junho.

Seminário "Ásia-Europa, 1500-1800", por Ricardo Roque (ICS-ULisboa), Matheus Serva Pereira (ICS-ULisboa) e José Miguel Moura Ferreira (IHC-UNL).

Um livro composto por um ensaio da historiadora e professora Ana Simões e uma banda desenhada da artista Ana Matilde Sousa, concebido como complemento à exposição E3 - Einstein, Eddington, e o Eclipse.

TWIN2PIPSA Expert Seminar, por Danny Hatters (The University of Melbourne).

An opportunity to get acquainted with some of the most promising contemporary topics in the exciting interdisciplinary area of scientific culture: the interactions of mathematics and music.

Minicurso por Heliton Tavares (Universidade Federal do Pará, Brasil).

As Jornadas Científicas 2024 da Universidade de Lisboa são dedicadas ao tema “Impacto Atual e Futuro da Inteligência Artificial no Trabalho”.

Ação de formação para docentes e investigadores de Ciências.

This year's program will cover two plenary sessions hosted by Susete Pinteus and Hugo Miranda, complemented by oral presentations, flash talks, and poster communications. Finally, a round table discussion will take place at the end of our meeting.

Seminário Helena Avelar de Astronomia e Astrologia Antiga, por Stephen Johnston (History of Science Museum, University of Oxford).

Seminário do Laboratório de Instrumentação e Física Experimental de Partículas, por Paschal Coyle (Centre de Physique de Particules de Marseille).

TWIN2PIPSA Expert Seminar, por Isabelle Landrieu (Lille University, Inserm, Institute Pasteur de Lille Research Department U1167).

Vai realizar-se em Lisboa, nos dias 28 e 29 de junho de 2024, o 37.º Encontro do Seminário Nacional de História da Matemática.

Ação de formação para docentes e investigadores de Ciências.

As candidaturas à 11.ª edição decorrem até 28 de junho.

Uma oportunidade única de conheceres e experimentares o ritmo e o espírito da vida académica!

O maior evento anual na área da ciência e da tecnologia em Portugal.