CAREER: A Unifying Interior-Point Approach to Sensitivity Analysis and Reoptimization in Conic Programming

职业生涯：圆锥规划中敏感性分析和重新优化的统一内点方法

• 批准号: 0237415
• 负责人: Emre Alper Yildirim
• 金额: $ 40万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0237415&HistoricalAwards=false
• 关键词: CAREER; Unifying; Interior; Point; Approach

The primary objective of this Faculty Early Career Development (CAREER) Program project is to develop a unifying framework to study sensitivity analysis of convex optimization problems in conic form and reoptimization after a data perturbation. The emphasis will be on the use of interior-point methods with the following goals: (1) obtaining provably reliable information about sensitivity analysis of a large class of optimization problems with a very modest computational effort and (2) developing reoptimization strategies that take advantage of the information gained by solving the original optimization problem with provably better worst-case complexity estimates. In both cases, the theoretical work will be incorporated into efficient, state-of-the-art optimization solvers. In addition, applications of convex optimization in various areas will be investigated. The main focus here will be on the design, analysis, and implementation of efficient algorithms for problems arising in computational geometry and discrete optimization. The educational component of this project includes reworking the graduate nonlinear optimization course, starting a nonlinear optimization seminar, introducing new graduate courses, and writing a textbook on recent advances in sensitivity analysis. The work on sensitivity analysis will lead to an innovative approach that will accurately characterize the behavior of an optimal solution under perturbations in a fairly large class of optimization problems, thereby avoiding possible costly mistakes due to the use of mostly inaccurate sensitivity information provided by today's commercial solvers. This work is likely to lead to further insight into convergence issues in interior-point methods. The development of effective reoptimization strategies will help to design and implement faster algorithms for a wide variety of optimization problems that require solutions of closely related subproblems. These algorithms include branch-and-bound methods, sequential quadratic programming algorithms, and decomposition methods to solve structured large-scale optimization problems. Application of continuous optimization techniques in computational geometry and discrete optimization will widen the domain of problems for which efficient algorithms can be designed.This project will provide significant enhancements to the value of interior-point methods by enabling their use for the purposes of sensitivity analysis and reoptimization, two areas of immense practical importance that were previously considered to be the shortcomings of such methods. Collaborations with researchers in computational geometry and discrete optimization will lead to synergy among different disciplines. The ideas resulting from this project will be disseminated in a timely manner through publications, software development, and participation at national and international workshops and meetings. Graduate students will be involved through seminar participation and dissertation research with the researcher. New developments will be integrated into courses taught at both undergraduate and graduate levels.

本学院早期职业发展（Career）计划项目的主要目标是开发一个统一的框架来研究二次型凸优化问题的敏感性分析和数据扰动后的再优化。重点将放在内点方法的使用上，其目标如下：(1)以非常适度的计算量获得关于大型优化问题的敏感性分析的可证明可靠的信息；(2)开发利用通过解决可证明更好的最坏情况复杂性估计的原始优化问题获得的信息的再优化策略。在这两种情况下，理论工作将被纳入有效的，最先进的优化求解器。此外，还将研究凸优化在各个领域的应用。这里的主要焦点将是设计、分析和实现有效的算法，以解决计算几何和离散优化中出现的问题。这个项目的教育部分包括修改研究生非线性优化课程，开设非线性优化研讨会，引入新的研究生课程，并编写一本关于灵敏度分析最新进展的教科书。灵敏度分析的工作将导致一种创新的方法，该方法将在相当大的一类优化问题中准确地描述扰动下最优解的行为，从而避免由于使用当今商业求解器提供的大多数不准确的灵敏度信息而可能导致的代价高昂的错误。这项工作可能会导致进一步深入了解内点方法的收敛问题。有效的再优化策略的发展将有助于设计和实现更快的算法，以解决各种各样的优化问题，这些问题需要解决密切相关的子问题。这些算法包括分支定界法、顺序二次规划算法和分解方法，以解决结构化的大规模优化问题。连续优化技术在计算几何和离散优化中的应用将拓宽问题的领域，从而可以设计出高效的算法。这个项目将大大提高内点方法的价值，使它们能够用于敏感性分析和再优化，这两个具有巨大实际重要性的领域以前被认为是这种方法的缺点。与计算几何和离散优化研究人员的合作将导致不同学科之间的协同作用。这个项目产生的想法将通过出版物、软件开发和参加国家和国际讲习班和会议及时传播。研究生将通过参与研讨会和论文研究与研究员。新的发展将被整合到本科和研究生的课程中。