Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities

The paper studies proximal level methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. It shows that they enjoy almost optimal efficiency estimates. The paper gives extensions for solving convex constrained problems, convex-concave saddle-point problems and variational inequalities with monotone operators. It presents several variants, establish their efficiency estimates, and discuss possible implementations. In particular, the present methods require bounded storage in contrast to the original level methods of Lemaréchal, Nemirovskii and Nesterov.