  


Improved secondorder evaluation complexity for unconstrained nonlinear optimization using highorder regularized models
Coralia Cartis(cartismaths.ox.ac.uk) Abstract: The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $p\geq 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first and secondorder critical point in at most $O \left(\max\left( \epsilon_1^{\frac{p+1}{p}}, \epsilon_2^{\frac{p+1}{p1}} \right) \right)$ function and derivatives evaluations, where $\epsilon_1$ and $\epsilon_2 >0$ are prescribed first and secondorder optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding secondorder critical points, and establishes the novel complexity bound for secondorder criticality under identical problem assumptions as for firstorder, namely, that the $p$th derivative tensor is Lipschitz continuous and that $f(x)$ is bounded from below. The evaluationcomplexity bound for secondorder criticality improves on all such known existing results. Keywords: complexity analysis, regularisation methods Category 1: Nonlinear Optimization Citation: Technical Report, University of Oxford, Mathematical Institute, 2017. Download: [PDF] Entry Submitted: 08/13/2017 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  