Abstract
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 Lemaréchal, Nemirovskii and Nesterov.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
U. Brännlund, “On relaxation methods for nonsmooth convex optimization,” Ph.D. Thesis, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden, 1993.
J.-L. Goffin, A. Haurie and J.-Ph. Vial, “Decomposition and nondifferentiable optimization with the projective algorithm,”Management Science 38 (1992) 284–302.
J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Berlin, 1993).
S. Kim, H. Ahn and S.-C. Cho, “Variable target value subgradient method,”Mathematical Programming 49 (3) (1991) 359–369.
K.C. Kiwiel,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133 (Springer, Berlin, 1985).
K.C. Kiwiel, “Proximity control in bundle methods for convex nondifferentiable minimization,”Mathematical Programming 46 (1) (1990) 105–122.
K.C. Kiwiel, “The efficiency of subgradient projection methods for convex nondifferentiable optimization, part I: General level methods,”SIAM Journal on Control and Optimization, to appear.
K.C. Kiwiel, “Finding normal solutions in piecewise linear programming,”Applied Mathematics and Optimization, to appear.
A.N. Kulikov and V.R. Fazilov, “Convex optimization with prescribed accuracy,”Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki 30 (1990) 663–671 (in Russian).
C. Lemaréchal, A.S. Nemirovskii and Yu.E. Nesterov, “New variants of bundle methods,” Research Report 1508, INRIA, Rocquencourt, France, 1991.
C. Lemaréchal, A. Nemirovskii and Yu. Nesterov, “New variants of bundle methods,”Mathematical Programming 69 (1) (1995) 111–147 (this issue).
J.F. Maurras, K. Truemper and M. Akgül, “Polynomial algorithms for a class of linear programs,”Mathematical Programming 21 (2) (1981) 121–136.
A.S. Nemirovskii and D.B. Yudin,Problem Complexity and Method Efficiency in Optimization (Nauka, Moscow, 1979, in Russian); English translation: (Wiley, New York, 1983).
B.T. Polyak, “Minimization of unsmooth functionals,”Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki 9 (1969) 509–521 (in Russian); English translation:Computational Mathematics and Mathematical Physics 9 (1969) 14–29.
Author information
Authors and Affiliations
Additional information
This research was supported by the Polish Academy of Sciences.
Supported by a grant from the French Ministry of Research and Technology.
Rights and permissions
About this article
Cite this article
Kiwiel, K.C. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Mathematical Programming 69, 89–109 (1995). https://doi.org/10.1007/BF01585554
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585554