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

Earth Systems Seminar, por Ricardo Pereira (GeoBioTec - NOVA FCT, IDL).

Seminário de Investigação Operacional, por Damján Tárkány (Joint work with Luis Gouveia).

Os portadores de Trissomia 21 têm lugar no ensino superior

A participação no debate é gratuita, mediante inscrição prévia.

Seminário Doutoral III (Doutoramento em Biologia), por Sofia Mendes.

Nebulosa de Orionte no infravermelho

Serão abordadas todas as áreas da Astronomia e Astrofísica, de forma ligeira mas cientificamente suportada, havendo também uma breve introdução ao uso prático de telescópios.

Chegou o momento ideal para realizar podas em verde e de frutificação - uma técnica fundamental para estimular uma produção abundante de frutos e manter as árvores equilibradas e saudáveis! Ao contrário das podas de inverno, estas intervenções mais suaves permitem orientar o crescimento e favorecer a frutificação ainda no mesmo ano.

Título/data/local do evento e fotografia do mar

Quais são os conceitos-chave para enfrentar os atuais desafios marinhos e costeiros? 

Título do evento, sobre imagem abstrata em tons de azul e laranja

Muitos parabéns aos investigadores de CIÊNCIAS premiados!

Daniel da Silva Distinguished Lecture, por Jean-Pierre Bourguignon (IHÉS).

Representação de programação R

This course aims at providing students with basic knowledge of R programming, allowing them to manipulate and visualize data with R.

Título "Jornadas Científicas ULisboa" e composição com os logótipos da ULisboa e da União Europeia

A edição de 2025 das Jornadas é dedicada ao tema "Universidade de Lisboa no Espaço Europeu de Investigação: Construir Carreiras Académicas Atrativas, Fortalecer Instituições".

The conference focuses on "Algebra and its role in Computer Science", with special emphasis on the areas of study related to the work of M. V. Volkov, such as semigroups and automata.

Título "Hoje quem manda sou eu" e mapa de Portugal

Palestra por Jorge Buescu (Ciências ULisboa), no âmbito da iniciativa "Hoje quem manda sou eu", promovida pela Ciência Viva.

Luz a atravessar nuvens

O concerto integra o programa Música na Universidade de Lisboa, numa parceria com a Orquestra Académica da Universidade de Lisboa, naquele que é o Concerto Final de Temporada.

Workshop organizado pelo CEMS.UL - Centro de Estudos Matemáticos e pelo CAMGDS - Centro de Análise Matemática, Geometria e Sistemas Dinâmicos.

Título/data/local do evento e fotografia do espaço

How far will you go? The IA Summer Program 2025 is your launchpad to the Universe!

Representação de programação R

This course aims at providing students with statistical knowledge and tools to manipulate, analyse and visualise biological data with R. Introduction to modeling, simulations and Bayesian statistics.

Logótipo do Verão na ULisboa, sobre um fundo azul

Uma iniciativa da Universidade de Lisboa que proporciona a oportunidade única, aos alunos do 8.º ao 12.º anos de estudo, ou que tenham já concluído o 12.º ano, de ficar a conhecer e experimentar o ritmo e o espírito da vida académica na Universidade.

Computability in Europe (CiE) is an interdisciplinary series of international conferences organised by the Association Computability in Europe (ACiE).

Título/data do evento e vários objetos museológicos

This course aims to provide an updated vision of the potential of museum collections for biodiversity research. More specifically, aims to present case studies on the value of museums and the use of collections and specimens in the 21st century, using new technologies and analytical methods.

Horta Solar

E se fosse possível experimentar um curso universitário antes de concorrer ao ensino superior? Agora já é!

Águas subterrâneas

Curso acreditado para efeitos de progressão na carreira dos professores na dimensão cientifico-pedagógica dos grupos 420 e 520.

Título e datas do programa de estágios

Ready to explore research up close?

A 10.ª edição do Ser Cientista realiza-se entre 21 e 25 de julho - vem investigar connosco!

Pormenor de lâmpada

Candidaturas a decorrer de 01 a 30 de setembro.

Páginas