Gradient-Based Adaptive Stochastic Search for Non-Differentiable Optimization

Abstract

In this paper, we propose a stochastic search algorithm for solving general optimization problems with little structure. The algorithm iteratively finds high quality solutions by randomly sampling candidate solutions from a parameterized distribution model over the solution space. The basic idea is to convert the original (possibly non-differentiable) problem into a differentiable optimization problem on the parameter space of the parameterized sampling distribution, and then use a direct gradient search method to find improved sampling distributions. Thus, the algorithm combines the robustness feature of stochastic search from considering a population of candidate solutions with the relative fast convergence speed of classical gradient methods by exploiting local differentiable structures. We analyze the convergence and converge rate properties of the proposed algorithm, and carry out numerical study to illustrate its performance.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 22, 2012
Accession Number
ADA575380

Entities

People

  • Enlu Zhou
  • Jiaqiao Hu

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Asymptotic Normality
  • Convergence
  • Differential Equations
  • Equations
  • Estimators
  • Mathematics
  • Optimization
  • Probabilistic Models
  • Probability
  • Probability Density Functions
  • Probability Distributions
  • Random Variables
  • Sampling
  • Statistical Algorithms
  • Systems Engineering

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space