Information-Based Complexity Analysis for Large-Scale Nonlinear Optimization

Clemson University, Clemson SC

Investigators

Abstract

Recent years have seen rapid advances in the fields of data analysis, which has impacts in various disciplines. Optimization has been an important tool in solving problems arising from data analysis applications. Modern applications with large volume datasets and sophisticated data structures bring great challenges to designing scalable and efficient numerical optimization algorithms for large-scale nonlinear optimization problems. While the goal of optimization algorithm design is to solve the problems of interest as efficiently as possible, it is equally important to study the complexity of the problems of interest themselves. In particular, the complexity analysis of a class of nonlinear optimization problems reveals the fundamental performance limits of any algorithms for solving problems in such class. The discovered performance limits would then encourage one to design efficient algorithms that reach such performance limits. First-order methods are a class of numerical optimization algorithms that only need to access the information on function value and first-order derivatives. Due to the computational efficiency and scalability, first-order methods have been widely used to solve large-scale nonlinear optimization problems. This proposal addresses the important question of performance limits of first-order methods through the information-based complexity theory. The problems of interests are nonlinear optimization with different special structures. In order to accelerate computation, many special problem structures have been explored in the literature on algorithm design. By utilizing the problem structure, several newly designed algorithms are able to achieve improved computational performance. However, comparing with the rapidly growing number of new and novel algorithms on structured nonlinear optimization, the complexity analysis and the design of worse-case instances does not match with the advancement in algorithm design. This proposal aims to close some of the aforementioned gaps by constructing several worst-case examples that demonstrate the performance limits of first-order methods, in the hope of broaden the understanding of efficiency of first-order methods and the difficulty of certain nonlinear optimization models. This project is jointly funded by Computational Mathematics Program, DMS/MPS, and the Established Program to Stimulate Competitive Research (EPSCoR). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.