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

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. Demyanov & L. V. Vasilyev, Nondifferentiable Optimization, Nauka, Moscow, 1981. (Russian) MR 673171 (84d:49002)
  • [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] K. C. Kiwiel, "An aggregate subgradient method for nonsmooth convex minimization," Math. Programming, v. 27, 1983, pp. 320-341. MR 725625 (85i:90105)
  • [6] K. C. Kiwiel, "A linearization algorithm for nonsmooth minimization," Math. Oper. Res. (To appear.) MR 793877 (86f:90130)
  • [7] C. Lemarechal, Nonsmooth Optimization and Descent Methods, Report No. RR-78-4, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1978. MR 537890 (80d:49002)
  • [8] R. Mifflin, "A modification and an extension of Lemarechal's algorithm for nonsmooth minimization," Nondifferential and Variational Techniques in Optimization (D. C. Sorensen and R. J.-B. Wets, eds.), Mathematical Programming Study 17, North-Holland, Amsterdam, 1982, pp. 77-90. MR 654692 (84d:90094)
  • [9] B. T. Polyak, "A general method for solving extremal problems," Dokl. Akad. Nauk SSSR, v. 174, 1967, pp. 33-36; English transl. in Soviet Math. Dokl., v. 8, 1967, pp. 593-597. MR 0217997 (36:1086)
  • [10] N. Z. Shor, Methods for Minimizing Nondifferentiable Functions and Their Applications, Naukova Dumka, Kiev, 1979. (Russian); English transl., Springer-Verlag, Berlin, 1985. MR 538081 (80f:49024)
  • [11] P. Wolfe, "A method of conjugate subgradients for minimizing nondifferentiable functions," Nondifferentiable Optimization (M. Balinski and P. Wolfe, eds.), Mathematical Programming Study 3, North-Holland, Amsterdam, 1975, pp. 145-173. MR 0448896 (56:7201)

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

American Mathematical Society