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 -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.

**[1]**A. Auslender,*Programmation Convexe avec Erreurs*:*Methodes*-*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**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0790650-5

Keywords:
Mathematical programming,
nonsmooth optimization,
convex nondifferentiable optimization,
descent methods,
aggregate subgradients

Article copyright:
© Copyright 1985
American Mathematical Society