Design and Complexity Analysis of Methods for Solving Large-Scale Non-convex and/or Sparse Optimization Problems
Abstract
Since many problems in economics, natural sciences and engineering can be formulated as optimization problems, there is a high and i""ncreasing demand for more efficient algorithms and software packages for solving them. Forexample, large datasets are constantly be""ing created due to the advent of the Internet where large amount of texts, images and videos are made available daily. Optimization"" is a critical tool for extracting useful information from thesedatasets. However, due to their huge size, there is a constant need" to develop ever more efficient methods to solve the mathematical models that handle and extract information from them. Algorithmic advances to be studied in this project sit in the center of the pipeline of data ~ predictive models ~ decision analysis. Coupled w"ith recent advances in statistical learning, as well as rapid rises in computing power and storage, the proposed research will help"" transform our ability to interpret increasingly large, noisy or incomplete datasets; to infer important new knowledge from the data""; and to guide action and policies. They have the potential to impact many facets of our daily lives, including for example transpor""tation, energy and environmental planning. For example, the alternating direction method of multipliers (ADMM) is a simple but power"ful algorithm for efficiently solving distributed optimization problems which appear in applications such as distributed matrix fact"orization, distributed clustering, sparse zero variance discriminant analysis, tensor decomposition, matrix completion, assetalloca"tion and big data set handling. It is basically a decomposition-coordination procedure in which the solutions to small local subproblems are coordinated to find a solution to a large global problem. One of its main features is itspotential to process huge dataset"s in a parallel and/or fully decentralized manner. While ADMM is quite well studied in the context of convex optimization, it is not" so in the non-convex setting. One of the topics of this project is to investigate in the non-convex setting the complexity analyses of: i) multi-block variants of the ADMM where the local subproblems are processed in a parallel manner; and ii) the augmented Lagrangian method and the more general multi-block ADMM without imposing a key assumption commonly used in the literature. More generally", the main focus of this proposal is on the design and analysis of projection type methods for solving large-scale non-convex optimi"zation problems. Another aspect of it lies on the development and complexity analysis of sparsity and/or rank preserving projection type methods for solving large-scale convex optimization problems via non-convex reformulations. In addition to the aforementioned" analysis of the ADMM, this project aims to: (i) design and study the complexity of news variants of the proximal point method for s"olving non-convex optimization problems; and(ii) investigate sparsity and rank preserving projection type methods for solving conve"x optimization problems via non-convex reformulations.As a result, this research will lead to new and improved algorithms and softw""are to solve optimization problems arising in important applications in industry, economics, natural sciences, and engineering.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 23, 2018
- Source ID
- N000141812077
Entities
People
- Renato Monteiro
Organizations
- Georgia Tech Research Corporation
- Office of Naval Research
- United States Navy