-

 

 

 




Optimization Online





 

On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Nicholas I.M. Gould(nick.gould***at***stfc.ac.uk)
Philippe L. Toint(philippe.toint***at***unamur.be)

Abstract: When solving the general smooth nonlinear optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy $\epsilon$ can be obtained by a second-order method using cubic regularization in at most $O(\epsilon^{-3/2})$ problem-functions evaluations, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear least-squares. As a consequence, the presence of (possibly nonlinear) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known ($O(\epsilon^{-2})$) evaluation-complexity bound for solving general nonconvexly constrained optimization problems.

Keywords: Nonlinear optimization, evaluation complexity, general constrained problem

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 3: Nonlinear Optimization (Bound-constrained Optimization )

Citation: @techreport{CartGoulToin13a, author={C. Cartis and N. I. M. Gould and Ph. L. Toint}, title = {On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods}, institution = {Namur Center for Complex Systems (NAXYS), University of Namur}, address = {Namur, Belgium}, number = {naXys-01-2013}, year = 2013}

Download: [PDF]

Entry Submitted: 04/03/2013
Entry Accepted: 04/03/2013
Entry Last Modified: 04/03/2013

Modify/Update this entry


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

 

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