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

9623135 Guler这个项目的目标是为大规模的编程问题开发算法并分析它们的性能。研究者将继续他的研究内点法，以寻求答案的几个理论和实践问题有关这些方法。具体问题包括：(1)为一般凸问题开发可行的和接近最优的势垒函数，(2)利用问题可能具有的任何特殊性质来构造具有额外理想性质的势垒函数，(3)利用潜在问题和/或势垒函数的性质开发有效的长步内点法，(4)对已开发的算法进行计算测试，以评估其性能并进一步了解其行为；(5)开发新的工具来分析内点方法。工业中的许多问题都可以表述为大规模优化问题。例如，许多生产、调度（如航空公司机组调度）、计划问题等都可以用线性程序来表述。内点法对这种大规模线性规划的实际影响是显著的。在线性互补问题和最近的半确定规划问题上也取得了类似的成功。后一类问题在工业、工程、经济和许多离散优化难题中也有实际应用。（其中一些应用是意想不到的，可以归因于内部点方法的实际成功。）许多其他工业问题都可以用凸规划来表示。目前，内点法为有效解决这类问题提供了理论希望。研究者将对推进内部点法进行研究，以使这一承诺成为现实。这些进步将直接影响我们解决制造、规划、运输、分销和工程等重大大规模工业问题的能力。

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.