Optimization Online


Smoothing and Worst Case Complexity for Direct-Search Methods in Non-Smooth Optimization

R. Garmanjani(nima***at***mat)
L. N. Vicente(lnv***at***mat.uc.pt)

Abstract: For smooth objective functions it has been shown that the worst case cost of direct-search methods is of the same order as the one of steepest descent, when measured in number of iterations to achieve a certain threshold of stationarity. Motivated by the lack of such a result in the non-smooth case, we propose, analyze, and test a class of smoothing direct-search methods for the optimization of non-smooth functions. Given a parameterized family of smoothing functions for the non-smooth objective function, this class of methods consists of applying a direct-search algorithm for a fixed value of the smoothing parameter until the step size is relatively small, after which the smoothing parameter is reduced and the process is repeated. One can show that the worst case complexity (or cost) of this procedure is roughly one order of magnitude worse than the one for direct search or steepest descent on smooth functions. The class of smoothing direct-search methods is also showed to enjoy asymptotic global convergence properties. Some preliminary numerical experience indicates that this approach leads to better values of the objective function, pushing in some cases the optimization further, apparently without an additional cost in the number of function evaluations.

Keywords: Derivative-free optimization, direct search, smoothing function, worst case complexity, non-smooth, non-convex.

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Preprint 12-02, Dept. Mathematics, Univ. Coimbra.

Download: [PDF]

Entry Submitted: 01/29/2012
Entry Accepted: 01/29/2012
Entry Last Modified: 01/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society