A Derivative-free Nonmonotone Line-search Technique For Unconstrained Optimization

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. © 2007 Elsevier B.V. All rights reserved.2192383397Alberto, P., Nogueira, F., Rocha, H., Vicente, L.N., Pattern search methods for user-provided points: application to molecular geometry problems (2004) SIAM J. Opt., 14, pp. 1216-1236Allaire, G., (2001) Shape Optimization by the Homogenization Method, , Springer, New YorkBarzilai, J., Borwein, J.M., Two point step size gradient methods (1988) IMA J. Numer. Anal., 8, pp. 141-148Van den Berghen, F., Bersini, H., CONDOR, a new parallel, constrained extension of Powell's UOBYQA algorithm: experimental results and comparison with the DFO algorithm (2005) J. Comput. Appl. Math., 181, pp. 157-175Birgin, E.G., Martínez, J.M., Raydan, M., Inexact spectral gradient method for convex-constrained optimization (2003) IMA J. Numer. Anal., 23, pp. 539-559Brezinski, C., Matos, A.C., A derivation of extrapolation algorithms based on error estimates (1996) J. Comput. Appl. Math., 66, pp. 5-26C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991Broyden, C.G., Quasi-Newton methods and their application to function minimization (1967) Math. Comput., 21, pp. 368-381Byrd, R.H., Khalfan, H.F., Schnabel, R.B., Analysis of a rank-one trust region method (1996) SIAM J. Opt., 6, pp. 1025-1039Conn, A.R., Gould, N.I.M., Toint, P.L., Convergence of quasi-Newton matrices generated by the symmetric rank one update (1991) Math. Programming, 50, pp. 177-195Conn, A.R., Scheinberg, K., Toint, Ph.L., Recent progress in unconstrained nonlinear optimization without derivatives (1997) Math. Programming, 79, pp. 397-414A. L. Custódio, J. E. Dennis Jr., L. N. Vicente, Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer., to appearDavidon, W.C., Variance algorithms for minimization (1968) Comput. J., 10, pp. 406-410Dennis Jr., J.E., Schnabel, R.B., (1983) Numerical Methods for Unconstrained Optimization and Nonlinear Equations, , Prentice-Hall, Englewood Cliffs, NJDiniz-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 (2003) Optimization, 52, pp. 417-440Fiacco, A.V., McCormick, G.P., (1968) Nonlinear Programming: Sequential Unconstrained Minimization Techniques, , Wiley, New YorkFletcher, R., (1987) Practical Methods of Optimization, , Wiley, New YorkGilmore, P., Kelley, C.T., An implicit filtering algorithm for optimization of functions with many local minima (1995) SIAM J. Opt., 5, pp. 269-285Grippo, L., Lampariello, F., Lucidi, S., A nonmonotone line search technique for Newton's method (1986) SIAM J. Numer. Anal., 23, pp. 707-716Haslinger, J., Mäckinen, R.A.E., (2003) Introduction to Shape Optimization: Theory, Approximation, and Computation, , SIAM, Philadelphia, PAKolda, T.G., Lewis, R.M., Torczon, V., Optimization by direct search: new perspectives on some classical and modern methods (2003) SIAM Rev., 45, pp. 385-482La Cruz, W., Martínez, J.M., Raydan, M., Spectral residual method without gradient information for solving large-scale nonlinear systems of equations (2006) Math. Comput., 75, pp. 1449-1466Li, D.H., Fukushima, M., A derivative-free line search and global convergence of Broyden-like method for nonlinear equations (2000) Opt. Methods Software, 13, pp. 181-201Lucidi, S., Sciandrone, M., On the global convergence of derivative-free methods for unconstrained optimization (2002) SIAM J. Opt., 13, pp. 97-116Mohammadi, B., Pironneau, O., (2001) Applied Shape Optimization for Fluids, , Clarendon Press, OxfordMoré, J.J., Garbow, B.S., Hillstrom, K.E., Testing unconstrained optimization software (1981) ACM Trans. Math. Software, 7, pp. 17-41Powell, M.J.D., Direct search algorithms for optimization calculations (1998) Acta Numer., 7, pp. 287-336Powell, M.J.D., On trust region methods for unconstrained minimization without derivatives (2003) Math. Progamming, 97, pp. 605-623Powell, M.J.D., On the use of quadratic models in unconstrained minimization without derivatives (2004) Opt. Methods Software, 19, pp. 399-411Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem (1997) SIAM J. Opt., 7, pp. 26-3