Optimal order of accuracy of search algorithms in stochastic optimization (Q749450)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Optimal order of accuracy of search algorithms in stochastic optimization
scientific article

    Statements

    Optimal order of accuracy of search algorithms in stochastic optimization (English)
    0 references
    1990
    0 references
    Consider min\(\{\) f(x): \(x\in Q\subset R^ N\}\) with f: \(R^ N\to R^ 1\). Assume the unique existence of a solution. f is unknown and observations \(y_ n=f(x_ n)+\xi_ n\) with random errors \(\xi_ n\) are possible. The following random search algorithm is discussed: \[ z_ 0=b\quad (given),\quad x_ n=z_{n-1}+h_ n\psi_ n\quad (h_ n>0), \] \[ z_ n=\Pr_{Q_ n}(z_{n-1}-an^{-1}h_ n^{-1}y_ nK(\psi_ n))\quad (a>0), \] where \(\psi_ 1,\psi_ 2,..\). are independent random variables uniformly distributed on [-1/2, \(1/2]^ N\), \(Q_ n=Q\) convex, compact, Pr is the projection operator, K(t) is a vector function with components of the form \[ K_ j(t)=K_ 0(t_ j)\prod^{N}_{m\neq j}\tilde K(t_ m)\quad (j=1,...,N). \] Under some regularity conditions on f it is proved that the convergence order is not higher than \(O(n^{-(\beta -1)/\beta})\) where it is assumed that \[ | f(z)-\sum_{| m| \leq 1}\quad (m!)^{-1}D^ mf(x)(z-x)^ m| \leq L| z-x|^{\beta}. \]
    0 references
    random search algorithm
    0 references
    convergence order
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references