Low-Complexity Algorithms for Sparse Conic Optimization with Applications to Energy Systems and Machine Learning

稀疏圆锥优化的低复杂度算法及其在能源系统和机器学习中的应用

基本信息

批准号：
1808859
负责人：
Somayeh Sojoudi
金额：
$ 36万
依托单位：
University of California-Berkeley
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-08-15 至 2022-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1808859&HistoricalAwards=false
关键词：
Low Complexity Algorithms Sparse Conic

项目摘要

The development of fast numerical algorithms is crucial for large-scale optimization problems arising in a wide range of areas, such as power systems, machine learning, control theory, transportations and operations research. The main challenge is the inability of the existing methods in handling the nonlinearity (non-convexity) of many real-world problems. Conic optimization is able to solve these nonconvex problems to global optimality in a rigorous and principled manner through the notion of convexification. Despite a mature theory on convexification, the practical use of conic optimization remains limited since this technique greatly increases the dimension of a problem. It is common amongst researchers to view conic optimization as a powerful theoretical tool that is inaccessible for real-world applications, due to the lack of efficient numerical algorithms for conic optimization. The objective of this proposal is to design low-complexity algorithms for conic optimization that directly exploit the structure of a give problem to reduce the complexity. The outcomes of this project will lead to wide-ranging societal impact in all areas of design, analysis, operation, and control in real-world systems. This project has several outreach and educational activities, such as participation in multiple programs for students from underrepresented groups, fostering undergraduate research, and organizing tutorial sessions and workshops. This project develops numerical algorithms for sparse conic optimization by exploiting problem structure, with a particular emphasis on sparse semidefinite programs. The proposed approach uses the notion of tree decomposition to solve sparse problems in near-linear time and linear memory. The main objectives of this proposal are as follows: 1) to identify graph-theoretic structures that control the computational complexity of sparse conic optimization; 2) to design numerical algorithms based on this graphical analysis to achieve best complexities; 3) to develop parallel and distributed versions of these algorithms for real-time computing. This is an interdisciplinary project theoretically underpinned by graph theory, numerical algorithms, matrix completion, conic optimization, low-rank matrix optimization, and algebraic geometry, and finding applications in power systems and machine learning. The proposed project will apply the designed numerical algorithms to nonlinear power optimization problems with tens of thousands of parameters to demonstrate its impact.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.

快速数值算法的开发对于在诸如电力系统，机器学习，控制理论，运输和操作研究等广泛领域产生的大规模优化问题至关重要。主要的挑战是现有方法无法处理许多现实世界中的非线性（非跨性别）。圆锥优化能够通过凸概念以严格而有原则的方式解决这些非概念问题。尽管具有成熟的凸化理论，但锥形优化的实际使用仍然有限，因为该技术大大增加了问题的维度。在研究人员中，由于缺乏有效的数值算法以进行圆锥优化，因此研究人员通常将锥形优化视为一种强大的理论工具，对于现实世界应用而言是无法访问的。该提案的目的是设计低复杂性算法以进行圆锥优化，直接利用给出问题的结构以降低复杂性。该项目的结果将导致在现实世界系统的设计，分析，操作和控制方面的各个领域的社会影响。该项目有几项宣传和教育活动，例如为来自代表性不足的小组的学生参加多个课程，培养本科研究以及组织教程和讲习班。该项目通过利用问题结构来开发用于稀疏圆锥优化的数值算法，并特别着重于稀疏的半决赛程序。提出的方法使用树的分解概念来解决近线性时间和线性记忆中的稀疏问题。该提案的主要目标如下：1）识别控制稀疏圆锥优化计算复杂性的图理论结构； 2）基于此图形分析设计数值算法以达到最佳复杂性； 3）开发这些算法的平行和分布式版本以实时计算。这是一个理论上的跨学科项目，由图理论，数值算法，矩阵完成，圆锥优化，低级别矩阵优化和代数几何形状以及在电力系统和机器学习中找到应用程序。拟议的项目将将设计的数值算法应用于具有数万参数的非线性功率优化问题，以证明其影响。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准通过评估的支持。