Optimization Online


Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

E. G. Birgin (ebirgin***at***ime.isp.br)
J.L. Gardenghi (john***at***ime.isp.br)
J.M. Martinez (martinez***at***ime.unicamp.br)
S.A. Santos (dandra***at***ime.unicamp.br)
Ph. L. Toint (philippe.toint***at***unamur.be)

Abstract: The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p\geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most $O(\epsilon^{-(p+1)/p})$ evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for $p=1$ and $p=2$.

Keywords: Nonlinear optimization, complexity, regularization methods

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Report naXys-05-2015, University of Namur, Namur, Belgium

Download: [PDF]

Entry Submitted: 06/21/2015
Entry Accepted: 06/21/2015
Entry Last Modified: 07/10/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