The notion of ‘modulus of regularity’, as recently studied in [Moduli of regularity and rates of convergence for Fejér monotone sequences, 2017, Preprint], unifies a number of different concepts used in convex optimization to establish rates of convergence for Fejér monotone iterative procedures. It generalizes the notion of ‘modulus of uniqueness’ to the nonunique case. In this paper, we investigate both notions in terms of reverse mathematics and calibrate their Weihrauch complexity.
M.Beeson, Foundations of Constructive Mathematics, Springer Verlag, Berlin, Heidelberg, New York, 1985.
3.
J.Berger, D.Bridges and P.Schuster, The fan theorem and unique existence of maxima, J. Symb. Logic71 (2006), 713–720. doi:10.2178/jsl/1146620167.
4.
J.M.Borwein, G.Li and M.K.Tam, Convergence rate analysis for averaged fixed point iterations in common fixed point problems, SIAM J. Optim.27 (2017), 1–33. doi:10.1137/15M1045223.
5.
V.Brattka and G.Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symb. Logic76 (2011), 143–176. doi:10.2178/jsl/1294170993.
6.
V.Brattka, G.Gherardi and A.Marcone, The Bolzano–Weierstraß theorem is the jump of weak König’s lemma, Ann. Pure Appl. Logic163 (2012), 623–655. doi:10.1016/j.apal.2011.10.006.
7.
E.M.Briseid, Logical aspects of rates of convergence in metric spaces, J. Symb. Logic74 (2009), 1401–1428. doi:10.2178/jsl/1254748697.
8.
D.K.Brown, Functional analysis in weak subsystems of second order arithmetic, PhD thesis, Pennsylvania State University, 1987.
9.
J.V.Burke and M.C.Ferris, Weak sharp minima in mathematical programming, SIAM J. Control Optim.31 (1993), 1340–1359. doi:10.1137/0331063.
10.
A.Dontchev and R.Rockafellar, Implicit Functions and Solution Mappings. A View from Variational Analysis, Springer Monographs in Mathematics, Springer, Dordrecht, 2009.
11.
P.Gerhardy, A quantitative version of Kirk’s fixed point theorem for asymptotic contractions, J. Math. Anal. Appl.316 (2006), 339–345. doi:10.1016/j.jmaa.2005.04.039.
12.
P.Gerhardy and U.Kohlenbach, General logical metatheorems for functional analysis, Trans. Amer. Math. Soc.360 (2008), 2615–2660. doi:10.1090/S0002-9947-07-04429-7.
13.
U.Kohlenbach, Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallée Poussin’s proof for Chebycheff approximation, Ann. Pure Appl. Logic64 (1993), 27–94. doi:10.1016/0168-0072(93)90213-W.
14.
U.Kohlenbach, New effective moduli of uniqueness and uniform a-priori estimates for constants of strong unicity by logical analysis of known proofs in best approximation theory, Numer. Funct. Anal. Optim.14 (1993), 581–606. doi:10.1080/01630569308816541.
15.
U.Kohlenbach, Things that can and things that cannot be done in PRA, Ann. Pure Applied Logic102 (2000), 223–245. doi:10.1016/S0168-0072(99)00036-6.
16.
U.Kohlenbach, On the computational content of the Krasnoselski and Ishikawa fixed point theorems, in: Proceedings of the Fourth Workshop on Computability and Complexity in Analysis, J.Blanck, V.Brattka and P.Hertling, eds, LNCS, Vol. 2064, Springer, 2001, pp. 119–145. doi:10.1007/3-540-45335-0_9.
17.
U.Kohlenbach, Some logical metatheorems with applications in functional analysis, Trans. Amer. Math. Soc.357(1) (2005), 89–128. doi:10.1090/S0002-9947-04-03515-9.
18.
U.Kohlenbach, Applied Proof Theory: Proof Interpretations and Their Use in Mathematics, Springer Monographs in Mathematics, 2008, xx+536pp.
19.
U.Kohlenbach, G.López-Acedo and A.Nicolae, Moduli of regularity and rates of convergence for Fejér monotone sequences, Submitted, arXiv:1711.02130.
20.
U.Kohlenbach and P.Oliva, Proof mining in -approximation, Ann. Pure Appl. Logic121 (2003), 1–38. doi:10.1016/S0168-0072(02)00081-7.
21.
A.Y.Kruger, Error bounds and metric subregularity, Optimization64 (2015), 49–79. doi:10.1080/02331934.2014.938074.
22.
D.Leventhal, Metric subregularity and the proximal point method, J. Math. Anal. Appl.360 (2009), 681–688. doi:10.1016/j.jmaa.2009.07.012.
23.
E.Neumann, Computational problems in metric fixed point theory and their Weihrauch degrees, Log. Method. Comput. Sci.11 (2015), 44pp.
24.
C.Parsons, On n-quantifier induction, J. Symbolic Logic37 (1972), 466–482. doi:10.2307/2272731.
25.
S.G.Simpson, Subsystems of Second Order Arithmetic, 2nd edn, ASL Perspectives in Mathematical Logic, Cambridge University Press, 2009, xvi+444.
26.
E.Specker, Nicht konstruktiv beweisbare Sätze der Analysis, J. Symb. Logic14 (1949), 145–158. doi:10.2307/2267043.
27.
E.Specker, Der Satz vom Maximum in der rekursiven Analysis, in: Constructivity in Mathematics, A.Heyting, ed., Proceedings of the Colloquium Held at Amsterdam 1957, North-Holland, 1959, pp. 254–265.
28.
A.S.Troelstra and D.van Dalen, Constructivism in Mathematics, Vol. I, North-Holland, Amsterdam, 1988.
