Mathematical Sciences: Interior Point Methods for Convex Programming--Theory and Applications

数学科学：凸规划的内点方法--理论与应用

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

9623135 Guler The object of this project is to develop algorithms for large scale programming problems and to analyze their performance. The investigator will continue his research in interior point methods in order to seek answers to several theoretical and practical issues concerning these methods. Particular issues include: (1) developing workable and near optimal barrier functions for general convex problems, (2) using any special property a problem might have in order to construct barrier functions with additional desirable properties, (3) developing efficient long--step interior point methods by taking advantage of the properties of the underlying problem and/or the barrier function, (4) computational testing of the developed algorithms in order to gauge their performance and gain additional insight into their behavior, and (5) developing new tools to analyze interior point methods. Many problems in industry can be formulated as large scale optimization problems. For example, many production, scheduling (such as airline crew scheduling), planning problems, etc. can be formulated as linear programs. The practical impact of interior point methods on such large scale linear programs have been phenomenal. This has been followed by similar successes in linear complementarity problems, and more recently in semi-- definite programming. The latter problems also have practical applications in industry, engineering, economics, and in many hard problems in discrete optimization. (Some of these applications have been unexpected, and can be attributed to the practical success of interior point methods.) Many other industrial problems can be posed as convex programs. At present, interior point methods provide the theoretical promise to solve such problems efficiently. The investigator will perform research towards advancing interior point methods in order to make this promise a reality. These advances will have a direct effect on our a bility to solve important large scale industrial problems in manufacturing, planning, transportation, distribution, and engineering.

小行星9623135 这个项目的目标是开发大规模的算法 编程问题，并分析其性能。 研究者 他将继续研究内点法，以寻求答案 关于这些方法的几个理论和实践问题。 具体问题包括：（1）制定可行的和接近最佳的屏障 函数的一般凸问题，（2）使用任何特殊性质a 问题可能是为了构造具有额外的 （3）开发高效的长台阶内点 方法通过利用基本问题的属性 和/或屏障功能，（4）开发的计算测试 算法，以衡量其性能并获得更多的洞察力 （5）开发新的工具来分析内部点 方法. 工业中的许多问题都可以归结为大规模优化问题 问题 例如，许多生产、调度（如航空公司机组人员） 调度）、规划问题等可以用公式表示为线性规划。 内点法对此类大规模线性方程组的实际影响 节目都很精彩 随后，类似 在线性互补问题上的成功，以及最近在半定规划中的成功。 后面的问题也有实际应用 在工业、工程、经济以及许多离散的难题中， 优化. (Some这些应用程序中的一些是意想不到的， 这归功于内点方法的实际成功。 许多其他 工业问题可以看作是凸规划。 目前，内地 点方法为解决这类问题提供了理论保证 有效地 研究人员将进行研究， 内点方法，以使这一承诺成为现实。 这些进步将对我们解决重大问题的能力产生直接影响。 在制造业、规划、运输、 分销和工程。