Interior-Point Algorithms: Theories and Applications

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

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.