Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 1 h ago
PreprintarXiv licencearXiv

On the Complexity of Finding Fixed Points for Set-Valued Contractions

  • Emmanouil-Vasileios Vlatakis-Gkaragkounis
  • Pucheng Xiong
Open at sourcePDFDOICite

Abstract

In this paper, we study the computational complexity of finding fixed points for set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem: Projected-Nadler, and prove that it is CLS-complete by showing its equivalence to Continuous-LocalOpt. We then establish a stronger converse for Nadler's fixed point theorem that can be applied as a tool to analyze the convergence rate of set-valued basic iteration procedure. Finally, we reduce large-margin triplet stationarity problem to Projected-Nadler. Together with its CLS-hardness introduced in [arXiv:2509.16898], this yields CLS-completeness of large-margin triplet stationarity.

Related

  1. The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
    Guy Kornowski
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
    Huanjian Zhou, Taiji Suzuki
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
    Yanpeng Liang, Luo Luo
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Fixed Point for Some Polynomial Contractions
    Doha A. Abulhamil, Saud M. Alsulami
    MathematicsPeer-reviewedCC BY 4.0Geometry & topologyCrossref
  5. Finding New Limit Points of Mahler Measure by Methods of Missing Data Restoration
    Jean-Marc Sac-Épée, Souad El Otmani, Armand Maul +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{vlatakisgkaragkounis2026complexity,
  title = {{On the Complexity of Finding Fixed Points for Set-Valued Contractions}},
  author = {Emmanouil-Vasileios Vlatakis-Gkaragkounis and Pucheng Xiong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.14101},
  eprint = {2609.14101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14101},
}
RIS
TY  - UNPB
TI  - On the Complexity of Finding Fixed Points for Set-Valued Contractions
AU  - Emmanouil-Vasileios Vlatakis-Gkaragkounis
AU  - Pucheng Xiong
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.14101
UR  - https://arxiv.org/abs/2609.14101
AB  - In this paper, we study the computational complexity of finding fixed points for set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem: Projected-Nadler, and prove that it is CLS-complete by showing its equivalence to Continuous-LocalOpt. We then establish a stronger converse for Nadler's fixed point theorem that can be applied as a tool to analyze the convergence rate of set-valued basic iteration procedure. Finally, we reduce large-margin triplet stationarity problem to Projected-Nadler. Together with its CLS-hardness introduced in [arXiv:2509.16898], this yields CLS-completeness of large-margin triplet stationarity.
ER  -