×

A derivative-free nonmonotone line-search technique for unconstrained optimization. (English) Zbl 1149.65041

Authors’ summary: A tolerant derivative-free nonmonotone line-search technique is proposed and analyzed. Several consecutive increases in the objective function and also nondescent directions are admitted for unconstrained minimization. To exemplify the power of this new line search we describe a direct search algorithm in which the directions are chosen randomly. The convergence properties of this random method rely exclusively on the line-search technique.
We present numerical experiments, to illustrate the advantages of using a derivative-free nonmonotone globalization strategy, with approximated-gradient type methods and also with the inverse SR1 update that could produce nondescent directions. In all cases we use a local variation finite differences approximation to the gradient.

MSC:

65K05 Numerical mathematical programming methods
90C56 Derivative-free methods and methods using generalized derivatives
90C30 Nonlinear programming

Software:

COBYLA2; DFO; CONDOR; minpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alberto, P.; Nogueira, F.; Rocha, H.; Vicente, L. N., Pattern search methods for user-provided points: application to molecular geometry problems, SIAM J. Opt., 14, 1216-1236 (2004) · Zbl 1079.90126
[2] Allaire, G., Shape Optimization by the Homogenization Method (2001), Springer: Springer New York
[3] Barzilai, J.; Borwein, J. M., Two point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055
[4] Van den Berghen, F.; Bersini, H., CONDOR, a new parallel, constrained extension of Powell’s UOBYQA algorithm: experimental results and comparison with the DFO algorithm, J. Comput. Appl. Math., 181, 157-175 (2005) · Zbl 1072.65088
[5] Birgin, E. G.; Martínez, J. M.; Raydan, M., Inexact spectral gradient method for convex-constrained optimization, IMA J. Numer. Anal., 23, 539-559 (2003) · Zbl 1047.65042
[6] Brezinski, C.; Matos, A. C., A derivation of extrapolation algorithms based on error estimates, J. Comput. Appl. Math., 66, 5-26 (1996) · Zbl 0854.65002
[7] C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991.; C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991. · Zbl 0744.65004
[8] Broyden, C. G., Quasi-Newton methods and their application to function minimization, Math. Comput., 21, 368-381 (1967) · Zbl 0155.46704
[9] Byrd, R. H.; Khalfan, H. F.; Schnabel, R. B., Analysis of a rank-one trust region method, SIAM J. Opt., 6, 1025-1039 (1996) · Zbl 0923.65035
[10] Conn, A. R.; Gould, N. I.M.; Toint, P. L., Convergence of quasi-Newton matrices generated by the symmetric rank one update, Math. Programming, 50, 177-195 (1991) · Zbl 0737.90062
[11] Conn, A. R.; Scheinberg, K.; Toint, Ph. L., Recent progress in unconstrained nonlinear optimization without derivatives, Math. Programming, 79, 397-414 (1997) · Zbl 0887.90154
[12] A. L. Custódio, J. E. Dennis Jr., L. N. Vicente, Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer., to appear.; A. L. Custódio, J. E. Dennis Jr., L. N. Vicente, Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer., to appear.
[13] Davidon, W. C., Variance algorithms for minimization, Comput. J., 10, 406-410 (1968) · Zbl 0155.19804
[14] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[15] Diniz-Ehrhardt, M. A.; Gomes-Ruggiero, M. A.; Lopes, V. L.R.; Martínez, J. M., Discrete Newton’s method with local variations and global convergence for nonlinear equations, Optimization, 52, 417-440 (2003) · Zbl 1098.90069
[16] Fiacco, A. V.; McCormick, G. P., Nonlinear Programming: Sequential Unconstrained Minimization Techniques (1968), Wiley: Wiley New York · Zbl 0193.18805
[17] Fletcher, R., Practical Methods of Optimization (1987), Wiley: Wiley New York · Zbl 0905.65002
[18] Gilmore, P.; Kelley, C. T., An implicit filtering algorithm for optimization of functions with many local minima, SIAM J. Opt., 5, 269-285 (1995) · Zbl 0828.65064
[19] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23, 707-716 (1986) · Zbl 0616.65067
[20] Haslinger, J.; Mäckinen, R. A.E., Introduction to Shape Optimization: Theory, Approximation, and Computation (2003), SIAM: SIAM Philadelphia, PA · Zbl 1020.74001
[21] Kolda, T. G.; Lewis, R. M.; Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482 (2003) · Zbl 1059.90146
[22] La Cruz, W.; Martínez, J. M.; Raydan, M., Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comput., 75, 1449-1466 (2006)
[23] Li, D. H.; Fukushima, M., A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Opt. Methods Software, 13, 181-201 (2000) · Zbl 0960.65076
[24] Lucidi, S.; Sciandrone, M., On the global convergence of derivative-free methods for unconstrained optimization, SIAM J. Opt., 13, 97-116 (2002) · Zbl 1027.90112
[25] Mohammadi, B.; Pironneau, O., Applied Shape Optimization for Fluids (2001), Clarendon Press: Clarendon Press Oxford · Zbl 0970.76003
[26] Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 17-41 (1981) · Zbl 0454.65049
[27] Powell, M. J.D., Direct search algorithms for optimization calculations, Acta Numer., 7, 287-336 (1998) · Zbl 0911.65050
[28] Powell, M. J.D., On trust region methods for unconstrained minimization without derivatives, Math. Progamming, 97, 605-623 (2003) · Zbl 1106.90382
[29] Powell, M. J.D., On the use of quadratic models in unconstrained minimization without derivatives, Opt. Methods Software, 19, 399-411 (2004) · Zbl 1140.90513
[30] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Opt., 7, 26-33 (1997) · Zbl 0898.90119
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.