SIAM Journal on Optimization · 1997 · 1.3K citations · 11 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationApproximation AlgorithmsConstrained OptimizationGlobal OptimizationNonlinear ProgrammingOptimization TheoryUnconstrained OptimizationApproximate OptimizationConvergenceGlobal Convergence AnalysisNonlinear Convergence AnalysisNonlinear Optimization
The paper introduces an abstract definition of pattern search methods for solving nonlinear unconstrained optimization problems. Using this characterization, the authors establish a global convergence theory that does not require sufficient decrease, enabled by the fact that pattern search iterates lie on a scaled, translated integer lattice. The definition unifies derivative‑free optimization methods and shows that, by relaxing classical step‑acceptance criteria under stronger step‑form conditions, global convergence can still be guaranteed.
We introduce an abstract definition of pattern search methods for solving nonlinear unconstrained optimization problems. Our definition unifies an important collection of optimization methods that neither compute nor explicitly approximate derivatives. We exploit our characterization of pattern search methods to establish a global convergence theory that does not enforce a notion of sufficient decrease. Our analysis is possible because the iterates of a pattern search method lie on a scaled, translated integer lattice. This allows us to relax the classical requirements on the acceptance of the step, at the expense of stronger conditions on the form of the step, and still guarantee global convergence.
11
A Simplex Method for Function Minimization
J. A. Nelder, R. Mead · The Computer Journal · 1965 · 28.9K citations
Variable Metric Method for Minimization
William C. Davidon · SIAM Journal on Optimization · 1991 · 882 citations · Full text