权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。