PROXIMAL LEVEL BUNDLE METHODS FOR CONVEX NONDIFFERENTIABLE OPTIMIZATION, SADDLE-POINT PROBLEMS AND VARIATIONAL INEQUALITIES

摘要

We study 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. We show that they enjoy almost optimal efficiency estimates. We give extensions for solving convex constrained problems, convex-concave saddle-point problems and variational inequalities with monotone operators. We present several variants, establish their efficiency estimates, and discuss possible implementations. In particular, our methods require bounded storage in contrast to the original level methods of Lemarechal, Nemirovskii and Nesterov. [References: 14]