Algorithms for Large-Scale Cone and Convex Programs, Saddle-Point Problems and Variational Inequalities

大规模锥凸规划、鞍点问题和变分不等式的算法

• 批准号: 1300221
• 负责人: Renato D. C. Monteiro
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-07-01 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1300221&HistoricalAwards=false
• 关键词: Algorithms; Large; Scale; Cone; Convex

The main focus of this project is on the development and/or complexity analysis of efficient algorithms for solving convex optimization (CO) problems. Many problems in economics, natural sciences and engineering can be formulated as convex optimization (CO) problems. In particular, these include first-order methods with low CPU time and memory space requirements in order to solve extremely large CO instances. This investigation will also lead to the study efficient algorithms in the context of the saddle-point (SP) problem and variational inequalities (VI) due to their close connection to CO. New algorithms for solving CO will be developed by either handling the instance as is, or by reformulating it as a SP problem or VI, and then using an efficient algorithm for solving the reformulation.If successful, the results of this research will lead to: 1) new and/or better algorithms for solving CO problems, and; 2) new complexity results for existing (e.g., augmented Lagrangian penalty) and/or new (e.g., variants of the block-decomposition) methods. As a by-product, this project will also lead to the development of new software packages, which will increase and improve the existing tools available to practitioners for solving CO problems arising in many applications in economics, natural sciences, and engineering.

这个项目的主要重点是开发和/或复杂性分析有效的算法来解决凸优化（CO）问题。经济学、自然科学和工程学中的许多问题都可以表述为凸优化问题。特别是，这些方法包括具有较低CPU时间和内存空间需求的一阶方法，以便解决非常大的CO实例。本研究还将导致在鞍点（SP）问题和变分不等式（VI）的背景下研究有效的算法，因为它们与CO密切相关。解决CO的新算法将通过原样处理实例，或将其重新表述为SP问题或VI，然后使用有效的算法来解决重新表述。如果成功，这项研究的结果将导致：1)新的和/或更好的算法来解决CO问题；2)现有方法（如增广拉格朗日惩罚）和/或新方法（如块分解的变体）的新复杂性结果。作为一个副产品，这个项目也将导致新的软件包的开发，这将增加和改进现有的工具，以供从业者解决在经济、自然科学和工程的许多应用中出现的CO问题。