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

Suny At Stony Brook, Stony Brook NY

Investigators

Abstract

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.