Investigations in Interior Point Methods and Convex Programming

内点法和凸规划的研究

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

AbstractThe goal of this project is to develop algorithms and tools for interior point methods. The investigator will continue his ongoing research into interior point methods with the aim of advancing several outstanding topics in semidefinite programming (SDP) and related problems. A better understanding of neighborhoods and paths is needed in SDP, and in programming over a symmetric cone in general. This is necessary in order to develop more efficient algorithms in terms of faster asymptotic convergence and numerical stability. The investigator intends to develop effective mathematical tools to deal with these issues. Programming over homogeneous cones and hyperbolic cones are likely to become the next emerging fields in interior point methods, and there is a need to develop efficient, long-step interior algorithms for such problems. Eventually, interior point methods will need to deal with even more complicated industrial applications which must be solved efficiently. The project will involve all of these areas of interior point methods; efficient algorithms will be devised in all cases, and the needed mathematical tools will be developed. The project also has two other goals. The first is an extension of duality theory beyond its traditional convexity, and the second one is the development of faster proximal point algorithms for convex programming. Interior point methods have been successful in solving many large scale industrial problems in industry: in civil and electrical engineering, management, communication networks, finance, and others. Further applicability of these methods depends on a better understanding of their behavior and continuous development of appropriate software. This project aims to search for efficient algorithms and improved mathematical tools so that large scale optimization problems arising from diverse industrial disciplines can be efficiently solved.

摘要本课题的目标是开发内点法的算法和工具。研究者将继续他正在进行的内点法的研究，目的是推进半确定规划（SDP）和相关问题的几个突出课题。在SDP和一般的对称锥规划中，需要更好地理解邻域和路径。为了在更快的渐近收敛和数值稳定性方面开发更有效的算法，这是必要的。研究者打算开发有效的数学工具来处理这些问题。齐次锥和双曲锥上的规划很可能成为内点法的下一个新兴领域，需要开发有效的、长步的内点法来解决这类问题。最终，内点法将需要处理更复杂的工业应用，这些应用必须得到有效解决。该项目将涉及所有这些领域的内部点法；在所有情况下都将设计有效的算法，并开发所需的数学工具。该项目还有另外两个目标。第一个是对偶理论在其传统凸性之外的扩展，第二个是凸规划中更快的近点算法的发展。内点法已经成功地解决了工业中的许多大规模工业问题：土木和电气工程、管理、通信网络、金融等。这些方法的进一步适用性取决于对其行为的更好理解和适当软件的持续开发。该项目旨在寻找有效的算法和改进的数学工具，从而有效地解决来自不同工业学科的大规模优化问题。