From Glossary

Jump to: navigation, search

An iterative method that generates a sequence of the form LaTeX: x^{k+1} = S_k (A_k (x^k)), where LaTeX: x^0 is given (called the initial point). LaTeX: A_k is an algorithm map that yields a set of policies, given the current point, LaTeX: x^k, and LaTeX: S_k is a selection function (in case LaTeX: A_k has more than one policy). Note that the algorithm map and selection function can depend on the iteration number LaTeX: k. A concrete example is of the form LaTeX: x^{k+1} = x^k + s_k d^k, where LaTeX: s_k is a scalar parameter, called the [1]tep size and LaTeX: d^k is a vector, called the direction of change. The step size may require a selection from a line search if there are many optimal solutions; one is to select the least value (perhaps above some threshold). In practice, algorithms have a variety of tolerances to control its computer representation, progression and termination.

A stochastic algorithm is one whose algorithm map is a random variable. Unlike the meaning in computer science, most people in mathematical programming mean an algorithm whereby an iterate is selected by some random mechanism. One example is simulated annealing. When LaTeX: x^k is a random variable, there is a meaning to convergence that differs from ordinary (deterministic) sequences.

An online algorithm is one that obtains a solution for an online problem. Typically, this is a heuristic that obtains a "good" solution because there is not enough time to guarantee optimality.

Personal tools