Stochastic global optimization algorithms: a systematic formal approach

DOI10.1016/J.INS.2018.09.021MaRDI QIDQ2200687zbMATH OpenOpenAlexFDO

Authors Jonatan Gómez

Publication date 22 September 2020

Published in Information Sciences (Search for Journal in Brave)

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

zbMATH Keywords

convergenceMarkov model\(\sigma\)-algebraMarkov kernelstochastic global optimizationoptimization space

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Stochastic programming (90C15)

Abstract: As we know, some global optimization problems cannot be solved using analytic methods, so numeric/algorithmic approaches are used to find near to the optimal solutions for them. A stochastic global optimization algorithm (SGoal) is an iterative algorithm that generates a new population (a set of candidate solutions) from a previous population using stochastic operations. Although some research works have formalized SGoals using Markov kernels, such formalization is not general and sometimes is blurred. In this paper, we propose a comprehensive and systematic formal approach for studying SGoals. First, we present the required theory of probability (sigma-algebras, measurable functions, kernel, markov chain, products, convergence and so on) and prove that some algorithmic functions like swapping and projection can be represented by kernels. Then, we introduce the notion of join-kernel as a way of characterizing the combination of stochastic methods. Next, we define the optimization space, a formal structure (a set with a sigma-algebra that contains strict epsilon-optimal states) for studying SGoals, and we develop kernels, like sort and permutation, on such structure. Finally, we present some popular SGoals in terms of the developed theory, we introduce sufficient conditions for convergence of a SGoal, and we prove convergence of some popular SGoals.

Recommendations

• A new theoretical framework for analyzing stochastic global optimization algorithms
• scientific article; zbMATH DE number 757687
• Stochastic techniques for global optimization: A survey of recent advances
• scientific article; zbMATH DE number 2188971
• Random linkage: A family of acceptance/rejection algorithms for global sation

Cites work

• scientific article; zbMATH DE number 5954252 (Why is no real title available?)
• scientific article; zbMATH DE number 3497315 (Why is no real title available?)
• scientific article; zbMATH DE number 3278887 (Why is no real title available?)
• scientific article; zbMATH DE number 964178 (Why is no real title available?)
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• Differential evolution -- a simple and efficient heuristic for global optimization over continuous spaces
• Discussion on: ``Comparison of practical adaptive algorithms in pH control
• Numerical recipes. The art of scientific computing.
• Probability theory. A comprehensive course
• The Cutting-Plane Method for Solving Convex Programs

Cited in

(4)

• Understanding measure-driven algorithms solving irreversibly ill-conditioned problems
• A new Bayesian approach to global optimization on parametrized surfaces in \(\mathbb{R}^3\)
• On the class of hybrid adaptive evolutionary algorithms (\textsc{chavela})
• scientific article; zbMATH DE number 6869269 (Why is no real title available?)

Describes a project that uses

Uses Software

• SIGOA

This page was built for publication: Stochastic global optimization algorithms: a systematic formal approach

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