Black-Box Complexity of Local Minimization

DOI10.1137/0803004MaRDI QIDQ4697309zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(27)

• Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives
• Efficient unconstrained black box optimization
• Lower bounds for finding stationary points I
• Lower bounds for finding stationary points II: first-order methods
• On the complexity of finding first-order critical points in constrained nonlinear optimization
• A Complexity Analysis of Local Search Algorithms in Global Optimization
• Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
• Black-Box and Data-Driven Computation
• Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• 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
• A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function
• Complexity of general continuous minimization problems: a survey
• Lower bounds for non-convex stochastic optimization
• Recent Theoretical Advances in Non-Convex Optimization
• The complexity of gradient descent: CLS = PPAD pls
• How to trap a gradient flow
• Complexity bounds for second-order optimality in unconstrained optimization
• Gradient descent in the absence of global Lipschitz continuity of the gradients
• No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
• On average complexity of global optimization problems
• The computational complexity of finding stationary points in non-convex optimization
• Fisher information lower bounds for sampling
• On the complexity of finding stationary points of smooth functions in one dimension
• Settling the complexity of Nash equilibrium in congestion games
• The query complexity of local search and Brouwer in rounds

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)