  


Strong Evaluation Complexity Bounds for ArbitraryOrder Optimization of Nonconvex Nonsmooth Composite Functions
Coralai Cartis(coralia.cartismaths.ox.ac.uk) Abstract: We introduce the concept of strong highorder approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite nonsmooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is shown that using a model of degree p, this algorithm will find a strong approximate qthorder minimizer in at most O(\max_{1 \leq j \leq q}}\epsilon_j^{(p+1)/(pj+1)}) evaluations of the problem’s functions and their derivatives, where $\epsilon_j$ is the jth order accuracy tolerance; this bound applies when either q = 1 or the problem is not composite with q \leq 2. For general noncomposite problems, even when the feasible set is nonconvex, the bound becomes O(\max_{1\leq j\leq q}\epsilon_j^{q(p+1)/p}) evaluations. If the problem is composite, and either q > 1 or the feasible set is not convex, the bound is then O(\max_{1\leq j\leq q}\epsilon_j^{(q+1)}) evaluations. These results not only provide, to our knowledge, the first known bound for (unconstrained or inexpensivelyconstrained) composite problems for optimality orders exceeding one, but also give the first sharp bounds for highorder strong approximate qth order minimizers of standard (unconstrained and inexpensively constrained) smooth problems, thereby complementing known results for weak minimizers. Keywords: composite nonlinear optimization, evaluation complexity, highorder optimality Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Nonlinear Optimization (Unconstrained Optimization ) Category 3: Nonlinear Optimization (Boundconstrained Optimization ) Citation: Download: [PDF] Entry Submitted: 01/29/2020 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  