Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains

DOI10.1137/140984038zbMath1346.65030arXiv1310.7697OpenAlexW1574994635MaRDI QIDQ3187981

Anne Auger, Nikolaus Hansen

Publication date: 16 August 2016

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

Full work available at URL: https://arxiv.org/abs/1310.7697

zbMATH Keywords

invarianceMarkov chainsMarkov chain Monte Carlolinear convergenceadaptive algorithmsstochastic algorithmsnumerical optimizationderivative-free optimizationcomparison-basedadaptive randomized searchnon-quasi-convex

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Monte Carlo methods (65C05) Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56) Stochastic programming (90C15) Numerical analysis or methods applied to Markov chains (65C40)

Related Items (10)

Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ Scaling-invariant functions versus positively homogeneous functions ⋮ On invariance and linear convergence of evolution strategies with augmented Lagrangian constraint handling ⋮ On geometric convergence rate of Markov search towards the fat target ⋮ On the convergence rate issues of general Markov search for global minimum ⋮ Average convergence rate of evolutionary algorithms in continuous optimization ⋮ Global linear convergence of evolution strategies with recombination on scaling-invariant functions ⋮ Asymptotic estimations of a perturbed symmetric eigenproblem ⋮ Verifiable conditions for the irreducibility and aperiodicity of Markov chains by analyzing underlying deterministic models ⋮ From black-box complexity to designing new genetic algorithms

Uses Software

• NewtonLib
• fminsearch

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variable metric random pursuit
• Log-linear convergence and divergence of the scale-invariant \((1+1)\)-ES in noisy environments
• Markov chains and stochastic stability
• Global convergence for evolution strategies in spherical problems: Some simple proofs and difficulties.
• Evolution strategies. A comprehensive introduction
• Learning probability distributions in continuous evolutionary algorithms -- a comparative review
• Convergence results for the (1,\(\lambda\))-SA-ES using the theory of \(\varphi\)-irreducible Markov chains
• Random gradient-free minimization of convex functions
• Stochastic global optimization.
• Optimization of Convex Functions with Random Pursuit
• Convergence of the Restricted Nelder--Mead Algorithm in Two Dimensions
• Newton Methods for Nonlinear Problems
• On the Convergence of Pattern Search Algorithms
• Principled Design of Continuous Stochastic Search: From Theory to Practice
• The structure of nonlinear control systems possessing symmetries
• `` Direct Search Solution of Numerical and Statistical Problems
• Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions
• Convergence of the Nelder--Mead Simplex Method to a Nonstationary Point
• Analysis of Generalized Pattern Searches
• Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles
• Invariant tracking
• A Simplex Method for Function Minimization
• Foundations of Genetic Algorithms

This page was built for publication: Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains