CAREER: Fundamentals of Low-complexity Relaxations for Nonconvex Optimization Problems with Conic Structure

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This Faculty Early Career Development (CAREER) Program grant will pioneer novel tools for the analysis and design of efficient and scalable algorithms for solving large-scale nonconvex optimization problems with conic constraints. These problems are critical components of operational problems in many diverse fields facing uncertainty such as energy, finance, and telemedicine, and are also frequently used in extracting useful information from high-dimensional data. While convex conic optimization problems are efficiently solvable, the presence of nonconvexities, such as yes/no decisions, present significant new challenges and the state-of-the-art algorithms do not scale well. This award supports foundational research to establish frameworks that overcome these challenges by exploiting valuable structural information in a unified manner. The main developments will address key trade-offs on relaxation quality and computational tractability. If successful, these developments will advance the fundamental tool set in optimization, thus improving the efficiency of operations in a broad range of activities in the aforementioned sectors, having a profound impact on US economy and society. Progress in this vein will provide valuable insights to researchers and practitioners in interdisciplinary domains such as machine learning and high dimensional statistics. The outcomes of this research will be incorporated into commonly used open-source platforms and integrated into the graduate curriculum. These efforts will also go hand-in-hand with synergistic activities to promote operations research among underrepresented groups as well as encourage creative mathematical problem solving skills in K-12 education. This award aims to develop foundational theory to study the key properties of structured non-convex sets and design new efficient algorithms. The focus will be on development of new systemic techniques to generate classes of low-complexity relaxations (expressed in linear or conic form) that are effective and easy to incorporate into existing and/or novel algorithmic frameworks. This research will introduce non-traditional paradigms for incorporating more information into the convexification process from different types of cones, multiple conic structures simultaneously present, and specific sources of nonconvexities such as nonconvex quadratics. Degradation of relaxation quality due to partial information use and resulting computational complexity trade-offs will be rigorously quantified. Whenever possible, these developments will be supplemented with explicit results on convex hull characterizations and accompanied with efficient algorithms based on reduced-complexity optimization methods to further enhance the scalability of this approach. Research findings will be studied in a diverse set of models from a number of interdisciplinary fields