The strict superlinear order can be faster than the infinite order

Abstract

The strict superlinear order (superlinear convergence) was usually regarded as having an intermediate speed between between linear and with order \(p>1\).

In this paper we analyze the superlinear convergence (superlinear order/rate) of sequences and we show that actually there are four distinct classes of strict superlinear order: “weak”, “medium”, “strong” and “mixed”. The speed of the sequences from the first three classes is increasingly much faster, term-by-term big Oh, i.e.,
\[|x^\ast-x_k|=\mathcal{O}(|y^\ast-y_k|^{\alpha}),  \mbox{ as } k\rightarrow \infty, \forall \alpha>1 \mbox{ given},
\]whereas the speed of the “mixed” class cannot be assessed.

We prove that the speed of the sequences from the “medium” and “weak” classes is term-by-term slower than the speed of the sequences with high classical C-orders \(p>1\) (in the sense of big Oh above), while an example shows that certain sequences from the “mixed” class may be term-by-term faster than some sequences with infinite C-order.

We also show that for a given sequence with strict superlinear convergence, one can evaluate numerically to which class it belongs.

Some recent results of Rodomanov and Nesterov (Math. Program., 2022), resp. Ye et al. (Math. Program., 2023) show that certain classical quasi-Newton methods (DFP, BFGS and SR1) belong to the “weak” class.

Authors

Emil Cătinaş
“Tiberiu Popoviciu” Institute of Numerical Analysis

Keywords

convergent sequence, convergence order, convergence speed, superlinear order, Q-order, convergence rate, big Oh, quasi-Newton method, DFP, BFGS, SR1.

Paper coordinates

E. Cătinaş, The strict superlinear order can be faster than the infinite order, Numer. Algor., (2023). https://doi.org/10.1007/s11075-023-01604-y

PDF

About this paper

Journal

Numerical Algorithms

Publisher Name

Springer Nature

Print ISSN

1017-1398

Online ISSN

1572-9265

google scholar link

The strict superlinear order can be faster than the infinite order

The strict superlinear order
can be faster than the infinite order

Emil Cătinaş111“Tiberiu Popoviciu” Institute of Numerical Analysis, Romanian Academy, P.O. Box 68-1, Cluj-Napoca, 400110, Romania, e-mail: ecatinas@ictp.acad.ro.
Abstract

The sequences with strict superlinear convergence are the output of numerous algorithms; such speed is clearly much faster than linear, but is it also slower than, say, quadratic?

In this note we show that actually there are four distinct classes of strict superlinear order: “weak”, “medium”, “strong” and “mixed”. The speed of the sequences from the first three classes is increasingly much faster (term-by-term big Oh, i.e., |xxk|=𝒪(|yyk|α), as k,α>1 given), whereas the speed of the “mixed” class cannot be assessed.

We prove that the speed of the sequences from the “medium” and “weak” classes is term-by-term slower than the speed of the sequences with high classical C-orders p>1 (in the sense of big Oh above), while an example shows that certain sequences from the “mixed” class may be term-by-term faster than some sequences with infinite C-order.

We also show that for a given sequence with strict superlinear convergence, one can evaluate numerically to which class it belongs.

Some recent results of Rodomanov and Nesterov (2022), resp. Qi et al. (2023) show that certain classical quasi-Newton methods (DFP, BFGS and SR1) belong to the “weak” class.

Keywords: convergent sequence, convergence order, convergence speed, superlinear order, Q-order, convergence rate, big Oh, quasi-Newton method, DFP, BFGS, SR1.

MSC: 40A05.

1 Introduction

We consider here real sequences {xk} converging to finite limits, xkx and, since we analyze the behavior of the absolute value of their errors, we assume without loss of generality that x=0 and xk>0 (i.e., xk=|xxk|). A more general frame may be considered (normed or metric spaces), but the one-dimensional setting is enough to analyze some essential properties.

First we recall some definitions and notations regarding orders other than superlinear. The quotient convergence factors are defined by [12, sect. 9.1]

Qp(k):=|xxk+1||xxk|p=xk+1(xk)p,k=0,1,,(p1),

with their lower/upper limits given by \stackunder[1.2pt]Q p=lim infkQp(k), resp. Q¯p=lim supkQp(k) [1].

The sequence {xk} has C-order p0>1 if Qp0:=limkQp0(k)(0,+) (i.e., Qp0 exists and is finite and nonzero), the linear C-order is attained when Q1:=limkQ1(k)(0,1), while the sublinear C-order requires Q1=1.

For the Q-order p0>1 there are four equivalent definitions (see [5], [15], [1], [7], [10]), but we consider here only two convenient ones

limkQL(k) =p0,with QL(k):=lnxk+1lnxk,k0, (QL)
limkQΛ(k) =p0, with QΛ(k):=lnxk+2xk+1lnxk+1xk,k0. (QΛ)

The lower/upper Q-orders, denoted by ql resp. qu, are (see [1], [7] and [10])

ql=inf{p[1,):Q¯p=+},resp., qu=sup{p[1,):\stackunder[1.2pt]Q p=0},

and it holds:

  • ql=lim infQL(k), qu=lim supQL(k) (retrieving qlqu in another way),

  • (QL)(QΛ)p0=ql=qu>1,

the condition p0=ql=qu>1 providing the third equivalent definition of the Q-order p0>1. When p0=1, the four definitions are no longer equivalent, as shown in [1].

Remark 1

Q1[0,1], when the limit exists (i.e., Q1>1 cannot hold). When Q1 (and therefore \stackunder[1.2pt]Q 1<Q¯1) the “global speed” of {xk} may be difficult to assess.

The sequences with Q¯1=, called in [10] “with unbounded nonmonotone errors”333Recall that one cannot have Q1=+ (as suggested by a typo in the abstract of [10]), but just Q¯1=+. despite not attaining Q-linear order, were shown that sometimes may have fast speed, as, e.g., xk={24k,k𝑒𝑣𝑒𝑛,25k,k𝑜𝑑𝑑 yk={232k,k𝑒𝑣𝑒𝑛,242k,k𝑜𝑑𝑑 (see [10, Ex. 2.46]). Such sequences were also called subsequently there “with no Q-order” [10, §2.2] but we notice here that such terminology is not suitable: zk={1k,k even1klnk,k odd shows that one may have Q¯1= and (QL)-order one.

As regarding the fast speed, it cannot be attained when \stackunder[1.2pt]Q 1>0 (due to the obvious lower bounds of the errors) and one necessarily needs \stackunder[1.2pt]Q 1=0; however, condition \stackunder[1.2pt]Q 1=0 alone is not also sufficient for fast speed: take {zk} above or uk={1k,k even1k,k odd.

The Q-superlinear convergence—which we call here simply as superlinear—requires (see [12, ch. 9], [4], [14], [7], [10])

limkxk+1xk=0 (1)

and it is usually understood as “at least superlinear order”: indeed, all {xk} with Q-order p0=ql=qu>1 or just with lower Q-order ql>1 are also superlinear (ql>1 implies p(1,ql),A>0 s.t. xk+1<Axkp, k0 [12, sect. 9.1], [10] and therefore xk+1xk<Axkp10).

Remark 2

There is another type of superlinear speed, the R-superlinear order, usually defined by using root-convergence factors (see [12, ch. 9], [14]), or (as for higher orders), simply by requiring that the errors are bounded by another sequence, converging to zero with Q-superlinear order [19], [13, (37b)].

Tapia [19] noticed that convergence with (lower) R-order p0 arbitrary high does not imply Q-superlinear convergence, while Boggs, Tolle and Wang [3] concluded that “because an R-superlinearly convergent sequence need not be even Q-linearly convergent, R-superlinear convergence by itself is computationally meaningless”. We have seen in the previous Example that the fast sequence {yk} with R-superlinear convergence (in fact with infinite R-order) not only that does not attain some type of Q-linear order, but even has unbounded nonmonotone errors (Q¯1=).

The above Example therefore shows that the Q-superlinear convergence is not necessary for high speed: {yk} there converges pretty fast despite Q¯1=+.

2 The strict superlinear (SSL) convergence

The strict superlinear (SSL) convergence requires additionally that [10]

Q¯p=lim supkxk+1xkp=+,p>1, (2)

i.e., {xk} does attain neither some Q-order p0>1 nor some lower Q-order ql>1.

The SSL was usually seen as a fast convergence, with an intermediate speed between the linear and high orders. Indeed, the SSL is (much) faster than the linear C-order, in the sense that

xk=𝒪(ykα), as k(α>1 given). (xk=𝒪(ykα))
Proposition 3

If {xk} has SSL order and {yk} has C-linear order then {xk} is [(xk=𝒪(ykα)), α>1] faster than {yk}.

For the proof we use here (and later too) the well known ratio test for sequences.

Lemma 4

Given a sequence {zk} with zk>0 k0, if zk+1zk0 then zk0. The same conclusion holds if zk+1zkq(0,1).

Proof of Proposition 3. Take zk=xkykα and apply Lemma 4.   

However, the SSL convergence is not always slower than that with some Q-order p0>1, as we will show in Example 10. Before that, we further analyze the SSL order.

Example 5

The convergence of {1k!} and of {1kk} is SSL—with the “strictness” implied by their QΛ-order one (QΛ(k)1).

By denoting a0=x0, ak+1=xk+1xk>0, k0,444When {xk} is starting from x1, {ak} is starting from a1 (as, e.g., {1kk}, {1k}, etc.). condition (1) may be equivalently written as (see, e.g., [13, (37b)] and [10])

xk=i=0kai,with ak0, as k. (3)

For the SSL convergence of {xk}, the Q-order of {ak} cannot be greater than one.

Theorem 6

Let ak>0 with ak0 as k. If {ak} has QL-order p0=1, then {xk} from (3) has SSL order. If {ak} has Q-order p0>1, then {xk} has Q-order p0.

Proof. The proof is obtained by using (QΛ).   

Now, consider {ak}, or just simply ask ourselves: how fast does {xk+1xk} converge to zero? We obtain the following classification of the SSL order:

(a) (strong SSL)

ak0 strict superlinearly: limkak+1ak=limkxk+1xk1xk2=0;

(b) (medium SSL)

ak0 with C-order 1: limkak+1ak=limkxk+1xk1xk2=q(0,1);

(c) (weak SSL)

ak0 C-sublinearly: limkak+1ak=limkxk+1xk1xk2=1;

(d) (mixed SSL)

otherwise.

Remark 7

We note that the weak SSL order may be defined by requiring only that 0<Q¯1<1 (instead of requiring C-linear order).

Example 8

One can show that {12k2} has medium SSL while {12k3} has strong SSL order.

Example 9

{1kk} has weak SSL order (hint: ak+1=1k+11(1+1k)k1e1k+1).

Example 10

a) (strong SSL) ak=1k!, so xk=11!2!k!; one may take further bk=11!2!k! and by theorem 6 yk=b1bk is again SSL, etc. For another instance, take ck=1kk, so zk=11122kk,etc.;

b) (medium SSL) for q(0,1) fixed, take ak=qk, so xk=q1qk=qk(k+1)2;

c) (weak SSL) ak=1k, so xk=1k!;

For the mixed class, we may take (similar) sequences from Remark 1 as {ak}.

d) (mixed SSL) ak={122k,k even123k,k odd, bk={1222k,k even1232k,k odd, ck={1k,k even1klnk,k odd, dk={1k,k even1(lnk)k,k odd, etc., resulting the corresponding sequences {xk}, {yk}, {zk}, resp. {uk}.

We notice that yk<bk1222k, k1, i.e., the SSL {yk} is term-by-term faster than {bk} (with no Q-order) which is in turn term-by-term faster than {1222k} (with infinite C- and Q-order).

In Figure 1 we have plotted some of these sequences (k1), computed using the Tikz/Pgf LaTeX package [18] (the cases {xk}, {zk} from (a), {xk} from (c) and {xk}, {yk} from (d), were first computed in Julia [2], using BigFloat with setprecision(10^4), and then passed to Tikz/Pgf).

The first values of the fastest sequence (in red), written truncated, are x0=2.5101 (not plotted), x1=4.8104, x2=7.4109, x3=6.5101 984, x4=3.21021 712, and x4 cannot therefore be plotted, being below the realmin107100 from Tikz/Pgf.

The second fastest sequence (violet, with infinite C-order) has the following iterates x0=2.5101 (not plotted), x1=6.2102, x2=1.5105, x3=8.61078, x4=4.91019 729 (not plotted).

Refer to caption
Figure 1: Linear, weak SSL, medium SSL, strong SSL, mixed SSL, quadratic and infinite orders.

The strong SSL {12k3} appears close to the quadratic {122k}, but their speed is quite different (as also shown by the next Theorem): indeed, at k=11, {122k} has approximately the same value as {12k3} at k=16; one more step of {122k} needs four steps of {12k3} to get the same magnitude.

With the scales of Figure 1, the weak SSL of xk=1k! appears only slightly faster than that of the linear {12k}, but the conclusions of Proposition 3 hold.

The following result justifies the terminology of strong, medium and weak SSL.

Theorem 11

If {xk} has strong SSL and {yk} has medium SSL, then {xk} is [(xk=𝒪(ykα)), α>1] faster than {yk}. The same conclusion holds for {xk} with medium SSL and {yk} with weak SSL order.

Proof. Let xk=i=0kai,yk=i=0kbi, with limak+1ak=0 and limbk+1bk=q(0,1).

As (xk+1xk/xkxk1)/(yk+1yk/ykyk1)α=ak+1ak/(bk+1bk)α0, by Lemma 4 we get xk+1xk/(yk+1yk)α0 and therefore xkykα0. The second part is similar.   

Remark 12

In [10, Rem. 2.50(b)] we noted (without proof) that “the C-orders (i.e., sublinear, linear, strict superlinear, 1<p̊0<p˙0 and infinite) form classes in [(xk=𝒪(ykα)), α>1] increasing speed”. However, the SSL order was erroneously mentioned, as it is not a C-order (its definition requires Q¯p, as noted in (2)) and moreover such a statement does not hold, as we have already seen in Example 10.

Here we prove that the weak and the medium SSL are (much) slower than the C-orders p>1.

Theorem 13

If {xk} has C-order p0>1 and {yk} has weak or medium SSL then {xk} is [(xk=𝒪(ykα)), α>1] faster than {yk}.

Proof. Let uk=xkykα, vk=uk+1uk. As vk+1vk=xk+2xk+1p0xkp0xk+1(xk+1xk)p01(yk+12ykyk+2)α0, by Lemma 4 we successively get vk,uk0.   

In some particular cases, the strong SSL is also (much) slower than C-order p>1.

Theorem 14

Let {xk} have C-order p>1 and {yk} have strong SSL order: bk=ak+1ak0, ak=yk+1yk. If {bk} has weak or medium SSL then {xk} is [(xk=𝒪(ykα)), α>1] faster than {yk}.

Proof. The proof is similar to the one of Theorem 13.   

For the remaining part of this paper we denote the absolute value of errors by |xxk| (instead of simply by xk).

In case of at least superlinear convergence, it was shown that the absolute value of the errors |xxk| and of the corrections |xk+1xk| behave asymptotically in the same way (the result also holds in N).

Lemma 15 (Potra–Pták Lemma, [14, Prop. 6.4]; see also [20])

xkx at least Q-superlinearly iff xk+1xk0 at least Q-superlinearly.

If {xk} has (at least) Q-superlinear convergence, then it holds that (the Dennis–Moré Lemma [11])

limk|xk+1xk||xxk|=1. (4)

We obtain the following immediate result, which holds in N as well.

Corollary 16

Given a sequence {xk} s.t. xkx with SSL convergence, let αk:=|xk+2xk+1||xk+1xk| and take

αk+1αk=|xk+2xk+1||xkxk1||xk+1xk|2. (5)
  • If αk+1αk1 then {xk} has weak SSL;

  • if αk+1αkq(0,1) then {xk} has medium SSL;

  • if αk+1αk0 then {xk} has strong SSL;

  • if {αk+1αk} does not converge at all then {xk} has mixed SSL.

The proof is obvious, as the errors from the expressions ak+1ak=|xk+1x||xk1x||xkx|2 by (4) may be replaced by corrections.

Example 17

We consider the SSL sequences from Example 10 and for each of them we represent graphically in Figure 2 the expressions (5), using the same corresponding colors as in Figure 1 (here the limit x=0 is known, but formula (5) does not require its knowledge).

For the same precision as in Example 10 (setprecision(10^4)), we have obtained nonzero results for k17; the (truncated) values of αk+1αk for k=17 are, for the following {xk}’s: {1kk} 0.943 (true limit 1); {1k!} 0.944 (true limit 1); {12k(k+1)/2} 0.4999990 (true limit 12); {12k2} 0.2499999 (true limit 14); {11!k!} 0.055 (true limit 0, but very slow convergence); {111kk} 0.0210 (true limit 0, but very slow convergence); {12k3} 1.971031 (true limit 0).

In the last two cases (Example 10d, xk=Πai, resp. yk=Πbi), much fewer relevant terms can be computed with this precision, and one clearly see we do not have convergence.

In each case it is confirmed numerically that the sequence belongs to the stated SSL class. However, it is worth noting that in some cases (e.g., {11!k!} and {111kk}) some more terms are needed to conclude that the sequence {αk+1αk} converges.

In certain applications it may be difficult to verify numerically whether αk+1αk converges to 0, to 1 or to some value in (0,1) (if at all), especially when the convergence is slow.

Refer to caption
Figure 2: αk+1αkak+1ak=|xk+1x||xk1x||xkx|2 for evaluating numerically the SSL order.

Numerous methods from Computational Optimization were proved to be with (at least) superlinear order. Three classical methods have explicit expressions for their errors, and now their speed can be assessed.

Example 18

The quasi-Newton methods for smooth unconstrained optimization are known for a long time that attain superlinear order, but it is only recently that some explicit expressions for the errors have been obtained.

Rodomanov and Nesterov [16] have shown for the Davidon–Fletcher–Powell (DFP) method that the errors are of the form ek=(ak)k2 (a depending on the dimension problem, the Lipschitz constant and the strong convexity parameter) and for the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method that similarly ek=(bk)k2.

Subsequently, Ye et al. [21] have shown for the Symmetric-Rank 1 (SR1) method that ek=(ck)k2.

We see that all the three methods attain weak SSL order, and it becomes interesting to find methods with medium or perhaps strong SSL order, for the reason that their faster speed may appear from the first terms.

3 Conclusions

The main role of the convergence orders is to allow the comparison of the speed of different convergent sequences: we usually expect that the higher the order, the faster the speed; while this is in general true (as shown in [8] for orders 1<p<q<+), these notions are imperfect and there are some notable exceptions. Indeed, a sequence with no Q-order was shown in [10] that may have fast speed (term-by-term faster than another sequence, with infinite order).

Here we have seen that a similar phenomenon holds in the case of the (mixed) superlinear convergence, as such a sequence may converge faster than another sequence, with infinite order (though, it is worth noting that not all sequences with mixed SSL order have such fast speed).

The explanation for such a behavior resides in the fact that both the superlinear and the Q-orders rely on conditions on consecutive errors, not on “global” relations involving all the errors. The graph of the sequence from Example 10(d) (xk=Πai) which was plotted in Figure 1 in olive color is perhaps most relevant: while its speed is high (steep slope), some of the consecutive errors do not have a high relative reduction.

A similar analysis may be taken for the linear convergence [9], and the higher orders [8], but with notable different particularities; we have also started to analyze the sublinear convergence.

In [6] we study the speed of {QΛ(k)} and {QL(k)}, while in [17] we obtain some simplified proofs for the Q-order.

Data availability. All data generated or analysed during this study are included in this published article.

Conflict of interest. The author has no conflict of interests to declare that are relevant to the content of this article.

Ethical Approval. Not Applicable.

Availability of supporting data. Not Applicable.

Competing interests. Not Applicable.

Funding. Not Applicable.

Authors’ contributions. Not Applicable.

Acknowledgments. Not Applicable.

References

  • [1] W. A. Beyer, B. R. Ebanks, and C. R. Qualls (1990) Convergence rates and convergence-order profiles for sequences. Acta Appl. Math. 20 (), pp. 267–284. External Links: Document Cited by: §1, §1, §1.
  • [2] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah (2017) Julia: a fresh approach to numerical computing. SIAM Review 59 (), pp. 65–98. External Links: Document Cited by: Example 10.
  • [3] P. T. Boggs, J. W. Tolle, and P. Wang (1982) On the local convergence of quasi-newton methods for constrained optimization. SIAM Journal on Control and Optimization 20 (2), pp. 161–171. External Links: Document, Link, https://doi.org/10.1137/0320014 Cited by: Remark 2.
  • [4] C. Brezinski (1977) Accélération de la convergence en analyse numérique. Springer-Verlag, Berlin. Cited by: §1.
  • [5] C. Brezinski (1985) Vitesse de convergence d’une suite. Rev. Roumaine Math. Pures Appl. 30, pp. 403–417. Cited by: §1.
  • [6] E. Cătinaş and A. Stan (2021) Measuring the measures. Note: (manuscript) Cited by: §3.
  • [7] E. Cătinaş (2019) A survey on the high convergence orders and computational convergence orders of sequences. Appl. Math. Comput. 343 (), pp. 1–20. External Links: Document Cited by: §1, §1, §1.
  • [8] E. Cătinaş (2021) Characterizing the classical convergence orders. Note: manuscript, submitted Cited by: §3, §3.
  • [9] E. Cătinaş (2021) Characterizing the classical linear convergence order. Note: manuscript Cited by: §3.
  • [10] E. Cătinaş (2021) How many steps still left to x*?. SIAM Rev. 63 (3), pp. 585–624. External Links: Document Cited by: §1, §1, §1, §2, §2, §3, Remark 1, Remark 12, footnote 3.
  • [11] J. E. Dennis, Jr. and J. J. Moré (1974) A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comp. 28 (126), pp. 549–560. External Links: Document Cited by: Lemma 15.
  • [12] J. M. Ortega and W. C. Rheinboldt (2000) Iterative solution of nonlinear equations in several variables. SIAM, PA. External Links: Document Cited by: §1, §1, Remark 2.
  • [13] E. Polak (1997) Optimization. algorithms and consistent approximations. Springer-Verlag, New York. Cited by: §2, Remark 2.
  • [14] F. A. Potra and V. Pták (1984) Nondiscrete induction and iterative processes. Pitman, Boston, Massachusetts. Cited by: §1, Lemma 15, Remark 2.
  • [15] F. A. Potra (1989) On Q-order and R-order of convergence. J. Optim. Theory Appl. 63 (3), pp. 415–431. External Links: Document Cited by: §1.
  • [16] A. Rodomanov and Y. Nesterov (2022) Rates of superlinear convergence for classical quasi-Newton methods. Math. Program. 194 (1-2, Ser. A), pp. 159–190. External Links: ISSN 0025-5610, Document, Link Cited by: Example 18.
  • [17] A. Stan and E. Cătinaş (2021) Simpler proofs for the Q-order. Note: manuscript Cited by: §3.
  • [18] T. Tantau The tikz and pgf packages. Manual for version 3.1.5b-34-gff02ccd1. External Links: Link Cited by: Example 10.
  • [19] R. A. Tapia (1977) Diagonalized multiplier methods and quasi-Newton methods for constrained optimization. J. Optim. Theory Appl. 22 (2), pp. 135–194. External Links: ISSN 0022-3239, Document, Link Cited by: Remark 2, Remark 2.
  • [20] H. F. Walker (1997) An approach to continuation using Krylov subspace methods. Computational Science in the 21st Century, J. Periaux, ed., John Wiley and Sons, Ltd., pp. 72–81. Cited by: Lemma 15.
  • [21] H. Ye, D. Lin, X. Chang, and Z. Zhang (2023) Towards explicit superlinear convergence rate for SR1. Math. Program. 199 (1-2, Ser. A), pp. 1273–1303. External Links: ISSN 0025-5610, Document, Link, MathReview Entry Cited by: Example 18.

Preprint html version of the paper:

[1] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. SIAM, PA (2000)
[2] Beyer, W.A., Ebanks, B.R., Qualls, C.R.: Convergence rates and convergence-order profiles for sequences. Acta Appl. Math. 20, 267–284 (1990)
[3] Brezinski, C., Vitesse de convergence d’une suite. Rev. Roumaine Math. Pures Appl. 30, 403–417 (1985)
[4] Potra, F.A., On Q-order and R-order of convergence. J. Optim. Theory Appl. 63(3), 415–431 (1989)
[5] Catinas, E., A survey on the high convergence orders and computational convergence orders of sequences. Appl. Math. Comput. 343, 1–20 (2019)
[6] Catinas, E., How many steps still left to x*? SIAM Rev. 63(3), 585–624 (2021)
[7] Brezinski, C., Accélération de la Convergence en Analyse Numérique. Springer-Verlag, Berlin (1977)
[8] Potra, F.A., Pták, V.,  Nondiscrete Induction and Iterative Processes. Pitman, Boston, Massachusetts (1984)
[9] Tapia, R.A., Diagonalized multiplier methods and quasi-Newton methods for constrained optimization. J. Optim. Theory Appl. 22(2), 135–194 (1977)
[10] Polak, E., Optimization. Algorithms and Consistent Approximations. Springer-Verlag, New York (1997)
[11] Boggs, Paul T., Tolle, Jon W., Wang, Pyng, On the local convergence of Quasi-Newton methods for constrained optimization. SIAM Journal on Control and Optimization 20(2), 161–171 (1982)
[12] Tantau, T., The tikz and pgf packages. Manual for version 3.1.5b-34-gff02ccd1
[13] Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Review 59, 65–98 (2017)
[14] Walker, H.F., An approach to continuation using Krylov subspace methods. In: Periaux, J. (ed.) Computational Science in the 21st Century, pp. 72–81. John Wiley and Sons, Ltd. (1997)
[15] Dennis, J.E., Jr., Moré, J.J., A characterization of superlinear convergence and its application to quasiNewton methods. Math. Comp. 28(126), 549–560 (1974)
[16] Rodomanov, A., Nesterov, Y., Rates of superlinear convergence for classical quasi-Newton methods. Math. Program. 194(1–2, Ser. A), 159–190 (2022)
[17] Ye, H., Lin, D., Chang, X., Zhang, Z., Towards explicit superlinear convergence rate for SR1. Math. Program. 199(1–2, Ser. A), 1273–1303 (2023)
[18] Catinas, E., Characterizing the classical convergence orders. Manuscript, submitted (2021)
[19] Catinas, E., Characterizing the classical linear convergence order Manuscript. (2021)
[20] Catinas, E., Stan, A., Measuring the measures. (2021). (manuscript)
[21] Stan, A., Catinas, E., Simpler proofs for the Q-order. Manuscript (2021)

2023

Related Posts