O método do gradiente conjugado estocástico

Abstract

In this work, we develop stochastic linear and nonlinear conjugate gradient methods, establishing, based on probability theory, almost sure convergence and convergence rate analysis for the solution of stochastic optimization problems. For these results, we employ the concept of nonnegative quasi-supermartingales, introduced by Robbins and Siegmund (1971), which generalizes the concept of nonnegative supermartingales. Regarding the convergence rate analysis of the proposed stochastic linear method, we obtain a rate of order $O\bigg(\dfrac{1}{k\log k}\bigg)$, which is superior to that of the Robbins-Monro method, whose convergence rate is $O\bigg(\dfrac{1}{k}\bigg)$, for the same class of problems analysed. Subsequently, we develop a stochastic version of the nonlinear conjugate gradient method, whose main features, in the proofs of almost sure convergence and convergence rate analysis, include the use of estimates of the gradient and the objective function values and, in particular, the adoption of a line search satisfying the Armijo condition, which is less restrictive than the Wolfe condition.