Approximate Level Method for Nonsmooth Convex Minimization

摘要: In this paper, we propose and analyse an approximate variant of the level method Lemarechal, Nemirovskii Nesterov for minimizing nonsmooth convex functions. The main per-iteration work is spent on (i) a piecewise-linear model objective function (ii) projecting onto intersection feasible region set function. We show that, by replacing exact computations in both cases computations, relative scale, theoretical iteration complexity increases only small factor which depends approximation reduces to one case.