Regional complexity analysis of algorithms for nonconvex smooth optimization
- PDF / 870,101 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 228 Views
Series A
Regional complexity analysis of algorithms for nonconvex smooth optimization Frank E. Curtis1
· Daniel P. Robinson1
Received: 24 August 2018 / Accepted: 12 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract A strategy is proposed for characterizing the worst-case performance of algorithms for solving nonconvex smooth optimization problems. Contemporary analyses characterize worst-case performance by providing, under certain assumptions on an objective function, an upper bound on the number of iterations (or function or derivative evaluations) required until a pth-order stationarity condition is approximately satisfied. This arguably leads to conservative characterizations based on certain objectives rather than on ones that are typically encountered in practice. By contrast, the strategy proposed in this paper characterizes worst-case performance separately over regions comprising a search space. These regions are defined generically based on properties of derivative values. In this manner, one can analyze the worst-case performance of an algorithm independently from any particular class of objectives. Then, once given a class of objectives, one can obtain a tailored complexity analysis merely by delineating the types of regions that comprise the search spaces for functions in the class. Regions defined by first- and second-order derivatives are discussed in detail and example complexity analyses are provided for a few standard first- and second-order algorithms when employed to minimize convex and nonconvex objectives of interest. It is also explained how the strategy can be generalized to regions defined by higher-order derivatives and for analyzing the behavior of higher-order algorithms. Keywords Nonlinear optimization · Nonconvex optimization · Worst-case iteration complexity · Worst-case evaluation complexity · Regional complexity analysis
Supported by the U.S. Department of Energy, Office of Science, Early Career Research Program under Award Number DE–SC0010615 (Advanced Scientific Computing Research), and by the U.S. National Science Foundation under Award Numbers CCF-1740796 and CCF-1618717 (Division of Computing and Communication Foundations) and IIS-1704458 (Division of Information and Intelligent Systems).
B
Frank E. Curtis [email protected] Daniel P. Robinson [email protected]
1
Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA
123
F. E. Curtis, D. P. Robinson
Mathematics Subject Classification 49M37 · 65K05 · 65K10 · 65Y20 · 68Q25 · 90C30 · 90C60
1 Introduction Users of optimization algorithms often choose to employ one algorithm instead of another based on its theoretical properties. One such property of broad interest is worst-case complexity, wherein one measures the resources that an algorithm will require, in the worst case, to solve (approximately) a given problem. In the context of convex optimization [31], such worst-case complexity has for man
Data Loading...
