CONVERGENCE ANALYSIS OF PERTURBED FEASIBLE DESCENT METHODS

We develop a general approach to convergence analysis of feasible desc ent methods in the presence of perturbations. The important novel feat ure of our analysis is that perturbations need not tend to zero in the limit. In that case, standard convergence analysis techniques are not applicable. Therefore, a new approach is needed. We show that, in the presence of perturbations, a certain epsilon-approximate solution can be obtained, where epsilon depends linearly on the level of perturbat ions. Applications to the gradient projection, proximal minimization, extragradient and incremental gradient algorithms are described.