Black-Box Complexity of Local Minimization

DOI10.1137/0803004zbMATH Open0794.90045OpenAlexW2056243826MaRDI QIDQ4697309FDOQ4697309

Authors: Stephen A. Vavasis 

Publication date: 29 June 1993

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6972

Recommendations

• scientific article; zbMATH DE number 429516
• Local optimization on graphs
• Black-box complexity for bounding the performance of randomized search heuristics
• A Complexity Analysis of Local Search Algorithms in Global Optimization
• Complexity of general continuous minimization problems: a survey

zbMATH Keywords

black-box modelcomplexity of local minimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (21)

• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• How to trap a gradient flow
• A Complexity Analysis of Local Search Algorithms in Global Optimization
• On average complexity of global optimization problems
• Gradient descent in the absence of global Lipschitz continuity of the gradients
• On the complexity of finding first-order critical points in constrained nonlinear optimization
• Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
• Lower bounds for finding stationary points I
• Lower bounds for finding stationary points II: first-order methods
• Lower bounds for non-convex stochastic optimization
• No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
• Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives
• Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
• On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods
• Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
• Recent Theoretical Advances in Non-Convex Optimization
• Complexity bounds for second-order optimality in unconstrained optimization
• A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function
• Efficient unconstrained black box optimization
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• Complexity of general continuous minimization problems: a survey

This page was built for publication: Black-Box Complexity of Local Minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4697309)