Title :
Particle Filtering Framework for a Class of Randomized Optimization Algorithms
Author :
Zhou, Eric ; Fu, Michael C. ; Marcus, Steven I.
Author_Institution :
H. Milton Stewart Sch. of Ind. & Syst. Eng., Georgia Inst. of Technol., Atlanta, GA, USA
Abstract :
We reformulate a deterministic optimization problem as a filtering problem, where the goal is to compute the conditional distribution of the unobserved state given the observation history. We prove that in our formulation the conditional distribution converges asymptotically to a degenerate distribution concentrated on the global optimum. Hence, the goal of searching for the global optimum can be achieved by computing the conditional distribution. Since this computation is often analytically intractable, we approximate it by particle filtering, a class of sequential Monte Carlo methods for filtering, which has proven convergence in “tracking” the conditional distribution. The resultant algorithmic framework unifies some randomized optimization algorithms and provides new insights into their connection.
Keywords :
Monte Carlo methods; optimisation; particle filtering (numerical methods); randomised algorithms; statistical distributions; conditional distribution; deterministic optimization problem; filtering problem; observation history; particle filtering framework; randomized optimization algorithms; sequential Monte Carlo methods; Approximation algorithms; Convergence; Estimation; Kernel; Monte Carlo methods; Noise; Optimization; Cross-entropy method; particle filtering; randomized optimization;
Journal_Title :
Automatic Control, IEEE Transactions on
DOI :
10.1109/TAC.2013.2281132