Please use this identifier to cite or link to this item:
Title: Convergence of Trust-Region Methods Based on Probabilistic Models
Authors: Bandeira, A. S. 
Scheinberg, K. 
Vicente, Luís Nunes 
Issue Date: 2014
Publisher: Society for Industrial and Applied Mathematics (SIAM)
Project: PEst-C/MAT/UI0324/2011 
Serial title, monograph or event: SIAM Journal on Optimization
Volume: 24
Issue: 3
Abstract: In this paper we consider the use of probabilistic or random models within a classical trust-region framework for optimization of deterministic smooth general nonlinear functions. Our method and setting differs from many stochastic optimization approaches in two principal ways. Firstly, we assume that the value of the function itself can be computed without noise, in other words, that the function is deterministic. Second, we use random models of higher quality than those produced by the usual stochastic gradient methods. In particular, a first order model based on random approximation of the gradient is required to provide sufficient quality of approximation with probability $\geq 1/2$. This is in contrast with stochastic gradient approaches, where the model is assumed to be “correct” only in expectation. As a result of this particular setting, we are able to prove convergence, with probability one, of a trust-region method which is almost identical to the classical method. Moreover, the new method is simpler than its deterministic counterpart as it does not require a criticality step. Hence we show that a standard optimization framework can be used in cases when models are random and may or may not provide good approximations, as long as “good” models are more likely than “bad” models. Our results are based on the use of properties of martingales. Our motivation comes from using random sample sets and interpolation models in derivative-free optimization. However, our framework is general and can be applied with any source of uncertainty in the model. We discuss various applications for our methods in the paper.
DOI: 10.1137/130915984
Rights: openAccess
Appears in Collections:I&D CMUC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
random_tr.pdf403.1 kBAdobe PDFView/Open
Show full item record


checked on Jun 25, 2019


checked on Jun 25, 2019

Page view(s) 50

checked on Oct 15, 2019


checked on Oct 15, 2019

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.