Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. (English) Zbl 0857.90101
Summary: 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, Nemirovskij and Nesterov.
Keywords:
nondifferentiable optimization; bundle methods; proximal level methods; convex optimization; convex-concave saddle-point problems; variational inequalities with monotone operatorsReferences:
| [1] | U. Brännlund, ”On relaxation methods for nonsmooth convex optimization,” Ph.D. Thesis, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden, 1993. |
| [2] | J.-L. Goffin, A. Haurie and J.-Ph. Vial, ”Decomposition and nondifferentiable optimization with the projective algorithm,”Management Science 38 (1992) 284–302. · Zbl 0762.90050 · doi:10.1287/mnsc.38.2.284 |
| [3] | J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Berlin, 1993). |
| [4] | S. Kim, H. Ahn and S.-C. Cho, ”Variable target value subgradient method,”Mathematical Programming 49 (3) (1991) 359–369. · Zbl 0825.90754 · doi:10.1007/BF01588797 |
| [5] | K.C. Kiwiel,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133 (Springer, Berlin, 1985). · Zbl 0561.90059 |
| [6] | K.C. Kiwiel, ”Proximity control in bundle methods for convex nondifferentiable minimization,”Mathematical Programming 46 (1) (1990) 105–122. · Zbl 0697.90060 · doi:10.1007/BF01585731 |
| [7] | 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. |
| [8] | K.C. Kiwiel, ”Finding normal solutions in piecewise linear programming,”Applied Mathematics and Optimization, to appear. · Zbl 0838.90094 |
| [9] | 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). · Zbl 0714.90076 |
| [10] | C. Lemaréchal, A.S. Nemirovskii and Yu.E. Nesterov, ”New variants of bundle methods,” Research Report 1508, INRIA, Rocquencourt, France, 1991. |
| [11] | C. Lemaréchal, A. Nemirovskii and Yu. Nesterov, ”New variants of bundle methods,”Mathematical Programming 69 (1) (1995) 111–147 (this issue). · Zbl 0857.90102 · doi:10.1007/BF01585555 |
| [12] | J.F. Maurras, K. Truemper and M. Akgül, ”Polynomial algorithms for a class of linear programs,”Mathematical Programming 21 (2) (1981) 121–136. · Zbl 0509.90056 · doi:10.1007/BF01584235 |
| [13] | 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). |
| [14] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
