ALGORITHM

Algorithm - An iterative method that generates a sequence of the form x^(k+1) = S_k(A_k(x^k)), where x^0 is given (called the initial point); A_k is an algorithm map that yields a set of policies, given the current point, x^k; and S_k is a selection function (in case A_k has more than one policy in it). Note that the algorithm map and selection function can depend on the iteration number (k). A concrete example is of the form x^(k+1) = x^k + s_k d^k, where s_k is a scalar parameter, called the step size and d^k is a vector, called the direction of change. The step size may require a selection from a line search solution (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 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.