Optimization Online


Trust-region methods without using derivatives: Worst case complexity and the non-smooth case

R. Garmanjani(nima***at***mat.uc.pt)
D. Júdice(judice.diogo***at***gmail.com)
L. N. Vicente(lnv***at***mat.uc.pt)

Abstract: Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of iterates converging to stationarity independently of the starting point. Most of such an analysis is carried out in the smooth case, and, moreover, little is known about the complexity or global rate of these methods. In this paper, we start by analyzing the worst case complexity of general trust-region derivative-free methods for smooth functions. For the non-smooth case, we propose a smoothing approach, for which we prove global convergence and bound the worst case complexity effort. For the special case of non-smooth functions that result of the composition of smooth and non-smooth/convex components, we show how to improve the existing results of the literature and make them applicable to the general methodology.

Keywords: Trust-region methods, derivative-free optimization, worst case complexity, non-smoothness, smoothing, composite functions.

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: R. Garmanjani, D. Júdice, and L. N. Vicente, Trust-region methods without using derivatives: Worst case complexity and the non-smooth case, preprint 15-03, Dept. Mathematics, Univ. Coimbra, 2015.

Download: [PDF]

Entry Submitted: 01/26/2015
Entry Accepted: 01/26/2015
Entry Last Modified: 01/26/2015

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