Interior Point Methods Semidefinite Programming

内点法半定规划

• 批准号: 9706894
• 负责人: Kendall Atkinson
• 金额: $ 9.47万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-08-15 至 1999-02-16
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9706894&HistoricalAwards=false
• 关键词: Interior; Point; Methods; Semidefinite; Programming

PI: Florian Potra DMS-9706894 Interior Point Methods for Semidefinite Programming Abstract Further investigation of interior point algorithms for semidefinite programming (SDP) is proposed with emphasis on the study of global and local convergence, infeasibility detection and software development. While the vast majority of interior point methods for linear programming (LP) have proven polynomial complexity, this is not the case for SDP. The iteration complexity of interior point algorithms for SDP and its dependence on the search direction as well as on the central path neighborhood used by the algorithm will be investigated. Locally superlinearly convergent algorithms will be identified within the class of interior point methods for SDP with proven polynomial complexity. Superlinear convergence is especially important for SDP since no finite termination schemes exist for such problems. The local convergence analysis for interior point algorithms for SDP is much more challenging than those for LP and it will be a major focus point of the project. A C++ package for solving large-scale SDP problems will be developed. The code will efficiently handle different sparsity patterns arising in applications, and will provide refined infeasibility detectors. Semidefinite programming (SDP) represents one of the most important classes of optimization problems with many applications in science and engineering especially related to optimal control (in electrical engineering), optimal allocation of resources (in economics and manufacturing), structural optimization (in civil engineeering), etc. According to a recent survey paper, semidefinite programming is ``the most exciting development in mathematical programming in the 1990's''. Until recently no efficient methods were known for solving general semidefinite programming problems. In the late 80's it has been realized that interior point methods, initially developed for linear programming, can be successfully used for solving semidefinite programming problems. The advent of interior point methods has created new opportunities for the application of SDP in science and engineering. In order for these opportunities to materialize it is important to provide the scientific community with a good theoretical understanding of the behaviour of interior point methods for SDP and with reliable and efficient software capable of solving large-scale SDP problems. The project will investigate some of the most critical issues in the theory of semidefinite programming and will lead to the design of efficient practical algorithms. The software resulting from this project is likely to have a positive impact on several application areas in science and technology.

PI：Florian Potra DMS-9706894 半定规划的内点法 摘要 对求解半定规划的内点算法进行了进一步的研究，重点研究了算法的全局收敛性、局部收敛性、不可行性检测和软件开发。 虽然绝大多数线性规划（LP）的内点方法已经证明了多项式复杂性，但SDP的情况并非如此。将研究SDP内点算法的迭代复杂性及其对搜索方向和算法所用中心路径邻域的依赖性。 局部超线性收敛的算法将被确定内点方法类SDP证明多项式复杂性。超线性收敛是特别重要的SDP，因为没有有限终止计划存在这样的问题。SDP内点算法的局部收敛性分析比LP算法更具挑战性，这将是该项目的主要焦点。 将开发用于解决大规模SDP问题的C++包。该代码将有效地处理应用程序中出现的不同稀疏模式，并提供精细的不可行性检测器。 半定规划是一类重要的优化问题，在科学和工程中有着广泛的应用，特别是与最优控制有关（在电气工程），资源的优化配置（经济学和制造业），结构优化根据最近的一份调查报告，半定规划是“20世纪90年代数学规划中最令人兴奋的发展”。 直到最近还没有有效的方法来解决一般的半定规划问题。在80年代后期，人们已经认识到，最初为线性规划开发的内点方法可以成功地用于解决半定规划问题。内点法的出现为SDP在科学和工程中的应用创造了新的机会。为了实现这些机会，重要的是要提供科学界的内点法SDP的行为有一个很好的理论理解，并与可靠和高效的软件能够解决大规模的SDP问题。 该项目将调查半定规划理论中的一些最关键的问题，并将导致有效的实用算法的设计。该项目产生的软件可能对科学和技术的若干应用领域产生积极影响。