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
titulo e data do evento

A major vehicle to bring together the national Physical Chemistry community.

Seminário do Laboratório de Instrumentação e Física Experimental de Partículas, por Pedro Cruz (Northeastern University).

Logótipo do EVM 2024

Por Giosuè Muratore (DM Ciências ULisboa e CMAFcIO).

Logótipo do EVM 2024

Por Pedro Duarte (DM Ciências ULisboa, CMAFcIO).

Título do programa, sobre mosaico de fotografias de jovens cientistas

As candidaturas encontram-se encerradas. Obrigada aos quase 80 candidatos/as!

Fotografia de ilha

Seminários Doutorais no âmbito da disciplina de Projeto de Investigação (Doutoramento em Ciências do Mar).

Logótipo do EVM 2024

Por Maria Manuel Torres (DM Ciências ULisboa e CMAFcIO).

Seminário do Centro de Matemática, Aplicações Fundamentais e Investigação Operacional, por Baptiste Claustre (aluno ENS Lyon, estagiário CMAFcIO).

Logótipo do EVM 2024

Por: Jorge Buescu (DM Ciências ULisboa e CMAFcIO).

Titulo e data do evento, com imagem de ponte sobre o tejo

Um evento organizado no âmbito da Ação COST EURO-MIC, de cujo Comitê de Gestão Elisabete Silva, líder do Bioactive and Multifunctional Materials Lab do BioISI, faz parte.

Logótipo do EVM 2024

Por Jean-Baptiste Casteras (DM Ciências ULisboa e CMAFcIO).

Chegou a hora: os participantes do Programa Ser Cientista vão apresentar os projetos que desenvolveram ao longo de uma semana, acompanhados por docentes e investigadores de CIÊNCIAS. E todos podem assistir!

Imagem do evento

Extended enrolement date until July 12th.

Logótipo do evento, sobre um fundo branco

Um evento de reunião da comunidade nacional nas diversas vertentes da informática, com a ambição de ser o fórum de eleição para a divulgação, discussão e reconhecimento de trabalhos científicos.

Are you ready for this year's edition?

Imagem do evento - título, local e data do evento

Investigação Ecológica ao Serviço da Conservação

A leading venue for presenting and discussing the latest research, industrial practice and innovations in dependable and secure computing.