  


Sharp worstcase evaluation complexity bounds for arbitraryorder nonconvex optimization with inexpensive constraints
Coralia Cartis(coralia.cartismaths.ox.ac.uk) Abstract: We provide sharp worstcase evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e.\ problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexlyconstrained problems. It is shown that, given an accuracy level $\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$ and a desired optimality order $q$ between one and $p$, a conceptual regularization algorithm requires no more than $O(\epsilon^{\frac{p+1}{pq+1}})$ evaluations of the objective function and its derivatives to compute a suitably approximate $q$th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$th derivative is merely H\"{o}lder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worstcase complexity point of view, within a large class of algorithms that use the same derivative information. Keywords: evaluation complexity, regularization algorithm, highorder optimization, sharp bounds, nonconvex optimization, setconstrained problems Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Applications  Science and Engineering (DataMining ) Category 3: Nonlinear Optimization (Nonlinear Systems and LeastSquares ) Citation: Download: [PDF] Entry Submitted: 11/03/2018 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  