Algorithms for Large Scale Convex and Cone Programming

大规模凸锥规划算法

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

Many problems in economics, natural sciences and engineering can be formulated in terms of convex optimization (CO) problems. The development of efficient algorithms for solving CO problems is then of paramount importance to handle these applications.In this project, the investigation of two important classes of algorithms for solving CO problems will be continued, namely: interior-point methods (also, called second-order methods) and first-order methods. The latter methods are particularly important for solving CO problems that, due to their huge size, cannot be solved by the first ones. More specifically, the purpose of this project is to investigate the following topics: 1) development of new algorithms and implementations for first-order smooth and non-smooth methods for cone programming (CP) problems; 2) development and implementation of first-order methods for geometric programming problems; 3) investigation of the complexity of first-order algorithms for solving CO problems based on the augmented Lagrangian penalty methods; 4) development of new insights on the geometry of the central path and examination of their impact into the polynomial complexity analysis of second-order methods for CP problems.If successful, this project will lead to the development of new software packages, which will increase and improve the existing tools available to practitioners to handle CO problems originating from many areas of economics, natural sciences, and engineering. For example, geometric programming is a tool commonly used to model many circuit design problems. The development of fast algorithms for geometric programming will have strong impact in the development of higher performance computers, which are important to several applications (e.g., weather prediction).

经济学、自然科学和工程学中的许多问题都可以归结为凸优化问题。开发有效的算法求解CO问题，然后处理这些应用程序是至关重要的。在这个项目中，两个重要类的算法求解CO问题的调查将继续进行，即：邻点方法（也称为二阶方法）和一阶方法。后一种方法对于解决CO问题特别重要，由于其庞大的规模，无法通过第一种方法解决。更具体地说，本项目的目的是研究以下主题：1）锥规划（CP）问题的一阶光滑和非光滑方法的新算法和实现的发展; 2）几何规划问题的一阶方法的发展和实现; 3）研究了基于增广拉格朗日罚方法求解CO问题的一阶算法的复杂性; 4）发展关于中心路径几何的新见解，并检查其对CP问题二阶方法的多项式复杂性分析的影响。如果成功，该项目将导致开发新的软件包，这将增加和改善现有的工具，从业人员处理CO问题，起源于许多领域的经济学，自然科学和工程。例如，几何编程是一种常用于对许多电路设计问题建模的工具。几何规划的快速算法的发展将对更高性能计算机的发展产生强烈的影响，这对若干应用（例如，天气预报）。