×

zbMATH — the first resource for mathematics

A bundle-Newton method for nonsmooth unconstrained minimization. (English) Zbl 0920.90132
Summary: An algorithm based on a combination of the polyhedral and quadratic approximation is given for finding stationary points for unconstrained minimization problems with locally Lipschitz problem functions that are not necessarily convex or differentiable. Global convergence of the algorithm is established. Under additional assumptions, it is shown that the algorithm generates Newton iterations and that the convergence is superlinear. Some encouraging numerical experience is reported.

MSC:
90C30 Nonlinear programming
49J52 Nonsmooth analysis
Software:
PNEW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cheney, E.W., Goldstein, A.A., 1959. Newton’s method for convex programming and Tchebycheff approximation. Numer. Math 1, 253–268. · Zbl 0113.10703
[2] Clarke, F.H., 1983. Optimization and Nonsmooth Analysis. Wiley-Interscience, New York. · Zbl 0582.49001
[3] Fletcher, R., 1987. Practical Methods of Optimization. Wiley, Chichester. · Zbl 0905.65002
[4] Gill, P.E., Murray, W., 1974. Newton-type methods for unconstrained and linearly constrained optimization. Math. Programming 7, 311–350. · Zbl 0297.90082
[5] Hiriart-Urruty, J.B., Lemarechal, C., 1993. Convex Analysis and Minimization Algorithms I, II. Springer, Berlin.
[6] Kelley, J.E., 1960. The cutting plane method for solving convex programs. SIAM J. 8, 703–712. · Zbl 0098.12104
[7] Kiwiel, K.C., 1985. Methods of descent for nondifferentiable optimization. In: Lecture Notes in Mathematics, vol. 1133, Springer, Berlin. · Zbl 0561.90059
[8] Kiwiel, K.C., 1989. An ellipsoid trust region bundle method for nonsmooth convex minimization. SIAM J. Control Optim. 27, 737–757. · Zbl 0694.65026
[9] Kiwiel, K.C., 1996. Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization. SIAM J. Optim. 6, 227–249. · Zbl 0846.65028
[10] Lemarechal, C., 1978. Nonsmooth optimization and descent methods, Report RR-78-4, International Institute for Applied System Analysis, Laxenburg, Austria. · Zbl 0398.90090
[11] Lukšan, L., 1984. Dual method for solving a special problem of quadratic programming as a subproblem at lineary constrained nonlinear minimar approximation. Kybernetika 20, 445–457.
[12] Mäkelä, M.M., Neittaanmäki, P., 1992. Nonsmooth Optimization. World Scientific, London.
[13] Mifflin, R., 1982. A modification and an extension of Lemarechal’s algorithm for nonsmooth minimization. Math. Programming Study 17, 77–90. · Zbl 0476.65047
[14] Mifflin, R., 1984. Better than linear convergence and safeguarding in nonsmooth minimization. In: Thoft-Christensen, P. (Ed.), System Modelling and Optimization, Springer, New York, pp. 321–330. · Zbl 0548.90059
[15] Mifflin, R., 1992. Ideas for developing a rapidly convergent algorithm for nonsmooth minimization. In: Gianessi, F. (Ed.), Nonsmooth Optimization Methods and Applications. Gordon and Breach, Amsterdam, pp. 228–239. · Zbl 1050.90554
[16] Schramm, H., Zowe, J., 1992. A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2, 121–152. · Zbl 0761.90090
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.