On convergence of a~random search method in convex minimization problems

V. G. Karmanov

Teoriâ veroâtnostej i ee primeneniâ, Tome 19 (1974) no. 4, pp. 817-824

Résumé

In the present paper, the minimization problem is considered for a convex function $\varphi(x)$ on a convex and closed set $X$ of the $n$-dimensional Euclidean space $E_n$, and a method is proposed for constructing a recurrent sequence $x^0,x^1,\dots,\in X$ by the formula $x^{k+1}=x^k+\beta_ks^k$, where $s^k$ is a random vector, and $\beta_k$ is determined so as to minimize $\varphi(x)$ on the straight line $x^k+\beta s^k$ $(|\beta|\infty)$. Under sufficiently general assumptions, it is proved that $$ \mathbf P\{\varphi(x^m)\to\min\varphi(x)\quad(x\in X,\quad m\to\infty)\}=1. $$ In case $X=E_n$, it is proved that $$ \lim_{m\to\infty}\mathbf P\biggl\{\varphi(x^m)-\min\varphi(x)\le\frac cm\biggr\}=1, $$ where $c=\mathrm{const}>0$.