A direct search method for smooth and nonsmooth unconstrained optimization


  • Christopher John Price
  • M. Reale
  • B. L. Robertson




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





Proceedings Computational Techniques and Applications Conference