Interior-Point Algorithms: Theories and Applications

内点算法：理论与应用

• 批准号: 9522507
• 负责人: Yinyu Ye
• 金额: $ 19.5万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-01 至 1999-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9522507&HistoricalAwards=false
• 关键词: Interior; Point; Algorithms; Theories; Applications

9522507 Ye The objective of this research is to develop and analyze interior-point algorithms and their variants for solving large-scale linear, quadratic, and nonlinear optimization problems that arise in production management and resource allocation. In the research, work will be performed to strengthen results obtained from prior research and explore new techniques for improving linear and nonlinear programming algorithms. The results of the research will be tested by solving actual industrial problems. Details of the research include (1) complexity analysis with the objective of developing complexity theory for linear programming (LP), (2) development of algorithms to extend LP-interior point algorithms to solve nonlinear optimization problems arising from engineering design and control, (3) decomposition and column generation for the development of interior point algorithms for solving large-scale, semi-infinite dimensional, and combinatorial optimization problems, and (4) implementation of the developed interior-point algorithms and development of public-domain computer programs based on the implementation. The findings and discoveries from this research will strengthen and improve theoretical results and practical performance of interior point algorithms. This will lead to the development of new efficient algorithms for a variety of optimization problems. Progress in the development of efficient algorithms for solving large-scale optimization problems improves the efficiency of manufacturing systems, communication networks, aircraft routing, multiple-flow operations, and resource planning. Strengthening research in this area will contribute to the national interest in industrial competitiveness and scientific knowledge.

小行星9522507 本研究的目的是开发和分析边界点算法及其变体，用于解决生产管理和资源分配中出现的大规模线性，二次和非线性优化问题。在这项研究中，将开展工作，以加强从以前的研究中获得的结果，并探索新的技术，以改善线性和非线性规划算法。研究结果将通过解决实际工业问题来检验。研究的细节包括：（1）复杂性分析，其目标是发展线性规划（LP）的复杂性理论;（2）开发算法，以扩展LP-内点算法来解决工程设计和控制中的非线性优化问题;（3）分解和列生成，以开发内点算法来解决大规模，半无限维，和组合优化问题，以及（4）实现开发的邻域点算法和开发公共领域的计算机程序的实现的基础上。 本文的研究成果和发现将进一步加强和完善内点算法的理论成果和实际性能。这将导致开发新的高效算法的各种优化问题。解决大规模优化问题的有效算法的发展进步提高了制造系统、通信网络、飞机路由、多流操作和资源规划的效率。加强这一领域的研究将有助于提高国家对工业竞争力和科学知识的兴趣。