TY - UNPB
T1 - Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions
AU - Cartis, Coralia
AU - Gould, Nick
AU - Toint, Philippe
PY - 2020/1/30
Y1 - 2020/1/30
N2 - 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.
AB - 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.
KW - nonlinear optimisation
KW - complexity theory
KW - High-order optimality conditions
M3 - Working paper
VL - 2001-10802
BT - Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions
PB - Arxiv
ER -