Optimization Online


Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions

Coralai Cartis(coralia.cartis***at***maths.ox.ac.uk)
Nick I. M. Gould( nick.gould***at***stfc.ac.uk)
Philippe L. Toint(philippe.toint***at***unamur.be)

Abstract: We introduce the concept of strong high-order approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite non-smooth 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 q-th-order minimizer in at most O(\max_{1 \leq j \leq q}}\epsilon_j^{-(p+1)/(p-j+1)}) evaluations of the problemís functions and their derivatives, where $\epsilon_j$ is the j-th order accuracy tolerance; this bound applies when either q = 1 or the problem is not composite with q \leq 2. For general non-composite 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 inexpensively-constrained) composite problems for optimality orders exceeding one, but also give the first sharp bounds for high-order strong approximate q-th order minimizers of standard (unconstrained and inexpensively constrained) smooth problems, thereby complementing known results for weak minimizers.

Keywords: composite nonlinear optimization, evaluation complexity, high-order optimality

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Category 3: Nonlinear Optimization (Bound-constrained Optimization )


Download: [PDF]

Entry Submitted: 01/29/2020
Entry Accepted: 01/29/2020
Entry Last Modified: 01/29/2020

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