Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An algorithm for nonsmooth convex minimization with errors

Author: Krzysztof C. Kiwiel
Journal: Math. Comp. 45 (1985), 173-180
MSC: Primary 90C25; Secondary 65K05
MathSciNet review: 790650
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A readily implementable algorithm is given for minimizing any convex, not necessarily differentiable, function f of several variables. At each iteration the method requires only one approximate evaluation of f and its $ \varepsilon $-subgradient, and finds a search direction by solving a small quadratic programming problem. The algorithm generates a minimizing sequence of points, which converges to a solution whenever f has any minimizers.

References [Enhancements On Off] (What's this?)

  • [1] A. Auslender, Programmation Convexe avec Erreurs: Methodes $ d'\varepsilon $-sous Gradients, IX International Symposium on Mathematical Programming (Abstracts), Budapest, 1976.
  • [2] V. F. Dem′yanov and L. V. Vasil′ev, Nedifferentsiruemaya optimizatsiya, \cyr Optimizatsiya i Issledovanie Operatsiĭ. [Optimization and Operations Research], “Nauka”, Moscow, 1981 (Russian). MR 673171
  • [3] R. Gabasov & F. M. Kirilova, Methods of Linear Programming, Part 3, Special Problems, Izdatel'stvo BGU, Minsk, 1980. (Russian)
  • [4] K. C. Kiwiel, Efficient Algorithms for Nonsmooth Optimization and Their Applications, Ph.D. Thesis, Technical University of Warsaw, Warsaw, Poland, 1983. (Polish)
  • [5] Krzysztof Czesław Kiwiel, An aggregate subgradient method for nonsmooth convex minimization, Math. Programming 27 (1983), no. 3, 320–341. MR 725625, 10.1007/BF02591907
  • [6] Krzysztof Czesław Kiwiel, A linearization algorithm for nonsmooth minimization, Math. Oper. Res. 10 (1985), no. 2, 185–194. MR 793877, 10.1287/moor.10.2.185
  • [7] Claude Lemarechal and Robert Mifflin (eds.), Nonsmooth optimization, IIASA Proceedings Series, vol. 3, Pergamon Press, Oxford-New York, 1978. MR 537890
  • [8] Robert Mifflin, A modification and extension of Lemarechal’s algorithm for nonsmooth minimization, Math. Programming Stud. 17 (1982), 77–90. Nondifferential and variational techniques in optimization (Lexington, Ky., 1980). MR 654692
  • [9] B. T. Poljak, A general method for solving extremal problems, Dokl. Akad. Nauk SSSR 174 (1967), 33–36 (Russian). MR 0217997
  • [10] N. Z. Šor, Metody minimizatsii nedifferentsiruemykh funktsii i ikh prilozheniya, “Naukova Dumka”, Kiev, 1979 (Russian). MR 538081
  • [11] Philip Wolfe, A method of conjugate subgradients for minimizing nondifferentiable functions, Math. Programming Stud. 3 (1975), 145–173. Nondifferentiable optimization. MR 0448896

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 90C25, 65K05

Retrieve articles in all journals with MSC: 90C25, 65K05

Additional Information

Keywords: Mathematical programming, nonsmooth optimization, convex nondifferentiable optimization, descent methods, aggregate subgradients
Article copyright: © Copyright 1985 American Mathematical Society