A direct search method for smooth and nonsmooth unconstrained optimization

Abstract

A derivative free frame based method for minimizing~$C^1$ and non-smooth functions is described. A `black-box' function is assumed with gradients being unavailable. The use of frames allows gradient estimates to be formed. At each iteration a ray search is performed either along a direct search quasi-Newton direction, or along the ray through the best frame point. The use of randomly oriented frames and random perturbations is examined, the latter yielding a convergence proof on non-smooth problems. Numerical results on non-smooth problems show that the method is effective, and that, in practice, the random perturbations are more important than randomly orienting the frames. The method is applicable to nonlinear~$\ell_1$ and~$\ell_\infty$ data fitting problems, and other nonsmooth problems. References

• C. Audet and J. E. Dennis Jr, Analysis of generalized pattern searches, SIAM J. Optim., 13 (2003), 889--903. doi:10.1137/S1052623400378742
• C. Audet and J. E. Dennis Jr, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17 (2006), 188--217. doi:10.1137/040603371
• A. Burmen, J. Puhan, and T. Tuma, Grid restrained Nelder Mead Algorithm, Comp. Optim. and Applic. 34 (2006), 359--375. doi:10.1007/s10589-005-3912-z
• F. H. Clarke, Optimization and non-smooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990.
• I. D. Coope and C. J. Price, Frame based methods for unconstrained optimization, J. Optimization Theory Applic., 107 (2000), 261--274. doi:10.1023/A:1026429319405
• I. D. Coope and C. J. Price, Frame based ray search algorithms in unconstrained optimization, J. Optimization Theory Applic., 116 (2003), 359--377. doi:10.1023/A:1022414105888
• C. Davis, Theory of positive linear dependence, American Journal of Mathematics, 76 (1954), 733--746.
• U. M. Garcia-Palomares and J. F. Rodriguez, New sequential and parallel derivative free algorithms for unconstrained minimization, SIAM J. Optim., 13 (2002), 79--96. doi:10.1137/S1052623400370606
• T. G. Kolda, R. M. Lewis, and V. Torczon, Optimization by Direct Search: New perspectives on some classical and modern methods, SIAM Review, 45 (2003), 385--482. doi:10.1137/S003614450242889
• J. J. More, B. S. Garbow, and K. E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software, 7:1 (1981), 17--41.
• C. J. Price and I. D. Coope, Frames and grids in unconstrained and linearly constrained optimization: a non-smooth approach, SIAM J. Optim., 14 (2003), 415--438. doi:10.1137/S1052623402407084
• A. H. G. Rinnooy Kan and G. T. Timmer, Stochastic global optimization methods part I: clustering methods, Math. Prog., 39 (1987), 27--56. doi:10.1007/BF02592070
• A. H. G. Rinnooy Kan and G. T. Timmer, Stochastic global optimization methods part II: multi-level methods, Math. Prog., 39 (1987), 57--78. doi:10.1007/BF02592071
• V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim. 7 (1997), 1--25. doi:10.1137/S1052623493250780
• A. Torn and A. Zilinskas, Global Optimization, Lecture Notes in Computer Science, 350, (1989).
• W.-C. Yu, Positive basis and a class of direct search techniques, Scientia Sinica (Zhongguo Kexue), Special Issue 1 on Mathematics (1979), 53--68.
• S. K. Zavriev, On the global optimization properties of finite difference local descent algorithms, J. Global Optimization, 3 (1993), 67--78. doi:10.1007/BF01100240