An algorithm for nonsmooth convex minimization with errors

Author:
Krzysztof C. Kiwiel

Journal:
Math. Comp. **45** (1985), 173-180

MSC:
Primary 90C25; Secondary 65K05

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

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

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