×

zbMATH — the first resource for mathematics

Globally convergent limited memory bundle method for large-scale nonsmooth optimization. (English) Zbl 1278.90451
Summary: Many practical optimization problems involve nonsmooth (that is, not necessarily differentiable) functions of thousands of variables. In the authors’ paper [Optim. Methods Softw. 19, No. 6, 673–692 (2004; Zbl 1068.90101)] we have described an efficient method for large-scale nonsmooth optimization. In this paper, we introduce a new variant of this method and prove its global convergence for locally Lipschitz continuous objective functions, which are not necessarily differentiable or convex. In addition, we give some encouraging results from numerical experiments.

MSC:
90C56 Derivative-free methods and methods using generalized derivatives
65K10 Numerical optimization and variational techniques
90C30 Nonlinear programming
Software:
L-BFGS; LDGB; NSOLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacaud, L., Lemaréchal, C., Renaud, A., Sagastizábal, C.: Bundle methods in stochastic optimal power management: A disaggregated approach using preconditioners. Comput. Optim. Appl. 20 (3), 227–244 (2001) · Zbl 0990.90085 · doi:10.1023/A:1011202900805
[2] Bihain, A.: Optimization of upper semidifferentiable functions. J. Optimization Theory Appl. 4, 545–568 (1984) · Zbl 0534.90069 · doi:10.1007/BF00938396
[3] Byrd, R.H., Nocedal, J., Schnabel, R.B.: Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63, 129–156 (1994) · Zbl 0809.90116 · doi:10.1007/BF01582063
[4] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York, 1983 · Zbl 0582.49001
[5] Clarke, F.H., Ledyaev, Y.S., Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Springer, New York, 1998 · Zbl 1047.49500
[6] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[7] Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley and Sons, Chichester, 1987 · Zbl 0905.65002
[8] Gilbert, J.C., Lemaréchal, C.: Some numerical experiments with variable-storage quasi-Newton algorithms. Math. Program. 45, 407–435 (1989) · Zbl 0694.90086 · doi:10.1007/BF01589113
[9] Gröwe-Kuska, N., Kiwiel, K.C., Nowak, M.P., Römisch, W., Wegner, I.: Power management in a hydro-thermal system under uncertainty by Lagrangian relaxation. In: C. Greengard, A. Ruszczynski (eds.) Decision Making under Uncertainty: Energy and Power, IMA Volumes in Mathematics and its Applications, vol. 128, Springer, New York, 2002, pp. 39–70 · Zbl 1079.90550
[10] Haarala, M.: Large-scale nonsmooth optimization: Variable metric bundle method with limited memory. Ph.D. thesis, University of Jyväskylä, Department of Mathematical Information Technology (2004) · Zbl 1068.90101
[11] Haarala, M., Miettinen, K., Mäkelä, M.M.: New limited memory bundle method for large-scale nonsmooth optimization. Optim. Methods Softw. 19 (6), 673–692 (2004) · Zbl 1068.90101
[12] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II. Springer-Verlag, Berlin, 1993 · Zbl 0795.49002
[13] Kärkkäinen, T., Majava, K., Mäkelä, M.M.: Comparison of formulations and solution methods for image restoration problems. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing, B 14/2000 University of Jyväskylä, Jyväskylä (2000)
[14] Kärkkäinen, T., Majava, K., Mäkelä, M.M.: Comparison of formulations and solution methods for image restoration problems. Inverse Probl. 17 (6), 1977–1995 (2001) · Zbl 1016.94004 · doi:10.1088/0266-5611/17/6/326
[15] Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics 1133. Springer-Verlag, Berlin, 1985 · Zbl 0561.90059
[16] Kiwiel, K.C.: A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6, 137–152 (1986) · Zbl 0603.65041 · doi:10.1093/imanum/6.2.137
[17] Lemaréchal, C.: Nondifferentiable optimization. In: G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (eds.) Optimization. Elsevier North-Holland, Inc., New York, 1989, pp. 529–572 · Zbl 0683.90079
[18] Lemaréchal, C., Strodiot, J.J., Bihain, A.: On a bundle algorithm for nonsmooth optimization. In: O.L. Mangasarian, R.R. Mayer, S.M. Robinson (eds.) Nonlinear Programming. Academic Press, New York, 1981, pp. 285–281 · Zbl 0533.49023
[19] Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116
[20] Lukšan, L., Vlček, J.: Globally convergent variable metric method for convex nonsmooth unconstrained minimization. J. Optimization Theory Appl. 102, 593–613 (1999) · Zbl 0955.90102 · doi:10.1023/A:1022650107080
[21] Mäkelä, M.M.: Issues of implementing a Fortran subroutine package NSOLIB for nonsmooth optimization. Technical Report 5/1993, Department of Mathematics, Laboratory of Scientific Computing, University of Jyväskylä (1993)
[22] Mäkelä, M.M.: Survey of bundle methods for nonsmooth optimization. Optim. Methods Softw. 17 (1), 1–29 (2002) · Zbl 1050.90027 · doi:10.1080/10556780290027828
[23] Mäkelä, M.M., Miettinen, M., Lukšan, L., Vlček, J.: Comparing nonsmooth nonconvex bundle methods in solving hemivariational inequalities. J. Glob. Optim. 14, 117–135 (1999) · Zbl 0947.90125 · doi:10.1023/A:1008282922372
[24] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore, 1992 · Zbl 0757.49017
[25] Mifflin, R.: A modification and an extension of Lemaréchal’s algorithm for nonsmooth minimization. Math. Program. Study 17, 77–90 (1982) · Zbl 0476.65047
[26] Mistakidis, E.S., Stavroulakis, G.E.: Nonconvex Optimization in Mechanics. Smooth and Nonsmooth Algorithms, Heuristics and Engineering Applications by the F.E.M. Kluwert Academic Publishers, Dordrecht, 1998 · Zbl 0918.73002
[27] Moreau, J.J., Panagiotopoulos, P.D., Strang, G. (eds.): Topics in Nonsmooth Mechanics. Birkhäuser Verlag, Basel, 1988 · Zbl 0646.00014
[28] Naniewicz, Z., Panagiotopoulos, P.D.: Mathematical Theory of Hemivariational Inequalities and Applications. Marcel Dekker, New York, 1995 · Zbl 0968.49008
[29] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35 (151), 773–782 (1980) · Zbl 0464.65037
[30] Nowak, M.P., Nürnberg, R., Römisch, W., Schultz, R., Westphalen, M.: Stochastic programming for power production and trading under uncertainty. In: W. Jäger, H.J. Krebs (eds.) Mathematics — Key Technology for the Future. Springer, Berlin, 2003, pp. 623–636 · Zbl 1161.90451
[31] Outrata, J., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems With Equilibrium Constraints. Theory, Applications and Numerical Results. Kluwert Academic Publisher, Dordrecht, 1998 · Zbl 0947.90093
[32] Panagiotopoulos, P.D.: Hemivariational Inequalities. Springer-Verlag, New York, 1993 · Zbl 0826.73002
[33] Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2 (1), 121–152 (1992) · Zbl 0761.90090 · doi:10.1137/0802008
[34] Vlček, J., Lukšan, L.: Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. J. Optimization Theory Appl. 111 (2), 407–430 (2001) · Zbl 1029.90060
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.