Сверхлинейно-сходящийся проксимальный метод типа Ньютона для оптимизации конечных сумм

Работа посвящена новому методу минимизации суммы большого числа гладких функций, названному циклическим методом Ньютона. Показано, что при предположениях, аналогичным тем, что используются в классическом анализе сходимости стандартного метода Ньютона, циклический метод Ньютона для минимизации суммы n функций обладает локальной n-шаговой квадратичной сходимостью. Предложенный метод является первым примером инкрементального метода со сверхлинейной сходимостью. Во второй части работы рассматривается обобщение циклического метода Ньютона для задач композитной минимизации, где к сумме большого числа функций дополнительно прибавляется выпуклая добавка. При этом на каждой итерации метода требуется решать вспомогательную квадратичную композитную задачу минимизации, которая в большинстве случаев не имеет точного аналитического решения. Значительное внимание уделяется вопросу о том, с какой точностью нужно решать вспомогательную задачу, чтобы сохранить сверхлинейную сходимость метода.