Parallel Optimization with Input Delays
Abstract
Technological advances in data gathering have led to a rapid proliferation of big data in diverse areas. In order to make sense of this massive amount of data, new computational approaches are needed for scientists and engineers to analyze their data and make decisions. Owing much to the key roles that `1 and other nonsmooth functions play in the areas of statistical and machine learning, neural network training, and image processing, nonsmooth optimization hasbecome a common type of problem in data sciences. With the increasing number of researchers using nonsmoothoptimization in their research, there is a pressing need for solvers that can handle a difficult, important subclass ofproblem: nonsmooth nonseparable optimization.Nonsmooth nonseparable functions (including the indicator functions corresponding to global constraints) arise in avariety of optimization problems: linear and second-order cone programming, the recovery of tree/graph/transformedsparsesignals, and distributed consensus problems. Improved ability for solving large-scale and distributed instancesof these problems will translate to more rapid, accurate information processing and decision making, which areimportant for the Navy applications.The PI proposes a project that focuses on solving a set of large-scale optimization problems that are possibly bothnonsmooth and nonseparable. This proposal encompasses two aspects:(1) Development of parallel algorithms for nonsmooth nonseparable optimization;(2) Development of asynchronous parallel algorithms and their convergence theory.New decomposition methods, coordinate-friendly structures, analysis of iterations with input delays, and an opensourcepackage that implement the algorithms in (1) and (2), will be introduced.Significance and impact. Current state of the art methods have been shown to be inefficient or inapplicable when anonsmooth nonseparable function is introduced to optimization. Hence, modeling big data problems using nonsmoothnonseparable functions has been avoided. While many algorithms have been developed for nonsmooth problems,their efficiency is tied to the separability of the nonsmooth functions. By providing easy-to-use methods, the PI willexpand the solvable problem formulations beyond the typical nonsmooth separable functions such as `1 norm andconstraints on individual (or non-overlapping groups of) variables. The proposed work opens the door for researchersto work on new problems.The developed algorithms will be realized as a computational toolbox and made available on GitHub. The toolboxallows researchers to solve a wide class of problems, to test and refine their theories, and to quickly involve students incurrent research problems. Moreover, the toolbox, which is open-course and well-documented, is extensible andactively developed. Other researchers can add their own features and algorithms to the toolbox.While the problems and algorithms are of great interest to a large scientific community, an expected outcome of thisproject will be the training of the next generation of computational scientists working in optimization-related fields.Researchers and students in mathematics, computer science, and engineering have the necessary background tolearn and use the results of this research. Thus, there is an opportunity to form cross-disciplinary research teams.Furthermore, by having a set of easily used computational tools, it is much easier for undergraduate students toparticipant in research projects through exploring specific examples or conducting numerical experiments. Studentsand postdoctoral researchers working on aspects of this proposal will get valuable research experience designingoptimization algorithms and developing computational software.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 04, 2017
- Source ID
- N000141712162
Entities
People
- Wotao Yin
Organizations
- Office of Naval Research
- United States Navy
- University of California, Los Angeles