Efficient Algorithms for Large Scale Convex Programming

大规模凸规划的高效算法

• 批准号: 0411955
• 负责人: Osman Guler
• 金额: $ 24万
• 依托单位: University of Maryland Baltimore County
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0411955&HistoricalAwards=false
• 关键词: Efficient; Algorithms; Large; Scale; Convex

The goal of this project is to analyze and develop algorithms for large scale convex programming problems. The principal investigator will extend the scope of interior point methods by developing invariant, primal and dual interior point methods over homogeneous cones, which form a large class of problems including linear programming, semidefinite programming, and second order cone programming. Homogeneous cones have rich symmetry properties and a classification theory, which make them an ideal candidate for extending the theory of structured interior point methods beyond semidefinite programming. The investigation of the modeling power of homogeneous cone programming will be an important part of the project, and several related topics in semidefinite programming and hyperbolic cone programming will also be investigated. A second, but related component of this project will be the development of provably efficient first order methods for large scale convex programming. These methods have low memory requirements and global convergence rates which are (nearly) independent of the dimension of the underlying optimization problem. Hence, they are attractive for solving very large scale problems for which interior point methods may be ineffective because of their extensive memory requirements. The principal investigator and his graduate students will seek answers to these and related problems in convex programming. The resulting algorithms will be numerically tested in order to confirm their effectiveness.Numerous problems from industry, engineering, and science (designs of VLSI, antenna arrays, truss structures, and control systems in engineering, portfolio analysis in finance, structure of molecules in quantum chemistry, combinatorial optimization, and many others) depend on efficient optimization algorithms for their resolution. Semidefinite programming (SDP) has proved to be an excellent framework in which to model most of these large scale problems, and interior point methods for SDP have been very successful in solving them numerically. Very large scale problems arising from medical imaging and quantum chemistry provide good incentives for developing first order methods for convex programming. The theoretical insights gained from this research will lead to a deeper understanding of interior point methods for semidefinite programming and beyond. These insights will enable the principal investigator, his students, and other researchers to develop faster, more reliable algorithms which will make it possible to model and solve larger problems. These advances will directly benefit researchers in diverse scientific fields, who rely on modern optimization techniques to solve their problems, by providing them with a set of state of the art algorithms. The research of this project will help advance the frontiers of scientific research in convex programming, and will be incorporated into undergraduate and graduate teaching whenever possible.

这个项目的目标是分析和开发大规模凸规划问题的算法。主要研究者将通过开发均匀锥上的不变，原始和对偶内点方法来扩展内点方法的范围，这些方法形成了一大类问题，包括线性规划，半定规划和二阶锥规划。 齐次锥具有丰富的对称性和分类理论，这使得它们成为将结构内点方法理论扩展到半定规划之外的理想候选者。 齐次锥规划的建模能力的调查将是该项目的重要组成部分，半定规划和双曲锥规划的几个相关主题也将进行调查。第二，但相关的组成部分，这个项目将是可证明有效的一阶方法的发展，大规模凸规划。 这些方法具有较低的内存需求和全局收敛速度，这是（几乎）独立的基本优化问题的尺寸。因此，他们是有吸引力的解决非常大规模的问题，内点方法可能是无效的，因为他们广泛的内存需求。 首席研究员和他的研究生将寻求答案，这些问题和相关的凸规划。 许多工业、工程和科学领域的问题（如超大规模集成电路、天线阵列、桁架结构和工程控制系统的设计，金融领域的投资组合分析，量子化学中的分子结构，组合优化等）都依赖于高效的优化算法来解决。 半定规划（SDP）已被证明是一个很好的框架，在其中建模大多数这些大规模的问题，和SDP的内点方法已经非常成功地解决它们的数值。 医学成像和量子化学中的超大规模问题为凸规划的一阶方法的发展提供了良好的激励。 从本研究中获得的理论见解将导致更深入的了解半定规划的内点方法和超越。 这些见解将使首席研究员，他的学生和其他研究人员能够开发更快，更可靠的算法，这将使建模和解决更大的问题成为可能。 这些进步将直接使不同科学领域的研究人员受益，他们依靠现代优化技术来解决他们的问题，为他们提供一套最先进的算法。本项目的研究将有助于推进凸规划的科学研究前沿，并将尽可能纳入本科和研究生教学。