Worst-case complexity analysis of derivative-free methods for multi-objective optimization

Giampaolo Liuzzi; Stefano Lucidi

REVIEW 2 major objections 6 minor 2 cited by

Worst-case complexity analysis of derivative-free methods for multi-objective optimization

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Derivative-free multi-objective methods hit ε-Pareto criticality in O(n^q ε^{-2q}) iterations

desk verdict Useful extension of DFO worst-case bounds to multiobjective a posteriori methods, but Proposition 2's displacement bound is wrong and breaks the claimed n-dependence in the strong-exploration results. read the letter →

arxiv 2505.17594 v1 pith:RUAGDU24 submitted 2025-05-23 math.OC

Giampaolo Liuzzi , Stefano Lucidi This is my paper · ORCID

classification math.OC MSC 90C2990C3090C56

keywords multi-objectiveoptimizationderivative-freeworst-casecomplexityParetocriticalityhypervolumeindicatorlinesearchexpansionaposteriorimethodsnon-dominatedsolutions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes worst-case complexity bounds for two derivative-free, a posteriori multi-objective optimization algorithms, DFMOstrong and DFMOlight, which produce sets of non-dominated points using only function evaluations. The main result is that DFMOstrong reaches a list in which every point has Pareto criticality at most ε in O(n^q $ε^{{-2q}}$) iterations, with O($n^{{q+1}}$ L(ε) $ε^{{-2q}}$) function evaluations, where n is the dimension, q the number of objectives, and L(ε) the maximum list size. DFMOlight, which explores around only one point per iteration, finds at least one ε-critical point in O(|L(ε)| $ε^{{-2q}}$) iterations, matching the bound previously known for directional direct-search methods. These results quantify how the number of objectives and problem dimension affect the cost of certifying Pareto-stationary approximations of the front. A sympathetic reader would care because these bounds are the first for set-based derivative-free methods with the linesearch expansion technique, and they provide a benchmark for practical a posteriori algorithms.

What carries the argument

The key machinery is the Approximate Optimization procedure, a linesearch expansion that moves along each direction d_i in the current set D_k. Starting with a trial step β equal to the current step size, it repeatedly tests y+β d_i; the point is accepted into the set if it is sufficiently non-dominated, i.e. F(y+β d_i) is not componentwise greater than F(z) - γ $β^{2}$ 1 for every z in the current set. When the trial fails, the procedure returns the largest accepted step; this failure condition, combined with the Lipschitz continuity of the gradients, gives the step-size bound on μ_Dk(x_k). Progress is measured by the hypervolume indicator HI(F(X_k)) with a reference point ρ = f_max + s 1, and the auxiliary cost function Φ_k = -HI(F(X_k)) + η $Δ_k^{{2q}}$ decreases by a fixed amount at every iteration. Telescoping that decrease over iterations is what converts hypervolume gains into iteration counts of order $ε^{{-2q}}$.

What would settle it

Run DFMOstrong on a smooth bi-objective quadratic in R^n with D_k the 2n coordinate directions, record for every iterate the ratio μ_Dk(x_k)/Δ_{k+1}, and compare it to the constant c from Proposition 2; a single iterate exceeding that constant, or an iterate with μ(x_k)>0 but μ_Dk(x_k)=0, would violate the paper's key inequality. Alternatively, inspect the iteration count needed to reach Γ(X_k)≤ε on random instances; if it grows faster than O(n^q $ε^{{-2q}}$) for fixed n and q, the bound would be contradicted.

Watch

Extended reading notes

Core claim

The central discovery is that a linesearch expansion procedure links step sizes to the Pareto criticality measure, turning step-size decrease into a stationarity certificate for the whole list. In Proposition 2, the paper proves that for every point x_k and every direction set D_k, the approximate criticality measure μ_Dk(x_k) is bounded above by a constant times the maximum step size Δ_{k+1} produced by the expansion, either c1 Δ_{k+1} on successful explorations or c2 Δ_{k+1} on failures. Because each successful iteration increases the hypervolume of the list by a fixed multiple of Δ_{k+1}^{2q}, the cost function Φ_k = -HI(F(X_k)) + η $Δ_k^{{2q}}$ decreases by at least c~ (Δ_{k+1}^2)^q at every iteration. Summing these decreases yields Proposition 5: the number of iterations with Γ(X_k)>ε is at most O(n^q $ε^{{-2q}}$). The same mechanism, applied along linked sequences, gives the DFMOlight, DFMOmin, and DFMOmax variants their respective bounds. In short, the paper proves that step-size decrease plus hypervolume growth is enough to certify Pareto stationarity in worst case.

Load-bearing premise

All complexity results rest on Assumption 3: at every iterate, the distance between the true Pareto criticality measure and its discrete approximation must be bounded by a constant times the discrete measure, and the direction set must have size r=O(n); if some noncritical point has no common descent direction in D_k, the step-size-to-stationarity bounds may fail and the $ε^{{-2q}}$ guarantees no longer follow.

Editorial extensions

If this is right

If the central bounds are correct, the single-objective case q=1 reproduces the classical O(ε^{-2}) iteration complexity and O(n ε^{-2}) evaluation complexity of line-search derivative-free methods.
DFMOlight's bound O(|L(ε)| ε^{-2q}) shows that exploring only one point per iteration costs no more asymptotically than directional direct-search methods, at least for finding one ε-critical point.
DFMOstrong certifies the entire list is ε-critical in O(n^q ε^{-2q}) iterations, without an explicit list-size factor in the iteration count; the price is a factor n in per-iteration evaluations.
The exponent 2q implies that any method in this class will struggle as the number of objectives grows: reducing ε by a factor of ten multiplies the worst-case iteration count by 10^{2q}.
The convergence corollaries imply that DFMOstrong's list asymptotically converges to a set of Pareto critical points, and DFMOmax retains that all-points guarantee along a subsequence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The O(ε^{-2q}) scaling is likely a fundamental limitation for a posteriori methods that rely on hypervolume progress alone; it sets a baseline that gradient-based or sample-based multi-objective methods might aim to beat.
A direct testable extension is to instrument DFMOmin and DFMOmax on smooth bi-objective problems and measure the empirical exponent of iteration counts versus ε, which could reveal whether the constants in Proposition 2 are loose.
Because Assumption 3 involves a constant C that may not be known a priori, an algorithmic extension would be to adaptively enrich D_k with a common descent direction when μ_Dk(x_k)=0, making the bound constructive.
The hypervolume-based proof suggests that replacing the hypervolume with a weaker but cheaper progress measure, such as a scalarized improvement, could yield similar bounds with smaller constants and cheaper hypervolume computations.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper does something useful. It takes the line-search expansion machinery from single-objective DFO and adapts it to a posteriori multiobjective methods, producing worst-case iteration and evaluation bounds for four algorithm variants. DFMOlight matches the existing DMS bound, and the strong-exploration variants add a full-set guarantee. The proof architecture is mostly solid, with explicit Lipschitz and hypervolume arguments, no fitted parameters, and the paper openly discusses Assumption 3 and its limitations. But there is a real bug in Proposition 2 that affects the n-dependence of the strong variants.

The problem is the displacement bound. To pass from y_i^k back to x_k in the successful case, the proof uses ||x_k − y_i^k|| ≤ √n max_i α̃^i_{k+1}. But y_i^k is reached by taking up to r steps along arbitrary unit directions in D_k, and Assumption 3 only says r = O(n), not that the directions are orthogonal. The general bound is r times the max step, not √n. For n=2, a set of four nearly parallel positive-spanning directions satisfies Assumption 3 (single objective), and two successful steps along the first two directions give displacement ≈ 2Δ, which exceeds √2 Δ. So the constant ĉ in Propositions 5, 13, and 17 becomes O(n) instead of O(n^{1/2}), and the bounds O(n^q ε^{-2q}) turn into O(n^{2q} ε^{-2q}). The DFMOlight result in Propositions 9–11 is unaffected, since it only uses the unsuccessful-case bound with c2, which is independent of n. So the headline claim "aligned with the DMS bound" survives for DFMOlight, but the strong-exploration n-exponents are not established.

Assumption 3 is strong, but the authors state it plainly and discuss it in Remark 1; it's the same kind of assumption used in the DMS literature. Minor typos: the abstract says DFMOnew, the text says DFMOstrong, and Proposition 2 quantifies over i=1,...,n while it should be r.

This paper is for the worst-case complexity subfield. The DFMOlight bound is genuinely useful and deserves citation. The strong-exploration results are interesting if the displacement bound can be repaired, either by assuming orthonormal directions or by accepting the O(n^{2q}) dependence. I'd send it to referees, with a note to the authors to fix Proposition 2 before it's in final form.

Referee Report

2 major / 6 minor

Summary. The paper proposes two derivative-free algorithms for unconstrained multi-objective optimization with a posteriori Pareto-set approximation. DFMOstrong explores all current non-dominated points at each iteration using an expansion line search along a set of r = O(n) directions, while DFMOlight explores only one selected point per iteration, with special instances DFMOmin and DFMOmax. The authors derive worst-case iteration and evaluation complexity bounds to drive a Pareto criticality measure below a tolerance ε, using hypervolume progress and an auxiliary potential function. The headline claims are O(n^q ε^{-2q}) iterations for DFMOstrong to make all points in the list ε-critical, O(|L(ε)| ε^{-2q}) iterations for DFMOlight to produce one ε-critical point, and corresponding evaluation counts. The analysis follows the framework of Custódio et al. (2021) and the authors' earlier line-search expansion work.

Significance. If the stated n-dependence is correct, the paper gives a useful extension of worst-case complexity results from directional direct search to expansion-based line-search methods for multi-objective optimization, and it provides explicit constants and a transparent hypervolume-potential argument. The comparison with the DMS method and the separate treatment of min/max selection rules are valuable. However, the advertised n-exponent in the DFMOstrong and per-linked-sequence bounds rests on a geometric estimate that is not established for general direction sets, and one proof case in the potential-function argument is missing. These issues affect load-bearing parts of the derivation and must be fixed before the main complexity claims can be accepted.

major comments (2)

[Proposition 2, Section 3.1] In the successful-exploration case, the proof uses the bound ||x_k − y_i^k|| ≤ √n max_{i=1,...,r} α̃^i_{k+1} to pass from gradients at y_i^k to gradients at x_k. This bound is not justified. From the algorithm, y_i^k = x_k + ∑_{l<i} α_l d_l with ||d_l|| = 1 and arbitrary directions, so the general estimate is ||x_k − y_i^k|| ≤ ∑_{l<i} α_l ≤ r max_l α_l, not √n times the maximum step. Assumption 3 only requires |D_k| ≤ r = O(n) and does not impose orthogonality; the positive spanning sets discussed in Remark 1 can consist of arbitrarily oriented unit vectors. For n = 2, taking D_k = {(1,0), (cosθ,sinθ), (-1,0), (0,-1)} and expanding along the first two directions gives ||y_i^k − x_k|| ≈ 2Δ, which exceeds √2 Δ. Consequently, the constant ĉ in Proposition 5 should be O(n) rather than O(n^{1/2}), and the proof of |K_ε| ≤ O(n^q ε^{-2q}) collapses; the written argument yields at best O(r^q ε^{-2q}), i.e. O(n^{2q} ε^{-2q}) under r = O(n). The same ĉ appears in Propositions 10, 13, 14, 17, and 18, so the advertised n-dependence of those bounds is not established.
[Propositions 3 and 4, Section 3.1] Proposition 3 asserts that a successful iteration can only have Δ̄_k = Δ̄_{k+1} or Δ̄_k < Δ̄_{k+1}. If Algorithm 1 line 6 uses the same c ∈ (0,1) as Algorithm 3, this dichotomy is false. A point with the current maximum step can fail, reducing its step to θΔ̄_k, while another point succeeds with a step in [cΔ̄_k, θΔ̄_k); the iteration is then successful but Δ̄_{k+1} < Δ̄_k. In such a case the hypervolume increase can be as small as (γ c^2 Δ̄_k^2)^q, which can be much smaller than the quantity (γ c2 Δ̄_{k+1}^2)^q used in the proof of Proposition 4. The missing case must be handled explicitly (for example, using the η(1−θ^{2q})/θ^{2q} term already present in c̃, or adding a constant depending on c/θ), or DFMOstrong must be specified with c = 1. As written, the proof of the universal decrease of Φ_k, which underpins Propositions 5, 6, 10, 13, 14, 17, and 18, is incomplete.

minor comments (6)

[Abstract] The abstract refers to algorithms DFMOnew and DFMOlight, but the body of the paper uses DFMOstrong and DFMOlight; please harmonize the names.
[Algorithm 1] Algorithm 1 line 6 uses a constant c in cΔ̄_k, but c is not declared in the data statement; Algorithm 3 declares c ∈ (0,1). Please clarify the value of c for DFMOstrong and its role in Proposition 3.
[Proposition 2] The proof says 'For every i = 1, ..., n', but the direction set has r directions; it should read i = 1, ..., r.
[Proposition 6] The first sentence states N_f^{j_ε} ≤ O(n L(ε) ε^{-2q}), but the displayed bound and Table 1 give O(n^{q+1} L(ε) ε^{-2q}) because of the ĉ^{2q} factor; please correct the sentence or the display.
[Appendix A, Proposition 19] In the proof of the 'only if' part, the sets Y_j are defined for each coordinate j and ε as a minimum over them, but some Y_j may be empty; for example, different points may be improved in different coordinates. The equivalence is true, but the proof needs a case distinction or a different construction of the positive-volume box.
[Notation] The symbol L(ε) is used for max_k |L_k| in Proposition 6 and for the number of linked sequences in Proposition 9; please use distinct names to avoid confusion.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the complexity bounds are derived in-text from stated assumptions; self-citations to [6] and [16] are contextual, not load-bearing.

full rationale

The paper's complexity claims are derived in the text from explicit hypotheses (Assumptions 1-3), the bounded-hypervolume argument (Proposition 19 / Proposition 1), and the stepsize-to-stationarity bound of Proposition 2, with no fitted parameter being renamed as a prediction. The use of Assumption 3 to convert mu(x)>epsilon into mu_D(x)>epsilon/(C+1) is the application of a stated hypothesis, not a circular definition; Remark 1 openly acknowledges that the assumption can fail when no common descent direction exists, which is an honest limitation rather than a hidden circular reduction. The citations to the authors' own work [6] and [16] concern background WCC results and the linked-sequence formalism: Definition 6 is stated in full in the paper, and Proposition 2 is proved from Lipschitz continuity and the expansion loop, so these citations are not load-bearing. The DFMOlight bound is compared with, not assumed from, the DMS result in [1]. The skeptical concern about the displacement bound ||x_k - y_i^k|| <= sqrt(n) Delta in Proposition 2 is a correctness or rigor issue about the n-dependence of the constants, not a circularity, since it does not reduce the theorem to its own input by construction. Minor self-citations are present but do not carry the central derivation, so the paper is substantially self-contained and the circularity score is low.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No fitted parameters enter the complexity exponents; the proof rests on smoothness (Assumption 1), boundedness (Assumption 2), a direction-set approximation property (Assumption 3), and the imported criticality-measure lemma. The algorithmic constants θ, δ, γ, η, c, s appear only in constants of the bounds and are not fitted to data.

free parameters (1)

Algorithmic constants θ, δ, γ, η, c, s
Tuning and proof constants with stated ranges (θ, δ, γ, c in (0,1), 0<η<γ^q, s sufficiently large). They appear in the bounds only through constants, are not fitted to data, and the complexity exponents are independent of them.

assumptions (4)

domain assumption Objective functions are continuously differentiable with Lipschitz continuous gradients (Assumption 1), with constant L_max.
Used in Proposition 2 to bound first-order terms by step sizes via mean value theorem; standard for worst-case complexity.
domain assumption Objective functions are bounded on the set {x: F(x0) not ≤ F(x)} (Assumption 2), ensuring a finite hypervolume upper bound HI.
Underlies the hypervolume increase arguments in Propositions 3, 4, 7, and 8; restricts problems with bounded trade-off region.
domain assumption The direction sets D_k satisfy |μ(x_k)-μ_Dk(x_k)| ≤ C μ_Dk(x_k) and |D_k|≤r=O(n) (Assumption 3).
Bridges the continuous criticality measure μ and its discrete approximation μ_D; if no common descent direction exists, μ_D can vanish and the bounds fail.
standard math Pareto criticality measure μ(x) and the set F(x) satisfy the five properties stated in Lemma 1 (cited from Fliege and Svaiter [14]).
Imported background result used to define and manipulate the stationarity measure throughout the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Worst-case complexity analysis of derivative-free methods for multi-objective optimization." pith.science (2026). https://pith.science/paper/RUAGDU24

@misc{pith2026250517594,
  author       = {Pith},
  title        = {Pith review of: Worst-case complexity analysis of derivative-free methods for multi-objective optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RUAGDU24}},
  note         = {Machine review of arXiv:2505.17594}
}

read the original abstract

In this work, we are concerned with the worst case complexity analysis of "a posteriori" methods for unconstrained multi-objective optimization problems where objective function values can only be obtained by querying a black box. We present two main algorithms, namely DFMOnew and DFMOlight which are based on a linesearch expansion technique. In particular, \DFMOnew, requires a complete exploration of the points in the current set of non-dominated solutions, whereas DFMOlight only requires the exploration around a single point in the set of non-dominated solutions. For these algorithms, we derive worst case iteration and evaluation complexity results. In particular, the complexity results for DFMOlight aligns with those recently proved in the literature for a directional multisearch method. Furthermore, exploiting an expansion technique of the step, we are also able to give further complexity results concerning the number of iterations with a measure of stationarity above a prefixed tolerance.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Adaptive direct search algorithms for constrained optimization
math.OC 2025-07 conditional novelty 7.0 of 10

Adaptive Direct Search (ADS) replaces mesh or sufficient-decrease acceptance with a punctured-space exclusion rule, and is shown to generalize OrthoMADS and QRMADS.
Worst-Case Complexity of High-Order Algorithms for Pareto-Front Reconstruction
math.OC 2025-06 conditional novelty 7.0 of 10

New worst-case iteration and function-evaluation bounds for high-order set-generating multiobjective optimization algorithms, with exponents depending on the number of objectives and the model order.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages · cited by 2 Pith papers

[1]

A. L. Cust´ odio, Y. Diouane, R. Garmanjani, and E. Riccietti. Worst-case complexity bounds of directional direct-search methods for multiobjective optimization.Journal of Optimization Theory and Applications, 188(1):73–93, 2021

work page 2021
[2]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint.Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. SIAM, 2022

work page 2022
[3]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization problems.Siam journal on optimization, 20(6):2833–2852, 2010. Complexity analysis in DF multiobjective optimization 33 Fig. 2Hypervolume representation for the example in Remark 3

work page 2010
[4]

E. G. Birgin, J. L. Gardenghi, J. M. Mart ´ ınez, S. A. Santos, and Ph. L. Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regular- ized models.Mathematical Programming, 163:359–368, 2017

work page 2017
[5]

L. N. Vicente. Worst case complexity of direct search.EURO Journal on Computational Optimization, 1(1):143–153, 2013

work page 2013
[6]

Brilli, M

A. Brilli, M. Kimiaei, G. Liuzzi, and S. Lucidi. Worst case complexity bounds for linesearch-type derivative-free algorithms.Journal of Optimization Theory and Appli- cations, 203(1):419–454, 2024

work page 2024
[7]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization.SIAM Journal on Optimization, 22(1):66–86, 2012

work page 2012
[8]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results. Mathematical Programming, 127(2):245–295, 2011

work page 2011

Show all 16 references

[9]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function-and derivative-evaluation com- plexity.Mathematical Programming, 130(2):295–319, 2011

2011
[10]

Complexity of gradient descent for multiobjective optimization.Optimization Methods and Software, 34(5):949–959, 2019

J¨ org Fliege, A Ismael F Vaz, and Lu ´ ıs Nunes Vicente. Complexity of gradient descent for multiobjective optimization.Optimization Methods and Software, 34(5):949–959, 2019

2019
[11]

Calder´ on, M

L. Calder´ on, M. A. Diniz-Ehrhardt, and J. M. Mart ´ ınez. On high-order model regulariza- tion for multiobjective optimization.Optimization Methods and Software, 37(1):175–191, 2022

2022
[12]

M. Lapucci. Convergence and complexity guarantees for a wide class of descent algorithms in nonconvex multi-objective optimization.Operations Research Letters, 54:107115, 2024

2024
[13]

Lapucci, P

M. Lapucci, P. Mansueto, and D. Pucci. Effective front-descent algorithms with conver- gence guarantees.arXiv preprint arXiv:2405.08450, 2024

2024 arXiv
[14]

Fliege and B

J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51:479–494, 2000

2000
[15]

A. L. Cust´ odio, J. F. A. Madeira, A. I. F. Vaz, and L. N. Vicente. Direct multisearch for multiobjective optimization.SIAM Journal on Optimization, 21(3):1109–1140, 2011

2011
[16]

Liuzzi, S

G. Liuzzi, S. Lucidi, and F. Rinaldi. A derivative-free approach to constrained multiob- jective nonsmooth optimization.SIAM Journal on Optimization, 26(4):2744–2774, 2016

2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

A. L. Cust´ odio, Y. Diouane, R. Garmanjani, and E. Riccietti. Worst-case complexity bounds of directional direct-search methods for multiobjective optimization.Journal of Optimization Theory and Applications, 188(1):73–93, 2021

work page 2021

[2] [2]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint.Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. SIAM, 2022

work page 2022

[3] [3]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization problems.Siam journal on optimization, 20(6):2833–2852, 2010. Complexity analysis in DF multiobjective optimization 33 Fig. 2Hypervolume representation for the example in Remark 3

work page 2010

[4] [4]

E. G. Birgin, J. L. Gardenghi, J. M. Mart ´ ınez, S. A. Santos, and Ph. L. Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regular- ized models.Mathematical Programming, 163:359–368, 2017

work page 2017

[5] [5]

L. N. Vicente. Worst case complexity of direct search.EURO Journal on Computational Optimization, 1(1):143–153, 2013

work page 2013

[6] [6]

Brilli, M

A. Brilli, M. Kimiaei, G. Liuzzi, and S. Lucidi. Worst case complexity bounds for linesearch-type derivative-free algorithms.Journal of Optimization Theory and Appli- cations, 203(1):419–454, 2024

work page 2024

[7] [7]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization.SIAM Journal on Optimization, 22(1):66–86, 2012

work page 2012

[8] [8]

Cartis, N

C. Cartis, N. I. M. Gould, and Ph. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results. Mathematical Programming, 127(2):245–295, 2011

work page 2011