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

点击翻译按钮获取中文摘要

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.