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

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

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.